On Tue, May 27, 2014, Ben Laurie wrote: > Nice idea. > > It inspired my son, Felix, and I to think about a related idea: > generate random numbers which are inherently coprime to small primes. > Felix went on to implement the idea, and include benchmarks and tests. > > Not finished - while implementing, we noticed that the existing prime > number generators have a bias. We decided to remove that, which caused > prime candidate generation to take more than twice as long (it was 42% > of the speed on Felix' laptop) - but the good news is our technique > doubled the speed, getting most of the loss back. > > We also don't currently deal with the case where add != 2 or rem != 1. > But its clearly possible without too much work. > > You could use his branch as a basis for testing this idea: > https://github.com/openssl/openssl/pull/116. >
On the subject of possible improvements. I can vaguely recall an algorithm for testing multiple divisors simultaneously by multiplying lots of small primes together to produce a product, c and then seeing if gcd(c, p) == 1. Precomputing 2^k mod c for suitable values of k might help too. No idea if that would be faster though. Steve. -- Dr Stephen N. Henson. OpenSSL project core developer. Commercial tech support now available see: http://www.openssl.org ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
