🚀 go-pugleaf

	- then use Fermat's theorem 4 times
	  (Fermat's theorem:  if  b**(n-1) != 1 (mod n), then
	  'n' cannot be a prime. This requires that 'b' and 'n'
	  are relatively prime.)

In all the numbers less than 10^12 (or something like that), 
the Fermat test using b=2 will fail (i.e., give a false positive
reading) for only 15000 numbers.  Thats 15000 out of 10^12!  Thats
like 1 in 10^8, which are worse odds than you winning the lottery!

Now, if you iterate this four times, you increase your odds,
probabalistically, of having a good number.  Yes, you do have to
worry about the Carmichael numbers (since there are an infinity of
them), however there are far fewer Carmichael numbers than there
are primes.

-derek
--
         Derek Atkins -- MIT '93 -- Electrical Engineering
--warlord@MIT.EDU | ..!mit-eddie!mit-athena!warlord | s20069@mitvma.bitnet
      Chairman, MIT Student Information Processing Board (SIPB)
           MIT Media Laboratory, Speech Research Group