A number of changes to primality tests:

Use 64 bit nonces in the Miller-Rabin test, instead of 40 bits.

Rename check_prime to quick_check_prime and is_prime to check_prime

Remove some internal functions which weren't used outside the
primality test code, along with the prime products table.

For quick checking, instead of doing Miller-Rabin with fixed base 2,
do a small number of randomized tests.

Always use random bases instead of the first n primes.

5 files changed, 45 insertions, 167 deletions

diff --git a/src/math/numbertheory/dsa_gen.cpp b/src/math/numbertheory/dsa_gen.cpp
index 83646e50e..535c22976 100644
--- a/src/math/numbertheory/dsa_gen.cpp
+++ b/src/math/numbertheory/dsa_gen.cpp
@@ -83,7 +83,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
    q.set_bit(qbits-1);
    q.set_bit(0);
 
-   if(!is_prime(q, rng))
+   if(!check_prime(q, rng))
       return false;
 
    const u32bit n = (pbits-1) / (HASH_SIZE * 8),
@@ -107,7 +107,7 @@ bool generate_dsa_primes(RandomNumberGenerator& rng,
 
       p = X - (X % (2*q) - 1);
 
-      if(p.bits() == pbits && is_prime(p, rng))
+      if(p.bits() == pbits && check_prime(p, rng))
          return true;
       }
    return false;
diff --git a/src/math/numbertheory/make_prm.cpp b/src/math/numbertheory/make_prm.cpp
index 61d42634a..59a5c2635 100644
--- a/src/math/numbertheory/make_prm.cpp
+++ b/src/math/numbertheory/make_prm.cpp
@@ -75,7 +75,7 @@ BigInt random_prime(RandomNumberGenerator& rng,
 
          if(!passes_sieve || gcd(p - 1, coprime) != 1)
             continue;
-         if(passes_mr_tests(rng, p))
+         if(check_prime(p, rng))
             return p;
          }
       }
@@ -93,7 +93,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, u32bit bits)
    BigInt p;
    do
       p = (random_prime(rng, bits - 1) << 1) + 1;
-   while(!is_prime(p, rng));
+   while(!check_prime(p, rng));
    return p;
    }
 
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index e4c52323e..010a523ff 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -73,7 +73,7 @@ MillerRabin_Test::MillerRabin_Test(const BigInt& num)
 /*
 * Miller-Rabin Iterations
 */
-u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
+u32bit miller_rabin_test_iterations(u32bit bits, u32bit level)
    {
    struct mapping { u32bit bits; u32bit verify_iter; u32bit check_iter; };
 
@@ -117,13 +117,16 @@ u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
       {
       if(bits <= tests[i].bits)
          {
-         if(verify)
+         if(level >= 2)
             return tests[i].verify_iter;
-         else
+         else if(level == 1)
             return tests[i].check_iter;
+         else if(level == 0)
+            return std::max<u32bit>(tests[i].check_iter / 4, 1);
          }
       }
-   return 2;
+
+   return level > 0 ? 2 : 1; // for large inputs
    }
 
 }
@@ -250,106 +253,49 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod)
    }
 
 /*
-* Do simple tests of primality
+* Test for primaility using Miller-Rabin
 */
-s32bit simple_primality_tests(const BigInt& n)
+bool primality_test(const BigInt& n,
+                    RandomNumberGenerator& rng,
+                    u32bit level)
    {
-   const s32bit NOT_PRIME = -1, UNKNOWN = 0, PRIME = 1;
+   const u32bit PREF_NONCE_BITS = 64;
 
    if(n == 2)
-      return PRIME;
+      return true;
    if(n <= 1 || n.is_even())
-      return NOT_PRIME;
+      return false;
 
+   // Fast path testing for small numbers (<= 65521)
    if(n <= PRIMES[PRIME_TABLE_SIZE-1])
       {
       const word num = n.word_at(0);
+
       for(u32bit i = 0; PRIMES[i]; ++i)
          {
-         if(num == PRIMES[i]) return PRIME;
-         if(num <  PRIMES[i]) return NOT_PRIME;
+         if(num == PRIMES[i])
+            return true;
+         if(num < PRIMES[i])
+            return false;
          }
-      return NOT_PRIME;
-      }
-
-   u32bit check_first = std::min(n.bits() / 32, PRIME_PRODUCTS_TABLE_SIZE);
-   for(u32bit i = 0; i != check_first; ++i)
-      if(gcd(n, PRIME_PRODUCTS[i]) != 1)
-         return NOT_PRIME;
-
-   return UNKNOWN;
-   }
 
