🚀 go-pugleaf

In an article, Simson L. Garfinkel writes:
>> odd numbers.  From there count by twos, testing each number for primality
>> (easy), and stop when you have your two totally secret 100-digit primes.
>
> WAIT! It is not "easy" to test a 100-digit number for priamity.
>
> How do you do that? To tell if a number is prime or not, you factor it.

You can tell if a number is "probably" prime without a lot of
computation.  Let P be the number that you want to test.  Let N be
any positive integer smaller than P.

One computes (N|P), and compares it to something that I forget ( 
but it was something real simple, like -1**something).  If P is 
prime, then they will always be equal.  Note that (N|P) is about 
as difficult as computing g.c.d., i.e., not difficult.  If P is 
not prime, then there will be N for which they are not equal.  

Furthermore, the N for which they are equal form a subgroup of the
integers mod P under multiplication.  Thus, for composite P, at
most half of the choices for N can lead to equality.

Thus, if we need to check to see if P is prime, and want to be, say,
99.9% certain of the result, we pick 10 N at random, and test them.
If any fail, we know that P is composite.  If they all pass, then
there is a 99.9% chance ( 1023/1024 ) that P is prime.  If we want
to be really confident, pick 10 more N.
-- 
Religion: just say "no"

Tim Smith       USENET: sdcrdcf!ism780c!tim   Compuserve: 72257,3706
                Delphi or GEnie: mnementh