On 28 May 2014 13:32, <nicolas....@free.fr> wrote: > 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
a) The incremental search introduces bias, so not clear we should really maintain that b) It isn't very hard to incorporate incremental search in our scheme I am not suggesting that your idea is not also worthwhile - in particular, you can probably go to higher primes than our scheme - the tables quickly become pretty large... > 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 ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org
