🚀 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
 
Why not?? Please see below.

>number might be a Carmichael number. (So it would pass any number
>of such tests.) 
 
No! No! No! A thousand times No!

I have said this many times, but the message does not seem to get through.

ONE test [Yes, I said ONE] is sufficient.  Added tests do NOT give much
added confidence. The reason for this comes from Bayes Theorem.
One must combine the probability that a composite will slip past the
test with the a priori probability that a randomly selected integer
of the appropriate size is a prime in the first place. Added
Fermat's theorem tests do NOT give very much increased confidence.
For example, suppose one selects a 100-digit odd integer at random
and it passes just ONE Fermat test. The 'probability' that this number
is composite is approximately 2.77 x 10^-8. [actually either it is
prime or it isn't. the probability means that if you do this approximately
36 million times, you should expect 1 composite number to get through]


If you don't understand this, I suggest you read the following:

Su Hee Kim & Carl Pomerance
The Probability that a Random Probable Prime is Composite
Math. Comp. vol. 53, 1989, pp. 721-742

In particular, pay attention to the discussion on pages 722-724.

Suppose, that B is the probability that a random integer up to x
passes a single strong probable prime test and that A is the
probability that a number up to x is actually prime.
Then, the probability that a number passing a single test is
actually composite is:

(1-A)B/(A + (1-A)B)

by Bayes Theorem.

The Monier-Rabin Theorem gives B <= 1/4. This then becomes

(1-A)/(1+3A)

if x is large, then A is small, so this result is quite weak.

Instead, let P(x) be the probability that a single Fermat test lets
a composite get through. Let P_k(x) be the probability that a 
composite gets through k independent tests. The popular belief
is that P_k(x) <= (1/4)^k, but this is WRONG.
Bayes Theorem gives P_k(x) <= 4^(-k+1)P(x)/(1-P(x)).

What makes a SINGLE test so effective is the fact that P(x) is
very small. See the Pomerance paper.


After you've read the paper, get back to me and we will talk further
if you like.

I would also hope that PGP does NOT do a simple Fermat test, but instead
does a strong PRP test. There are no 'Carmichael-like' equivalents for
strong probable primes. i.e. a number cannot be a strong prp to all bases.
Strong pseudoprimes are also rarer than Fermat pseudoprimes.

I think this response should go in the FAQ list.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"