aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorlloyd <[email protected]>2014-04-10 14:01:17 +0000
committerlloyd <[email protected]>2014-04-10 14:01:17 +0000
commit5dc3912cc5cc11ef48c08c608c5724b25413c861 (patch)
tree0e9d0d14c59402d2383a50246135fc68fb22e38a /src
parentda2efcb6e07677cc8b0860508efb5d07c4f8171d (diff)
Fix a bug in Miller-Rabin primality testing introduced in 1.8.3
where we chose a single random nonce and tested it repeatedly, rather than choosing new nonces each time. Reported by Jeff Marrison. Also remove a pointless comparison (also pointed out by Jeff) and add an initial test using a witness of 2.
Diffstat (limited to 'src')
-rw-r--r--src/lib/math/numbertheory/numthry.cpp11
1 files changed, 6 insertions, 5 deletions
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index e3c673ea5..5946aa994 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -54,10 +54,7 @@ bool MillerRabin_Test::is_witness(const BigInt& a)
return false;
}
- if(y != n_minus_1) // fails Fermat test
- return true;
-
- return false;
+ return true; // fails Fermat test
}
/*
@@ -392,17 +389,21 @@ bool primality_test(const BigInt& n,
MillerRabin_Test mr(n);
+ if(mr.is_witness(2))
+ return false;
+
const size_t tests = miller_rabin_test_iterations(n.bits(), level);
- BigInt nonce;
for(size_t i = 0; i != tests; ++i)
{
+ BigInt nonce;
while(nonce < 2 || nonce >= (n-1))
nonce.randomize(rng, NONCE_BITS);
if(mr.is_witness(nonce))
return false;
}
+
return true;
}