Hi, it seems that the two discussions are somehow related
the idea of generating only prime candidates not dividible by small primes is interesting but, due to incremental search, it will not apply to next candidates however, it may be possible to use bit counting to perform a less biased walk AND efficiently avoid prime dividible by first primes : let say we generate randomly the first bytes of a key, except the last byte it is then possible to compute quickly all possible values for the last byte (or first depending on endianness) such that it is not dividible by first primes (as well as (p-1)/2 using a bit shift) looking at the last test of code provided, it can even be made quite efficiently using CRT given these values, we can test them in a random order in order to reduce the bias of incremental search in case of fail, just change last bit of second-to-last byte, and try again it should be statistically correct to do this on the byte of highest weight, but by applying this on the first byte we are sure that it will spawn a (strong) prime, just like incremental search This is just an idea as I didn't implement anything yet however with full optimization this could be quicker than incremental search And sorry if I'm mistaking anyhow Nico ----- Mail d'origine ----- De: Ben Laurie <b...@links.org> À: OpenSSL development <openssl-dev@openssl.org> Envoyé: Wed, 28 May 2014 11:10:25 +0200 (CEST) Objet: Re: open ssl rsa key generation improvement idea 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 ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
