Conference rusure::math

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.

        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

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

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.

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

>As for hidden nodes, HANNAH isn't hidden !  It's 7.1019.
        
        Maybe FLOYD is and RUSURE knows where it is.
        
        Dan

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
[email protected]; I'm currently having mail troubles from an unknown source.

> >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

    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

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.

    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

    > MFY is Michael Yoder
    
    And the F stands for Floyd, right? :-)
    
    Andrew

>    And the F stands for Floyd, right? :-)

No, Floyd is just a node name... the F is for Franz, actually.

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.)

    1898  VMSDEV::HALLYB       29-SEP-1994     6  Carmichael numbers

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

    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.

>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

.10> Hi Michael.  Sorry, I don't remember every being in LCG in Marlborough.
.10> Isn't LCG Littleton anyway ?  (Not that I've had an office there
.10> either).  I'm in MRO1 now.
    
     I was in LCG in MR01 form 1978-1981. You were there for a while too,
     Eric. That was where you developed and wrote up the solution to
     Rubik's Cube. Remember "Doing a Hurley"?
    
From 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.)
    
    Can we work out a real example? I suggest n = 786433, which is prime
    and has the desirable property n-1 = 3�2^18 so exponentiations are
    fairly easy. What is a good guess for r, or do we just pick something
    at random?
    
      John

	re .20
        
>    Can we work out a real example? I suggest n = 786433, which is prime
>    and has the desirable property n-1 = 3�2^18 so exponentiations are
>    fairly easy. What is a good guess for r, or do we just pick something
>    at random?
    
	Okay, let p = 786433 = 3�2^18 + 1, and try to find r such
        that r^(p-1) = 1 mod p but neither r^((p-1)/2) nor r^((p-1)/3)
        is 1 mod p.
        
        The (p-1)/d terms for d = 2,3 are
        
        	(p-1)/2 = 393216
        	(p-1)/3 = 262144
        
        Try each exponent separately
        
        	2^393216 = 1 mod p
        	3^393216 = 1 mod p
        	it is pointless to try 4 :-)
	        5^393216 = 786432 mod p		= -1 mod p
        
        	2^262144 = 392448 mod p
        
        Okay, so we have a good base for each of (p-1)/2 and (p-1)/3.
        The good bases are 5 and 2, combine them in the form 5^x 2^y
        
        ((5^x)(2^y)) ^ ((p-1)/d) = ?
        at d=2:
        	((5^x)(2^y)) ^ ((p-1)/d) = ((5^x)(2^y))^393216
        	= (5^393216)^x (2^393216)^y
        	= (-1)^x 1^y
        	= (-1)^x
        all mod p of course, and for d=3:
        	((5^x)(2^y)) ^ ((p-1)/d) = ((5^x)(2^y))^262144
        	= (5^262144)^x (2^262144)^y
        	= 1^x 392448^y
        	= 392448^y
        again all mod p.
        
        All we need to do select x and y so that (-1)^x and 392448^y
        are both not 1; this is as easy as selecting x to be not a
        multiple of d=2 and y to be not a multiple of d=3.  So let
        x=1,y=1 (duh! why not just multiply the 5 and 2, who needs all
        this x and y stuff?) and try r = 5^x 2^y = 10
        
        	10^((p-1)/2) = 786432 mod p		not 1 mod p
        	10^((p-1)/3) = 392448 mod p		not 1 mod p
        
        and of course you can't forget to check
        
        	10^(p-1) = 1 mod p
        
        so 10 is a primitive root mod p, and "p-1 = 2^18 * 3, r = 10"
        can be passed around as a certificate that p is indeed prime.
        
        Note that this doesn't say that 10 is the *least* positive
        primitive root, although for this particular p it is.
        
        Dan

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

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

.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

.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

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

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

    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

>.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.

        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