Re: Idle curiosity re RSA key generation

[nisse%lysator.liu.se@localhost (Niels Möller)]

Mouse <mouse%Rodents-Montreal.ORG@localhost> writes:

> When I'm generating RSA keys, the software I use filters using a
> small-primes wheel, then a Little Theorem test with base 2, then 32
> iterations of Miller-Rabin.

32 iterations of Miller-Rabin might be rather slow. Some alternatives
you might want to consider:

* Generate "provable" primes. If I remember correstly, the idea is to
  build them up recursively from a smaller prime q and then try
  candidates of the form p = k q + 1 (so that q is a largeish prime
  factor of p-1). For each candidate, besides a first round of trial
  division, attempt to prove (in tandem) either primality using
  Pocklington's theorem, or compositeness using Miller-Rabin. I think
  one variant is detailed (not very readable though, imo) in one of the
  appendices of
  https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf. I think
  speed of a careful implementation should be in the same ballpark as a
  dozen or so iterations of Miller-Rabin, but you don't need to worry
  about choosing the number of iterations. (And in practice, well tuned
  trial division/sieving is also important, in either case).

* The probabilistic "BPSW" test,
  https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.