aboutsummaryrefslogtreecommitdiffstats
path: root/src/math
diff options
context:
space:
mode:
authorlloyd <[email protected]>2009-07-11 15:30:21 +0000
committerlloyd <[email protected]>2009-07-11 15:30:21 +0000
commitb7b1d9a4371d5f4481437f1e21fa0c993938c912 (patch)
tree493bd629207405e5e380a6e58490ad2dd30c4365 /src/math
parent7308b52db7689bb1d393135ca1818f768600e7f9 (diff)
Fix generating primes between 4 and 7 bits. The problem was that when
verify mode is not set, by default the Miller-Rabin bases are chosen from the small primes. Generally speaking these make good test bases. However if the prime to be generated is very small, we will choose a base which is out of range. If the i'th prime is too big to be a base, then just choose a random integer of the appropriate size instead.
Diffstat (limited to 'src/math')
-rw-r--r--src/math/numbertheory/numthry.cpp39
1 files changed, 22 insertions, 17 deletions
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index d634ca88c..721d4a833 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -1,6 +1,6 @@
/*
-* Number Theory
-* (C) 1999-2008 Jack Lloyd
+* Number Theory Functions
+* (C) 1999-2009 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
@@ -56,14 +56,14 @@ u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
{ 0, 0, 0 }
};
- for(u32bit j = 0; tests[j].bits; ++j)
+ for(u32bit i = 0; tests[i].bits; ++i)
{
- if(bits <= tests[j].bits)
+ if(bits <= tests[i].bits)
{
if(verify)
- return tests[j].verify_iter;
+ return tests[i].verify_iter;
else
- return tests[j].check_iter;
+ return tests[i].check_iter;
}
}
return 2;
@@ -154,7 +154,7 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
{
u32bit zero_bits = low_zero_bits(u);
u >>= zero_bits;
- for(u32bit j = 0; j != zero_bits; ++j)
+ for(u32bit i = 0; i != zero_bits; ++i)
{
if(A.is_odd() || B.is_odd())
{ A += y; B -= x; }
@@ -163,7 +163,7 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod)
zero_bits = low_zero_bits(v);
v >>= zero_bits;
- for(u32bit j = 0; j != zero_bits; ++j)
+ for(u32bit i = 0; i != zero_bits; ++i)
{
if(C.is_odd() || D.is_odd())
{ C += y; D -= x; }
@@ -209,17 +209,17 @@ s32bit simple_primality_tests(const BigInt& n)
if(n <= PRIMES[PRIME_TABLE_SIZE-1])
{
const word num = n.word_at(0);
- for(u32bit j = 0; PRIMES[j]; ++j)
+ for(u32bit i = 0; PRIMES[i]; ++i)
{
- if(num == PRIMES[j]) return PRIME;
- if(num < PRIMES[j]) return NOT_PRIME;
+ if(num == PRIMES[i]) return PRIME;
+ if(num < PRIMES[i]) return NOT_PRIME;
}
return NOT_PRIME;
}
u32bit check_first = std::min(n.bits() / 32, PRIME_PRODUCTS_TABLE_SIZE);
- for(u32bit j = 0; j != check_first; ++j)
- if(gcd(n, PRIME_PRODUCTS[j]) != 1)
+ for(u32bit i = 0; i != check_first; ++i)
+ if(gcd(n, PRIME_PRODUCTS[i]) != 1)
return NOT_PRIME;
return UNKNOWN;
@@ -286,10 +286,15 @@ bool passes_mr_tests(RandomNumberGenerator& rng,
u32bit tests = miller_rabin_test_iterations(n.bits(), verify);
BigInt nonce;
- for(u32bit j = 0; j != tests; ++j)
+ for(u32bit i = 0; i != tests; ++i)
{
- if(verify) nonce.randomize(rng, NONCE_BITS);
- else nonce = PRIMES[j];
+ if(!verify && PRIMES[i] < (n-1))
+ nonce = PRIMES[i];
+ else
+ {
+ while(nonce < 2 && nonce >= (n-1))
+ nonce.randomize(rng, NONCE_BITS);
+ }
if(!mr.passes_test(nonce))
return false;
@@ -309,7 +314,7 @@ bool MillerRabin_Test::passes_test(const BigInt& a)
if(y == 1 || y == n_minus_1)
return true;
- for(u32bit j = 1; j != s; ++j)
+ for(u32bit i = 1; i != s; ++i)
{
y = reducer.square(y);