Date: Wed, 22 Oct 1997 17:39:40 -0600
From: rusin@math.niu.edu
To: Mitrick Johns <T80MAJ1@WPO.CSO.NIU.EDU>
Subject: Re:  test -Reply

Actually, finding primes is easy. An  n-digit number is prime with
probability about 1/log(n), so you get large primes by picking random
(odd!) integers of the right size, and discarding if prime. Of course,
you then need a way of determining if a large number really is prime of
not. In general, Fermat's little Theorem is just the tool we need!
To see if a number  P  is prime, pick a few random  x's  and see if
x^P=x mod P. If not, P is not prime. If yes, then, well, P is 
"probably prime". But it's not too hard to fix the Fermat procedure
into a real primality test. Popular symbolic algebra programs have a
"nextprime" function, easily providing 100-digit primes in the bat of
an eye.

> I am having a bit of trouble understanding
why the government is trying so hard to prevent the export
of cryptography software.

"We are the government. You have nothing to fear. Just do as
we say."

They explicitly forbid the export of encodings of this very routine which
utilize composite moduli of larger than, oh, 80 digits or so. (An 80-digit
number is with today's technology reasonably easy to factor if really
necessary.)

dave

==============================================================================
Date: Fri, 31 Oct 1997 14:35:40 -0600
From: Mitrick Johns <T80MAJ1@WPO.CSO.NIU.EDU>
To: rusin@math.niu.edu
Subject: Re:  test -Reply -Reply

Dave--getting back to this how to find primes question, I
have a problem with using Fermat's little theorm.  The way
it is written, as "if" not "iff", the contrapositive goes
something like "if, for EVERY integer a, a^p is not
congruent to a (mod p), then p is not prime."  So, as far as
I can see, this theorem is no better at determining
primeness than the old-fashioned method of checking every
prime less than the square root of p, since you still have
to check a very large number of possibilities.  Is the
"real" primality test you mentioned easily explained?  I
remain curious about this.  --Rick

==============================================================================
Date: Fri, 31 Oct 1997 16:14:36 -0600 (CST)
From: Dave Rusin <rusin>
To: T80MAJ1@WPO.CSO.NIU.EDU
Subject: Re:  test -Reply -Reply

You're right, FlT won't give an ironclad guarantee that a number is prime.
There are numbers ("Carmichael numbers") which have the property that
a^(n-1)=1 mod  n  for every  a  which is relatively prime to  n; the
smallest is  n=561. So FlT alone is useless for detecting composite numbers
of this type unless you are lucky enough to try using, for  a , one of the
numbers with a common factor with  n. (Your chances of finding such an  a
by picking at random are nearly nil when  n  is a product of large primes.)

But I _can_ improve this test to a real primality test. Watch. We test to
see if  561  is prime. (It's really  3*11*17):


Round 1: Pick an  a < 561. I pick, say, a=511. 
Is  a^560 =  1 mod 561?  Yes! 561 may be prime.

Round 2: Well, you could pick  different  a, but here's the next requirement
I have which  n  must satisfy. We have verified that for  a=511, we have
a^560=1 mod 561. This means that  x=a^280 is a number with  x^2=1 mod 561.
If 561 were prime, the only such  x  would be  x= +- 1 mod 561. OK, so 
let's check: is  a^280 = +-1 mod 561? Yes!(namely +1); 561 may still be prime.

Round 3: Repeat -- we now should have  a^140 = +- 1. Yes! (=+1)

Round 4, Round 5: We can keep this up with  a^70 and a^35. If one of them is
+1 and the next isn't  +-1, we have proof that  561  is composite.
In fact, we discover  a^35=+1, so  561  still looks prime, and this
line of testing is over. (We have to quit now because  35  is odd.)

Rounds 6-10:
Now we start again with a different  a . Form the sequence of numbers
	a^35, a^70, a^140, a^280, a^560
If the last isn't  1, then 561 is composite. (Turns out that will never
happen). If the predecessor of the first  1  isn't  -1, then  561  is
composite. If we have all 1's, or some junk followed by a -1 and then
all 1's, then the test is inconclusive: 561 could still be prime.
This is known as the Miller-Rabin test: each  a  gives 561 a chance to
demonstrate that it is composite, although  561  could pass this test for
a given  a, as we noted above for  a=511.

So we try, say, a=103. Here's the sequence to compute: a^35, ... is
	1, 1, 1, 1, 1.
