Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA

Le Chaud Lapin <jaibuduvin@xxxxxxxxx> wrote:

The primality test itself consists of trial division by the first
few thousand primes, which are not covered by the prime sieve, and
if the number still passes, then a Miller-Rabin or some other fast
test is done.

And finally AKS, heheh. :)

The reason for the many primality tests is efficiency. If you tested
every single number using, say, Miller-Rabin, generating a key could
well take a few hours. ;)

You can substitute Miller-Rabin for AKS or ECPP, though, if you want to
make sure that the number is prime. Slower, but correct in all cases.


Some might say it is unecessary, but IMO, a function with the
following signature..

bool Big_Integer::is_prime()

should not be named as such if there is a possibility that it will
return true when false is correct.

[We still keep our ::is_probably_prime (unsigned int)]

The name "is_prime" is really inappropriate. GMP calls its function
"mpz_probab_prime_p", but OpenSSL calls its functions like
BN_generate_prime and BN_is_prime, although it uses Miller-Rabin.

Though one might argue that the probability for false negatives is
totally neglible, the function name should be clear.


Regards,
Ertugrul.


--
http://ertes.de/

.