[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

2028.0. "primes for dummies" by HANNAH::OSMAN (see HANNAH::IGLOO$:[OSMAN]ERIC.VT240) Mon Feb 19 1996 12:42

Hi.  I'd like to do a discussion about the interesting proof in 178.23.

However, I wanted to first make the following request to "Yoder" but all
attempts to mail to "FLOYD::YODER" failed with "remote node unknown", so
I make it here.



Hi.  You posted some useful stuff in math 178.22 and
then you posted a correction in 178.23.

To make it all easier to read, could you please do this:

	Notes> open math

		178.22

		extract foo.bar ! save a copy

		delete ! get rid of erroneous copy

		178.23

		delete

		reply foo.bar ! edit your original

This way, we'll have only your corrected version.

By the way, it's best to do this *before* someone puts
in another reply to that note.

I'm particularly interested in studying what you wrote, but
it's complicated enough without the erratum, so it would
be easier for me if you edited as above.

Thanks.

/Eric
T.RTitleUserPersonal
Name
DateLines
2028.1Note 178.22 is fixedFLOYD::YODERMFYMon Feb 19 1996 13:213
Well, I can't mail to hannah::osman either, so I suppose we're even.

I edited 178.22 as requested, and deleted 178.23.
2028.2CSC32::D_DERAMODan D'Eramo, Customer Support CenterMon Feb 19 1996 14:027
        If RUSURE::MATH shows you as FLOYD::YODER and HANNAH::OSMAN
        then you should be able to send mail to RUSURE::FLOYD::YODER
        and RUSURE::HANNAH::OSMAN.  Of course, the RUSURE folks could
        probably tell you what the approved "gateway" node is for the
        nodes in hidden areas.
        
        Dan
2028.3HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Feb 19 1996 16:1035

Thanks for the edit !  I'll study the proof and ask questions about it
later.

As for hidden nodes, HANNAH isn't hidden !  It's 7.1019.

By the way, Yoder, what's your first name ?  Are you in elf ?  I know
you're not Beth Yoder.  The Yoders advertised are

$ elf yoder

Common Name:   ELIZABETH YODER
Search Surname:  YODER,  BETH YODER,  YODER  Search Given Name:  ELIZABETH,
ELIZABETH M,  ELIZABETH YODER,  ELIZABETH M YODER  DTN:  343-5090,  343-5090
Telephone:  404-343-5090  Intrnl Mail Addr:  ALF1-2/M20  Location:  ALF
Node:  SAHQ  Username:  YODER  Org Unit:  SYSTEMS INTEGRATION,
DIGITAL SYSTEMS INTEGRATION  Position:  SENIOR ADMINISTRATIVE ASSISTANT

Common Name:   KATHRYN YODER
Search Surname:  YODER  Search Given Name:  KATHRYN,  Kathryn A Yoder
DTN:  592-1489  Telephone:  (719)592-1489,  FAX:(719)592-4129
Intrnl Mail Addr:  CXO3  Location:  CXO  Node:  CSC32  Username:  K_YODER
Org Unit:  AMERICAS FEW PLACE ZONE,  LST TEAM,  TPS TEAM

Common Name:   KENNETH YODER
Search Surname:  YODER  Search Given Name:  KENNETH,  KENNETH JAY
DTN:  454-3351  Intrnl Mail Addr:  KZO2  Location:  KZO
Org Unit:  ABU SALES & MARKETING



Thanks.

/Eric
2028.4groundworkFLOYD::YODERMFYMon Feb 19 1996 16:1625
To work towards what Eric would like, here is the groundwork for the method,
with some historical information.

Fermat proved that for a /= 0 (mod p) and p a prime, a^(p-1) == 1 (mod p).

Euler generalized this to all positive n: if (a,n) = 1, then a^phi(n) == 1 (mod
n) where phi(n), the "Euler totient function," is the number of integers i such
that 1<=i<=n and (i,n) = 1.  (The number of positive integers less than or equal
to n and relatively prime to n.)

Euler showed that if (m,n) = 1, then phi(mn) = phi(m)phi(n).  Clearly, for a
nontrivial power of a prime p^e, phi(p^e) = p^e(1-1/p) since the numbers not
relatively prime to p^e are just the multiples of p.  From these two, we get the
formula

  phi(n) = n(1-1/p1)...(1-1/pk)

if {p1,...,pk} are all prime divisors of n, the pj being distinct.

The usual proof of Euler's theorem uses cancellability of modular arithmetic: if
(a,n) = 1 and ax==ay (mod n), then x==y (mod n).  So, if x1,...,xt are the
numbers <= n and relatively prime to n, where t=phi(n), the numbers
a*x1,...,a*xt (mod n) are all distinct and relatively prime to n, so they must
be the same set of numbers, perhaps in a different order.  Taking the product of
the two sets, we get a^t*x1...xt==x1...xt, so a^t==1.
2028.5HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Mon Feb 19 1996 18:0021
Thanks, that will help !  (I'd still like to know what "MFY" stands for though).

I had started to work things out with the *wrong* def for phi(n).  I was
considering it as the *sum* of all the factors, not including n.  So
I was falsely falculating phi(10) as 1+2+5 which is 8.  I even "checked"
a few examples to make sure, for instance, that 7^8 is 1 mod 10.  I calculated
this as 7*7 is 49 which is 9 mod 10, and 9*7 is 63, which is 3, and 3*7
is 21, which is 1, and 1*7 is 7, and 7*7 is 49 which is 9, and 9*7 is 63
which is 3 and 3*7 is 21 which is 1.

In fact, I even tried a second example.  3^8, which is (mod 10) 3,9,7,1,3,9,7,1.

Of course, now I know the real phi(10) is 4, since 1,3,7 and 9 are the numbers
prime to 10, and there are 4 of them.

I wonder if it's just coincidence that 8 worked as well as 4.  In other words,
if we call rho(n) the *sum* of all the factors of n not including n, will
x^rho(n) be 1 whenever x is relatively prime to n ?

/Eric
2028.7CSC32::D_DERAMODan D'Eramo, Customer Support CenterTue Feb 20 1996 13:285
>As for hidden nodes, HANNAH isn't hidden !  It's 7.1019.
        
        Maybe FLOYD is and RUSURE knows where it is.
        
        Dan
2028.8nameFLOYD::YODERMFYTue Feb 20 1996 13:595
Sorry, Eric, I keep forgetting to include this... MFY is Michael Yoder.  I think
we sat near each other ages ago in LCG in Marlborough.

Other things to try for a mail address are decada::yoder or possibly
yoder@g.enet.dec.com; I'm currently having mail troubles from an unknown source.
2028.9confused as usualHANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Feb 21 1996 12:479
> >if we call rho(n) the *sum* of all the factors of n not including n, will
> x^rho(n) be 1 whenever x is relatively prime to n ?
> 
> No: let n=4, and x=3.  rho(n)=7, 3^7==3 (mod 4).
    
    Sorry, I'm just another dummie on this bus, but to me, rho(n)=rho(4)
    =1+2=3.  I don't see how you got 7.
    
    /Eric
2028.10HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Feb 21 1996 13:0710
    Hi Michael.  Sorry, I don't remember every being in LCG in Marlborough.
    Isn't LCG Littleton anyway ?  (Not that I've had an office there
    either).  I'm in MRO1 now.
    
    Anyway, I've enjoyed your math postings very much.  I'm still curious,
    why aren't you listed in elf ?   
    
    Thanks.
    
    /Eric
2028.11re: .9FLOYD::YODERMFYWed Feb 21 1996 13:289
Sorry, my note was so wrong I decided to just delete it.

I was treating rho(n) as the sum of all divisors of n (not excluding n).

This is needed to get the property that rho(mn)=rho(m)rho(n); with the modified
definition you get rho(mn) = (rho(m)+m)(rho(n)+n) - mn.

Are you the Osman who did the "TV" program which was TECO with display?  If not,
I've been confusing you with someone else.
2028.12HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Feb 21 1996 13:308
    Yup, when I got to dec from MIT in '74 (I worked at MIT, didn't attend
    school there), I was shocked that dec engineers didn't have a "screen
    teco".  They only had line-more teco.
    
    So I took vteco which ran on tops20 and produced TV which gave screen
    view of the file being edited (what a concept!).
    
    /Eric
