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?
> 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.
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
