🚀 go-pugleaf

> >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.

In article <11617@sun.uucp>, (Ed Falk) quotes from RSA paper:
> VII(B). How to Find Large Prime Numbers
> 
>   To find a 100-digit "random" prime number, generate (odd) 100-digit
> random numbers until a prime number is found.  By the prime number
> theorem[9], about (ln 10**100)/2 == 115 numbers will be tested before
> a prime is found.
>    To test a large number 'b' for primality we recommend the elegant
> "probabilistic" algorithm due to Solovay and Strassen[14].  It picks a
> random number 'a' from a uniform distribution on {1,...,b-1}, and tests
> whether

  To give the most problems to a cryptanalyst who is trying to factor the
number, one technique can be used to generate what the author calls "strong
primes".  That is, a 100-digit prime number, n, is selected such that
n+1 and n-1 both have large prime factors.

  This is from a paper (circa 1983?) by John Gordon titled "Strong Primes
are Easy to Find".  He gives the derivations of how to find strong primes
and determines that finding such numbers is 19% slower than finding a
garden-variety large prime.

  A suggestion he lists for speeding up the search for primes (which
dominates in the search for strong primes) is to eliminate multiples of
the first 54 primes (ie, 2,3,5...,251).  This leaves roughly 10% of the
randomly generated numbers to test for primality.

Bob Devine