2028.13exitTPOVC::BUCHANANThu Feb 22 1996 03:265
    > MFY is Michael Yoder
    
    And the F stands for Floyd, right? :-)
    
    Andrew
2028.14FLOYD::YODERMFYThu Feb 22 1996 13:043
>    And the F stands for Floyd, right? :-)

No, Floyd is just a node name... the F is for Franz, actually.
2028.15Continuing the note topicFLOYD::YODERMFYMon Feb 26 1996 12:4323
Re: .10, I'd guess I'm not in ELF because I'm a contractor (not that this is any
intrinsic reason, but I don't know the policy).

Continuing the topic Eric wanted to talk about... first let's do the easy task
of showing one way to prove a number is composite without factoring it.

From Fermat's theorem, if p is prime, then a^p==1 (mod p) for any positive a
less than p.  So suppose p is a "candidate" prime.  If, for some such a, a^p
isn't congruent to 1, we know p isn't prime after all.  But this fact gives us
very little clue as to how p might be factored.

The proof of primality I mentioned uses similar (but more involved) logic.

One might ask whether, if p is composite, some such a can always be found.  (We
must restrict ourselves to those cases where a is relatively prime to p in order
to avoid a trivial answer.)  The answer is no.  There are composite numbers n
such that, for all a with (a,n)=1, a^n==1 (mod n).  These are called Carmichael
numbers.

