🚀 go-pugleaf

In article <ARI.HUTTUNEN.92Sep27174550@laphroaig.cs.hut.fi>, Ari.Huttunen@hut.fi (Ari Huttunen) writes:
|> I am concerned about the primeness of the prime numbers
|> that PGP generates. This is how they are done:
|> 	- first throw away numbers that are divisible
|> 	  by small primes
|> 	- 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.)
|> 
|> My concern is the number of rounds of the Fermat test. It's only 4.
|> I would not trust this level of primeness. Also, the resulting
|> number might be a Carmichael number. (So it would pass any number
|> of such tests.) 

It would be a lot better (and very little more expensive) to use the strong
pseudoprime test.  This removes powers of 2 from (n-1) and then checks that
the sequences of residues goes ..., -1, 1, ..., 1 as the result is squared.
There are no strong Carmichael numbers.  See any good book on number theory
for the details.


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm1@cus.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679