On 28 May 2014 00:03, Viktor Dukhovni <openssl-us...@dukhovni.org> wrote: > On Tue, May 27, 2014 at 09:04:20PM +0100, Ben Laurie wrote: > >> 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. > > When you say small, you mean really small right? Not the first > 2048 primes as in the OpenSSL code, but say the first few, for > example those less than 25?
Yeah - we went up to 11 for the 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. > > Do the resulting candidates also avoid having small odd factors in > (p-1)? This means p != 0 or 1 mod each of the first batch of odd > primes. No, but the method could be extended to do that pretty easily. > For the first 9 primes: > > 2, 3, 5, 7, 11, 13, 17, 19, 23 > > this leaves only > > 7,952,175 = 1 * 1 * 3 * 5 * 9 * 11 * 15 * 17 * 21 > > acceptable odd values modulo: > > 223,092,870 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 > > or ~7.1% of the odd candidates. > > -- > Viktor. > ______________________________________________________________________ > OpenSSL Project http://www.openssl.org > Development Mailing List openssl-dev@openssl.org > Automated List Manager majord...@openssl.org ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