-/*
-* Fast check of primality
-*/
-bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
-   {
-   return run_primality_tests(rng, n, 0);
-   }
-
-/*
-* Test for primality
-*/
-bool is_prime(const BigInt& n, RandomNumberGenerator& rng)
-   {
-   return run_primality_tests(rng, n, 1);
-   }
-
-/*
-* Verify primality
-*/
-bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
-   {
-   return run_primality_tests(rng, n, 2);
-   }
-
-/*
-* Verify primality
-*/
-bool run_primality_tests(RandomNumberGenerator& rng,
-                         const BigInt& n, u32bit level)
-   {
-   s32bit simple_tests = simple_primality_tests(n);
-   if(simple_tests) return (simple_tests == 1) ? true : false;
-   return passes_mr_tests(rng, n, level);
-   }
-
-/*
-* Test for primaility using Miller-Rabin
-*/
-bool passes_mr_tests(RandomNumberGenerator& rng,
-                     const BigInt& n, u32bit level)
-   {
-   const u32bit PREF_NONCE_BITS = 40;
+      return false;
+      }
 
    if(level > 2)
       level = 2;
 
-   MillerRabin_Test mr(n);
-
-   if(!mr.passes_test(2))
-      return false;
+   const u32bit NONCE_BITS = std::min(n.bits() - 2, PREF_NONCE_BITS);
 
-   if(level == 0)
-      return true;
-
-   const u32bit NONCE_BITS = std::min(n.bits() - 1, PREF_NONCE_BITS);
-
-   const bool verify = (level == 2);
+   MillerRabin_Test mr(n);
 
-   u32bit tests = miller_rabin_test_iterations(n.bits(), verify);
+   const u32bit tests = miller_rabin_test_iterations(n.bits(), level);
 
    BigInt nonce;
    for(u32bit i = 0; i != tests; ++i)
       {
-      if(!verify && PRIMES[i] < (n-1))
-         nonce = PRIMES[i];
-      else
-         {
-         while(nonce < 2 || nonce >= (n-1))
-            nonce.randomize(rng, NONCE_BITS);
-         }
+      while(nonce < 2 || nonce >= (n-1))
+         nonce.randomize(rng, NONCE_BITS);
 
       if(!mr.passes_test(nonce))
          return false;
diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h
index 080f184a4..2d889a68a 100644
--- a/src/math/numbertheory/numthry.h
+++ b/src/math/numbertheory/numthry.h
@@ -27,8 +27,8 @@ inline BigInt abs(const BigInt& n) { return n.abs(); }
 
 void BOTAN_DLL divide(const BigInt&, const BigInt&, BigInt&, BigInt&);
 
-BigInt BOTAN_DLL gcd(const BigInt&, const BigInt&);
-BigInt BOTAN_DLL lcm(const BigInt&, const BigInt&);
+BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y);
+BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y);
 
 BigInt BOTAN_DLL square(const BigInt&);
 BigInt BOTAN_DLL inverse_mod(const BigInt&, const BigInt&);
@@ -50,27 +50,28 @@ u32bit BOTAN_DLL low_zero_bits(const BigInt&);
 /*
 * Primality Testing
 */
-bool BOTAN_DLL check_prime(const BigInt&, RandomNumberGenerator&);
-bool BOTAN_DLL is_prime(const BigInt&, RandomNumberGenerator&);
-bool BOTAN_DLL verify_prime(const BigInt&, RandomNumberGenerator&);
+bool BOTAN_DLL primality_test(const BigInt& n,
+                              RandomNumberGenerator& rng,
+                              u32bit level = 1);
 