Three fairly easy theorems: (1) n is Carmichael iff n-1 = k*phi(n) for some k>1.
 (2) If n is Carmichael, n is squarefree (hence it is the product of distinct
primes).  (3) If n is Carmichael, n has at least 3 distinct prime divisors.  (If
people want to further discuss these, I suggest starting a new note series.)
2028.16topic *EVMS::HALLYBFish have no concept of fireMon Feb 26 1996 16:051
    1898  VMSDEV::HALLYB       29-SEP-1994     6  Carmichael numbers
2028.17HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Fri Apr 12 1996 21:5447
o.k. On with what I was originally going to ask.  Here's
what was written in 178.22:

>
> So, if (for some r) we have r^(n-1)==1 (mod n), and r^((n-1)/d) /= 1 (mod n)
> for all prime divisors d of n-1, n must be prime.  (If true, this also shows
> that r is a primitive root of n.)
>

The original question of mine was how we can determine that something
is prime without dividing it by every prime up to its square root, and
the above was Yoder's answer.

So let's try an example.  Suppose we want to know if 1,000,001 is prime.
(There's a cute way to know it's not, let that be a side puzzle).  The above
recipe asks us to find some r for which r^1000000==1 (mod 1000001) and
r^(1000000/d) != 1(mod 1000001) for all d gozinta 1000000.

I need to convince myself that finding such an r is less effort than dividing
1000001 by all primes up to 1000.

First of all, what is d.  Well, d are all the primes that divide (gozinta)
1000000.  Let m=1000000 so I don't have to keep typing 1000000.

m=10^6 = (2*5)^6, so d is the set of two numbers 2 and 5.

[For those of you that this drivel seems elementary, remember that this is
exactly why I created this "primes for dummies" topic separate from 178].

So we want to find some r for which r^(m/5) and r^(m/2) !=1 (mod m+1) and
r^m==1 (mod m+1).

Let's try r=2.  We look at 2^500000 and 2^200000 and hope they're not
1 mod 500001.  How are we going to determine that ?  In particular, how
are we going to determine it in less effort than to divide m+1 by all
primes < 1000 ?

And after 2 passes *that* test, we still have to hope that 2^m==1 mode m+1.
This seems unlikely.

So I'd appreciate some more insight here as to why this alternate method
of testing primality can be made quicker than the old fasioned way.

