From cc6f46322c01f39c428d36250d8348e777e5440f Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Mon, 14 May 2018 12:09:26 -0400 Subject: Always use 1/2^-128 error bounds with Miller-Rabin Simplifies the code and makes it easy to see we never use the weaker bounds even if the application expicitly requested it. GH #1569 --- src/lib/math/numbertheory/numthry.cpp | 38 +++++++++++++---------------------- 1 file changed, 14 insertions(+), 24 deletions(-) (limited to 'src/lib/math') diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 10f44a1ee..0e0893dd0 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -474,33 +474,23 @@ size_t mr_test_iterations(size_t n_bits, size_t prob, bool random) * These values are derived from the inequality for p(k,t) given on * the second page. */ - if(random) + if(prob <= 128) { - if(prob <= 80) - { - if(n_bits >= 1536) - return 2; // < 2^-89 - if(n_bits >= 1024) - return 3; // < 2^-89 - if(n_bits >= 512) - return 5; // < 2^-80 - if(n_bits >= 256) - return 11; // < 2^-80 - } - - if(prob <= 128) - { - if(n_bits >= 1536) - return 4; // < 2^-133 - if(n_bits >= 1024) - return 6; // < 2^-133 - if(n_bits >= 512) - return 12; // < 2^-129 - if(n_bits >= 256) - return 28; // < 2^-128 - } + if(n_bits >= 1536) + return 4; // < 2^-133 + if(n_bits >= 1024) + return 6; // < 2^-133 + if(n_bits >= 512) + return 12; // < 2^-129 + if(n_bits >= 256) + return 28; // < 2^-128 } + /* + If the user desires a smaller error probability than we have + precomputed error estimates for, just fall back to using the worst + case error rate. + */ return base; } -- cgit v1.2.3