-s32bit BOTAN_DLL simple_primality_tests(const BigInt&);
+inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return primality_test(n, rng, 0); }
 
-bool BOTAN_DLL passes_mr_tests(RandomNumberGenerator&,
-                               const BigInt&, u32bit = 1);
+inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return primality_test(n, rng, 1); }
 
-bool BOTAN_DLL run_primality_tests(RandomNumberGenerator&,
-                                   const BigInt&, u32bit = 1);
+inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+   { return primality_test(n, rng, 2); }
 
 /*
 * Random Number Generation
 */
-BigInt BOTAN_DLL random_prime(RandomNumberGenerator&,
+BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
                               u32bit bits, const BigInt& coprime = 1,
                               u32bit equiv = 1, u32bit equiv_mod = 2);
 
-BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator&,
-                                   u32bit);
+BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
+                                   u32bit bits);
 
 /*
 * DSA Parameter Generation
@@ -94,10 +95,8 @@ generate_dsa_primes(RandomNumberGenerator& rng,
 * Prime Numbers
 */
 const u32bit PRIME_TABLE_SIZE = 6541;
-const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256;
 
 extern const u16bit BOTAN_DLL PRIMES[];
-extern const u64bit PRIME_PRODUCTS[];
 
 }
 
diff --git a/src/math/numbertheory/primes.cpp b/src/math/numbertheory/primes.cpp
index 26ff098a5..a0c0f0093 100644
--- a/src/math/numbertheory/primes.cpp
+++ b/src/math/numbertheory/primes.cpp
@@ -606,71 +606,4 @@ const u16bit PRIMES[PRIME_TABLE_SIZE+1] = {
 65323, 65327, 65353, 65357, 65371, 65381, 65393, 65407, 65413, 65419, 65423,
 65437, 65447, 65449, 65479, 65497, 65519, 65521, 0 };
 
