Actually, I was proposing another way to perform incremental search using divisibility properties The fact is I agree with your b) point, I was trying to explain a way to do it
sorry if I didn't make myself clear there are two main points : - incremental search can be improved by testing less values for example with a 1024 bits prime, just take 1016 bits at random, and compute all possible values for the last 8 bits such that the resulting number is not dividible by primes less than 25 this allows to avoid the 2/3 that would give candidates that are obviously not prime the question left is how to compute these values efficiently, or at least quicker than multiple divisions - with a reduced number of values for last byte, they can be randomly tested given the previous example, you get get less than hundred possibilities I think it is possible at this point to choose them successively in a random sequence, and thus reduce the discussed bias (Note that the random sequence can be chosen once and for all at beginning, and be reused for next tries) however, I'm still not sure that this would result in a gain in speed guess I'll have to produce some code before going deeper into details ----- Mail d'origine ----- De: Ben Laurie <[email protected]> À: OpenSSL development <[email protected]> Envoyé: Wed, 28 May 2014 14:54:00 +0200 (CEST) Objet: Re: Re : Re: open ssl rsa key generation improvement idea & Prime generation On 28 May 2014 13:32, <[email protected]> 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 > > ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [email protected] Automated List Manager [email protected]
