When testing a random integer for primality, first try dividing through by some number of small primes before moving on to the Miller-Rabin algorithm. How many primes should be tried to minimize the total expected running time for a given size integer being tested? This seems a tricky theoretical problem involving the running time of modular exponentiation and the density of primes, as well as a practical implementation optimization challenge.
Empirically, that number seems to be in the thousands for RSA primes.
No comments :
Post a Comment