Thanks.

/Eric
2028.18some musingsAUSS::GARSONachtentachtig kacheltjesFri Apr 12 1996 23:1234
    re .17
    
>We look at 2^500000 and 2^200000 and hope they're not 1 mod 500001.
>How are we going to determine that ?
    
    The first thing to note is that a^(x+y) == a^x mod t  a^y mod t (mod t),
    that is, it is not necessary to raise a to the kth power and then find
    a^k mod t. Instead, for example, if we were going to find a^k by
    multiplying a by itself lots of times, we could reduce mod t any number
    of times along the way without affecting the result. This keeps the
    size of integers that we have to work with down.
    
    The second thing to note is that a^k can be found without doing k
    multiplications but rather in approximately log[2]k multiplications
    using an algorithm doubtless somewhere else in this conference.
    
>In particular, how are we going to determine it in less effort than to divide
>m+1 by all primes < 1000 ?
    
    Very roughly speaking then the effort with this method is sqrt(m)
    divisions.
    
    [In reality though since prime density goes down, the number of primes
    is much less than this but on the other hand, you won't know which
    numbers are prime. I wonder whether division by primes only is at all
    practical for large values of m i.e. one would have to divide by all
    numbers <= sqrt(m).]
    
    Thus for m=1000000 we have the choice of 20*z operations vs. 1000
    divisions. Well that doesn't answer your question because I don't know
    z. z depends on how you find r. Perhaps someone else can provide more
    information. Clearly though the difference between the basic approaches
    will widen as the number, m, increases. For m, a 6n digit number, we are
    looking at approximately 20*n*z operations vs. 10^(3n) divisions.
2028.19CSC32::D_DERAMODan D'Eramo, Customer Support CenterFri Apr 12 1996 23:4131
>So let's try an example.  Suppose we want to know if 1,000,001 is prime.
        
        This isn't a primality test.  If you want to know whether N is
        prime, there is a different test that you apply.  Once you
        know N is prime and have a complete factorization of N-1, then
        you can search for a primitive root--not to test that N is
        prime but to keep around as a certificate of primality.  You
        can send N, the primitive root, and the complete factorization
        of N-1 to anyone and they can use it to verify that N is
        indeed prime.  [If they challenge you on some of the large
        prime factors of N-1, then send them certificates of their
        primality too.]
        
        So if you already know 1000001 is composite, then it is
        pointless to try to find a primitive root.
        
        For testing primality of large numbers, there is another test
        based on a similar concept of a certificate of compositeness. 
        A factor of N is quite a convincing certificate that N is
        composite :-) but it turns out there there are other types of
        certificates of compositeness and in the very worst case only
        about 1/4 of the integers in the range 2 .. N-1 fail to be
        certificates of compositeness for N when N is truly composite. 
        So try several numbers in that range, and if none turn out to
        be certificates of compositeness for N, then N is probably
        prime.
        
        There are other kinds of certificates of primality too such as
        the test in reply 2.5.
        
        Dan
2028.2025 years ago I used to know this stuffEVMS::HALLYBFish have no concept of fireTue Apr 16 1996 19:3519
2028.21CSC32::D_DERAMODan D'Eramo, Customer Support CenterTue Apr 16 1996 23:5161
2028.22HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Apr 17 1996 13:077
I still don't see why we can't do the same sort of thing to prove that
1000001 is not prime.  In fact, I thought the whole value of this primitive
root method is to somehow determine whether a number is prime without
doing all the test divisions.

/Eric
2028.23CSC32::D_DERAMODan D'Eramo, Customer Support CenterWed Apr 17 1996 14:467
        For n = 1000001, the quickest way is to show that
        
        	2^(n-1) = 1 mod n
        
        is false.  So n cannot be prime.
        
        Dan