-const u64bit PRIME_PRODUCTS[PRIME_PRODUCTS_TABLE_SIZE] = {
-0xFF658BDE2F2A43DF, 0xFEEB94CD535119ED, 0xFA921839EC24DDD5, 0xFDDA766C77E1E605,
-0xFF3024B0EB4EE333, 0xFEEE350BBC92F4DF, 0xFFC724B7D011D01B, 0xFEED34B826C33B05,
-0xFE69D8DE3F85C6E3, 0xFE3B48909250918F, 0xFF8EC0CE9C632429, 0xFFD92A5C78226D6B,
-0xFFB4BFB0C65133CF, 0xFE77113704902C57, 0xFF8A21D222EA81FD, 0xFEDA1299661CF5AB,
-0xFF4CE86187737D0D, 0xFFD26443A07F519D, 0xFFA817B7191D7967, 0xFF00EDC142868873,
-0xFFB9C6D7F7A239B7, 0xFFE76D3481E98E39, 0xFF76D5432584120D, 0xFFAA499F071EC705,
-0xFEB5198F05722E59, 0xFF7E0431CA41107F, 0xFFCFD52FEDDC928F, 0xFE0EA42537BC6ABF,
-0xFF64937896876925, 0xFC6FC87E811607D3, 0xFFBF600E6CDD0F4F, 0xFF022700FE658243,
-0xFF2E21166779D6B9, 0xFFC224624C665C33, 0xFF1372F41FF177AD, 0xFF31E57E972D0C13,
-0xFFA891F866404D23, 0xFF7BF13EF716E9A3, 0xFE51CAFD9466E733, 0xFDA1CF55F6D6336F,
-0xFFAF6C040ED0950F, 0xFFAA1725F40BA269, 0xFEC593BC3570BEEB, 0xFEE05B35B426F413,
-0xFFCA5209A08890F9, 0xFFED8AF70EB0CC89, 0xFF3F98E3E27860A5, 0xFF92FECD017FF9F7,
-0xFEFA655B2609018F, 0xFFFC51D15AAC7B77, 0xFEF5007E71420DB1, 0xFFEC4784141332D1,
-0xFE8384ED4E1D21CD, 0xFFD3FF614D3ECC47, 0xFFDE5166FD540313, 0xFF5320ECED04B26F,
-0xFF223980F122FF75, 0xFF19C1F27CB1B4A5, 0xFF0F1DFC9DA9523B, 0xFF82DE7B387F5427,
-0xFF9A026BA87314E3, 0xFFAC7FF3ACE64E77, 0xFF808EB2FD5873C3, 0xFE983ED5BB363301,
-0xFF714856DB2CFE95, 0xFF84E1510CF3EB9F, 0xFF29D04C1DA0B115, 0xFFBCF3BF9433552F,
-0xFF32203D58A4C473, 0xFFF00910A15021C3, 0xFDE93041F28240AD, 0xFFC518BCD81C03C5,
-0xFEF504CD8BB9CBDD, 0xFEB8FFBFFF116A6B, 0xFF7642E0785ADA23, 0xFFECF068800FD50D,
-0xFFD703577CA247A7, 0xFF54C0ECAD2C9691, 0xFFC031706B8C72F5, 0xFFE59E5CA58BBDF5,
-0xFFF31FAFFD3B331D, 0xFF64DDF32349FF6D, 0xFFE38309D0BD4A51, 0xFF8C934F76B3C737,
-0xFFDC80B4BAEAFC1F, 0xFFCC1FE4C856FBD9, 0xFFDB5976DDF601FD, 0xFFD3DD25F424433D,
-0xFFC00FA367E746C7, 0xFFE08BF011CC854F, 0xFFC3F21982468F6D, 0xFFDA6C52478A76DF,
-0xFFC67D95AADED363, 0xFFD605D18C3AFC65, 0xFFE828C9D698F1DF, 0xFFBE5098D83B7737,
-0xFF79EB34474ABFB9, 0xFFD27AEED0786363, 0xFFD0FE27B77C271F, 0xFFFBB6563BD065EF,
-0xFFF3638F8635E1EB, 0xFFBE862C22C9F065, 0xFF44712D8488A01D, 0xFF7EEC97F9913111,
-0xFFC23CC78CB12AB1, 0xFFF390FE85F81D3D, 0xFFE8EA21A0FB9931, 0xFFB9D42D17A93385,
-0xFFCDB63AB21E904D, 0xFF5EB7F2210D33DF, 0xFFE6F6C7BB60C9DF, 0xFFAD4CA8DC26D699,
-0xFF7BE75BD21DCA51, 0xFEF89CE23CB61789, 0xFF40ECA3CCA22CE5, 0xF52BDF080F7ABA6F,
-0xEC8F38C8B28E0493, 0xE68E732A2ABED62F, 0xE21A13779E0CCDC7, 0xD823C075C325191B,
-0xD1B284C91EED248B, 0xCBA5A08068E8C1F7, 0xC483EE5A2228985D, 0xBCAEE9F787AC75EB,
-0xB782DAB1B77D3E09, 0xB0D77226F15E387B, 0xAA2A8727D47941CD, 0xA4A45682E9CE533D,
-0x9CAF15AF4CE7FCF7, 0x94C051DD15537305, 0x9006D2FBD933A297, 0x8C4DED05F19B7399,
-0x884FD7A270AD1B1B, 0x83C687D33F238D4B, 0xFF62E2BAE50C6C16, 0x7A59E1FD9D203DBB,
-0x764F1DC07B0E442D, 0x72732FE1F2023153, 0x6E373B550764872F, 0x680FFFD267C5F3FF,
-0x6206BFEC14F1CFC5, 0x5FA6F70CFD587265, 0x5CC7A1B4F6DF9823, 0x599291B29311407F,
-0xFF3CEBD359B67EF9, 0x51C573C14F289F6D, 0x4FA265B31B73C6DF, 0x4B3154ACBD077DED,
-0x4785C96B29A1E437, 0x451F887F646CF763, 0x429DC254C5490571, 0x408410840EAE2883,
-0x3E12CC83606624F3, 0x3A70D774B821DA71, 0x37A21449A196A825, 0x34C5D056E2278B81,
-0xFA0C6CAB29D8E297, 0x2FA5AEC982A5972B, 0x2D6831749426068F, 0x2B7F876418155CA7,
-0x2A1B897ED2AB433D, 0x28C9430D0F92132F, 0x26DF879EBF12E103, 0xFD2FAB4CA364D43B,
-0x22B5B4FC40D4C35F, 0x209298AA84D7E6A1, 0x1ED4B9F11445F1E7, 0x1DC6D2DD416CC91D,
-0x1C1517A52E37C3EF, 0x1A808916125AEF2F, 0x197A2FB2938FF13D, 0x1814AA6C087B561D,
-0xFB3B173E72947609, 0x1571187A8E3D4D6B, 0x13D306D29263C139, 0xF8AEC6ADA137E865,
-0x123EA204BAB48731, 0x11012099D202F297, 0x10290E15797C21BD, 0x0F3AB38E679D6317,
-0xF50B5505D593FCF9, 0xFF23754F7F2052B5, 0x0CC52D96BC2E5A2D, 0x0BF80EAD87B228E5,
-0x0B59A623082C9171, 0xF44E28B9221A433B, 0x09DB5CDD2505EABD, 0x09638C123BCAB351,
-0xFDB9AE6935254CD3, 0xFFE30D7E4F02F163, 0x07CF1FC053B9C61F, 0x0789244FF1705821,
-0x06FBD05649B0B9C7, 0xEF9713EC6A0C250B, 0xF47691AD6AA9F0DB, 0xF2A8EB02CB08CA51,
-0xF9559D40380A20E1, 0x04E15138A5B9BF43, 0xEECD739EA48F3ABB, 0xF76E7E7530574E79,
-0xF8393D2E42D7D277, 0xF666F9AD3A16D173, 0xF403C629749F3ED5, 0xFBD7EC45F220A473,
-0xFA8AFF7491B234FD, 0xFF471CE534D1F537, 0xF4BEBFDD9C54CEC9, 0xDD04722310A6CE9D,
-0xFD8071236214FA05, 0xFBCA07B399A482DD, 0xFD9642C104864C17, 0xFA525105AADEFA39,
-0xF71122156406E645, 0xFF415FDFD1247539, 0xFB709936F52446AF, 0xFF7734CCB806CDA7,
-0xF801E9A88CD3D70D, 0xFC0C00AC9BCC5491, 0xFF462CD8E52ED221, 0xFC97426300FCE331,
-0xFEB3049C5E37A059, 0xFFFC8AB1E05051CD, 0xFE5F4621F2D9FE63, 0xFE931DB54FC5D521,
-0xFFDE43D960FE42A5, 0xFFDBFAD1B802BDB5, 0xFF23C485F6B7BF53, 0xFFC98F169C8DF21B,
-0xF1609D0E2E564D01, 0xCB10B976C333834B, 0x9B52037A38DAB8F9, 0x800E88FF5E929095,
-0x55A9AD1C21F5E173, 0x3D1A64E4E555D699, 0x2A5D1D73694F7B93, 0x198F4260D8807623,
-0x140D45BB525C35EB, 0x102F4743FF914EEB, 0x0CB114936A734FBF, 0x096D97150B7B0A71,
-0x06F06B90B850C2E5, 0x053B17A0D7F7386B, 0xE3AD1CE3C82FE6A5, 0xDAE968B4B710E857,
-0xFA2DC15B2C96BE77, 0xF1FF5F22AF135BD9, 0xFC65C5CAAA878A13, 0xFB9427EB08CF9C11,
-0xCCB12B6FEBFE285D, 0x5BAADA462B48F999, 0x2E53167EC64B703B, 0x1264ED670CD61961,
-0x071F216A9AB74E2D, 0xEE26503C1266CE55, 0x4C6004C7E404E4B5, 0xCB649E41ECE95F85
-};
-
 }