Nice idea. 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.
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. We also don't currently deal with the case where add != 2 or rem != 1. But its clearly possible without too much work. You could use his branch as a basis for testing this idea: https://github.com/openssl/openssl/pull/116. On 26 May 2014 02:31, Russell Harkins <russ...@russellharkins.info> wrote: > Hi SSL Team, > > I was looking for ways to make calculating RSA public/private keys faster. > I noticed that trial division was being done to test if a number is > divisible by small primes. > Roughly 2/3 of all odd numbers are divisible by primes less than 25. I > found a faster way to test the divisibility than using division. > In school, I learned some divisibility rules. For instance, when > determining if a large number is divisible by 3, add the sum of all the > digits. To see if a large number is divisible by 5, check the last digit > to see if it’s a zero or 5. > > I’ve converted these divisibility rules into binary. For instance, to see > if a large number is divisible by 3, add the sum of all the bytes of the > large number and see if that sum is divisible by 3. > I’ve converted all the divisibility rules for all the primes less than 25 > into binary. All the sums can be calculated at once. > > I wrote a function to do this based on the BIGNUM that openssl uses: > BN_isdivisiblebyprimeslessthan25 > The easiest way to test my function is to generate random numbers and test > the results of BN_isdivisiblebyprimeslessthan25 with another function that > does the division the old way. > > Attached is a paper detailing the math behind the change. > > Here’s the function and where to put it in openssl: > > In file crypto\bn\bn_prime.c, > function BN_is_prime_fasttest_ex > After if (do_trial_division), add > if (BN_isdivisiblebyprimeslessthan25(a)) > return 0; > > bool bn:: BN_isdivisiblebyprimeslessthan25 (const BIGNUM *p) > { > int total3and5and17 = 0; // 256 mod 3 = 1, 256 mod 5 = 1, 256 mod 17 = 1 > int total7 = 0; > int total11 = 0; > int total13 = 0; > int total19 = 0; > int total23 = 0; > > const char sumBytes7[] = { 1, 4, 2}; // 1 mod 7 = 1, 256 mod 7 = 4, > 65536 mod 7 = 2 > const char sumBytes11[] = { 1, 3, 9, 5, 4}; // 1 mod 11 = 1, 256 mod 11 > = 3, 65536 mod 11 = 9 > const char sumBytes13[] = { 1, 9, 3}; // 1 mod 13 = 1, 256 mod 13 = 9, > 65536 mod 13 = 3 > const char sumBytes19[] = { 1, 9, 5, 7, 6, 16, 11, 4, 17}; > const char sumBytes23[] = { 1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8}; > > int index7or13 = 0; // Array indexes for 7 and 13 are the same because > the array is the same size. > int index11 = 0; > int index19 = 0; > int index23 = 0; > int byteLoop; > int top; > BN_ULONG item; > int itemByte; > BN_ULONG *itemptr; > BN_ULONG *lastItem; > > top = p->top; > if (top <= 0) > { > return true; > } > > itemptr = p->d; > lastItem = itemptr+top-1; > while(true) > { > item = *itemptr; > for(byteLoop=0;byteLoop<sizeof(BN_ULONG);byteLoop++) > { > itemByte = (int)(item & 255); > item >>= 8; > total3and5and17 += itemByte; > total7 += (sumBytes7[index7or13] * itemByte); > total13 += (sumBytes13[index7or13] * itemByte); > total11 += (sumBytes11[index11] * itemByte); > total19 += (sumBytes19[index19] * itemByte); > total23 += (sumBytes23[index23] * itemByte); > // Keep the array indexes in bounds. > index7or13 = (index7or13 + 1) % 3; > index11 = (index11 + 1) % 5; > index19 = (index19 + 1) % 9; > index23 = (index23 + 1) % 11; > } > // Move to the next item. > if (itemptr == lastItem) > { > break; > } > itemptr++; > } > bool returnValue = (((total3and5and17 % 3) == 0) > || ((total3and5and17 % 5) == 0) > || ((total7 % 7) == 0) > || ((total11 % 11) == 0) > || ((total13 % 13) == 0) > || ((total3and5and17 % 17) == 0) > || ((total19 % 19) == 0) > || ((total23 % 23) == 0)); > > return returnValue; > } > > Russell Harkins > 650-481-5261 > ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List openssl-dev@openssl.org Automated List Manager majord...@openssl.org