2028.24"Less filling!" "Tastes great!" the math wayEVMS::HALLYBFish have no concept of fireWed Apr 17 1996 17:1620
.22> In fact, I thought the whole value of this primitive
.22> root method is to somehow determine whether a number is prime without
.22> doing all the test divisions.
    
    But this is not the case. The value of this "primitive root method" is
    to PROVE that a number is prime, and to provide enough information that
    anyone who cares to spend a VERY small amount of time can verify.
    
    Usually you've already done a bunch of primality tests and concluded
    the number is "probably prime". Somewhere around this point it becomes
    easier to prove N is prime than to try to find its factors. That's
    where the primitive root stuff comes in.
    
    If the number is a pseudoprime (looks like a prime) but is really
    composite, you won't be able to prove it's prime (no "r" found) and
    at some point you swing back to the other side, spending more time on
    more primality tests and perhaps widening search ranges for various
    factoring methods.
    
      John
2028.25HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Apr 17 1996 18:0119
.15 says:


> From Fermat's theorem, if p is prime, then a^p==1 (mod p) for any positive a
> less than p.  So suppose p is a "candidate" prime.  If, for some such a, a^p
> isn't congruent to 1, we know p isn't prime after all. 

Then .23 says:

>    For n = 1000001, the quickest way is to show that
>                	2^(n-1) = 1 mod n
>                is false.  So n cannot be prime.

.23 doesn't look like a valid application of .15.  For one thing, the exponent
and the modulus are the same number in .15 (they're both p).  They're different
in .23 (exponent is n-1, modulus is n).

/Eric
2028.26HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Apr 17 1996 18:1119
Doing my own application of .15, which says

	If a^p != 1 (mod p) for some a, then p isn't prime

we can say

	If 2^1000001 != 1 (mod 1000001) then 1000001 isn't prime

Let's see, how would I calculate 2^1000001 modulo 1000001 ?

Well, 2^18 is 262144, so 2^19 is 524288, so 2^20 is 1048576.

This is the first power greater than 1000001, so we have

	2^20 = 48575 (modulo 1000001)

This is still going to take awhile !  Is there an easy way ?

/Eric
2028.27HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Apr 17 1996 18:139
By the way, the totally alternate way of observing that 1000001 isn't prime
is to see it as a^3+1 which algebraically is divisible by a+1.  In our case,
a=100, so 101 is a factor (quotient is 9901).

But I don't want this fact to deter from exploring this primitive root
business.

/Eric
2028.29Maybe this will help clear things upEVMS::HALLYBFish have no concept of fireWed Apr 17 1996 18:4318
    Here's how you raise a base to a huge power in log(p) time.
    
    Say you want to raise a to the 1000001 = ^X000F4241 = ^B11110100001001000001
    							    ^ start here
    
    Set answer to 1.
    Loop: If bit = 1; multiply answer by a. Reduce mod N if desired.
    	  If no more bits to the right of current point, done.
    	  Move current point 1 bit to the right.
    	  Square answer. Reduce mod N if desired.
    	  Goto loop.
    
    I'm sure someone can express this in a GOTO-free WHILE construct.
    
    Fermat's little theorem really says:
    	 If p is prime, a^p == a (mod p), or a^(p-1) == 1 (mod p)
    
      John
2028.30Re: .15, .23FLOYD::YODERMFYWed Apr 17 1996 18:456
>.23 doesn't look like a valid application of .15.  For one thing, the exponent
and the modulus are the same number in .15 (they're both p).  They're different
in .23 (exponent is n-1, modulus is n).

That's because .15 is wrong: the exponent should be p-1.  My mistake.
2028.31CSC32::D_DERAMODan D'Eramo, Customer Support CenterWed Apr 17 1996 19:2515
        For "a" an integer and "p" a prime, if p does not divide a
        then a^(p-1) == 1 mod p.  Multiply both sides by p and you get
        that if p does not divide a then a^p == a mod p.  But if p
        does divide a then p also divides a^p, and so in the case that
        p divides a you also have a^p == a mod p.
        
        Putting it all together you have Fermat's Little Theorem:
        
        	"p" a prime, "a" an arbitrary integer
        	implies both
        
        		a^p == a mod p
        		if (not (a == 0 mod p)) then a^(p-1) == 1 mod p
        
        Dan