Darn; looks like 561 may still be prime. Need to try another  a.

Rounds 11-15: Start again, maybe with a=460, or 256, or...


Does this sound like the FlT test -- try lots of  a's, wait for a clear shout
"composite!", otherwise try more  a's? It is, but with a difference: if
N is composite, there _will_ be  a's  which make  N  fail the M-R test.
Not only that, but your chances of finding such an  a  are excellent,
just by picking  a  at random.

Here's the scoop. Suppose  N = K*M  is composite. We may assume  K  and
M  are relatively prime unless  N  is a prime power, which is easy to
check for. By the Chinese Remainder Theorem, we can find an  a  with
a=+1 mod K and a=-1 mod M. Then  a^2 = 1 mod K and mod M and hence mod  N;
however, a  itself is congruent to neither +1 nor -1 mod  N.

Note that  a  raised to any odd power will still satisfy the same congruences
mod  K, M, and N. Thus with this choice of  a, the M-R sequence will begin
with something which is neither +1 nor -1 mod  N  but whose square (the
next M-R term) is +1. So this  a  will show  N  is composite.

Moreover, this isn't the only such  a. If for any  a  we have a term  x  in
the M-R sequence with  x^(2i) = 1 mod N, then  x^(2i) = 1 mod  M  and  K, too.
But even if  x^i = +-1 mod K and x^i = +-1 mod M (that would be forced, for
example, if  M  and  K  were prime), it's just as likely that the
signs would agree as disagree. That is, it's just as likely that
x^i = +-1 mod  N  as that  x^i <> +-1 mod  N. So when choosing an  a
at random, we have at best a 50-50 chance of passing the M-R test if
N  is composite.

If I choose two a's at random, I have at most a 1/4 chance of not
discovering 561 to be prime.  Continuing in this way, we see that the
chance of a composite being undetected drop to zero as the number of
a's increases.

Of the 320 a's prime to 561, all 320 of them have  a^560=1 mod 561.
-->Only 160 of these have a^280= +-1 mod 561 (in fact, it's never -1); that is,
half of them will have a M-R sequence " *,*,*,(not +-1),1 " and thus
prove 561 composite. I was unlucky (3:1 odds!) to pick two losers in a row.
-->Only 80 of those with a^280=1 have a^140=+-1 (again, it's never -1).
(These are the ones with M-R sequence "*, *, 1, 1, 1". Imagine my luck,
picking two of these one-out-of-four numbers in a row.)
-->Only 40 of those with a^140=1 have a^70=+-1 (again, it's never -1).
(Wow, only 40 numbers out of 320 could give  "*,1,1,1,1". If 64 people had
each picked two  a's, I'd be the only one to get two of these in a row.)
-->Only 5 of those with  a^70=1 have a^35=+-1 (again, it's never -1).
(Even among the previous 40, 35 have a sequence "*,1,1,1,1" with "*" <> +-1.
So in fact the  511 and 103  I picked were hardly representative;
I had to search pretty hard for those  a  which would allow the M-R test
to fail to detect 561 as a composite!)

So if you picked  a's  at random, your chances of getting 561 to pass the
M-R test get slimmer and slimmer until when you picked your sixth different
a, you would _have_ to have found one for which the M-R test failed.


Is this still probabilistic? Yes, but assuming a pretty widely believed
conjecture (the Generalized Riemann Hypothesis) one can show the
following: 
	if N passes the Miller-Rabin test for all  a < 4(log N)^2
	then  N  is prime.
So primality can be determined in an amount of time which is proportional
to a power of  log(N). This is a tremendous advance over trial division,
which requires a number of steps proprotional to a power of  N.


Is this then still conjectural? Well, yes, but I'd have to say that
for the GRH to fail would be one of the most monumental discoveries of
20th century mathematics. It's pretty sure to be true. But if you're the
nervous type, you can use alternative methods of primality testing 
which are more complicated but which can deterministically decide whether
N   is prime or not in an amount of time polynomial in  log(N).


If you're interested in this kind of thing I could give you a lot of
references. A nice survey is by Richard Pinch in Notices of the American
Mathematical Society, v. 40 (1993) pp 1203-1209. He's also got some
online info, or you could read about these ideas at my website too. Try
	http://www.math.niu.edu/~rusin/known-math/index/11Y05.html

dave