From c27f7a3604a159c7b573c75c5a48bb109b93dc1b Mon Sep 17 00:00:00 2001 From: Peter Dettman Date: Thu, 29 Oct 2015 17:51:47 +0700 Subject: Optimize the number of Rabin-Miller rounds used for probable primality testing --- crypto/src/math/BigInteger.cs | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-) (limited to 'crypto/src/math') diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs index ebeb78788..7c73334de 100644 --- a/crypto/src/math/BigInteger.cs +++ b/crypto/src/math/BigInteger.cs @@ -1408,10 +1408,27 @@ namespace Org.BouncyCastle.Math public bool RabinMillerTest(int certainty, Random random) { + int bits = BitLength; + Debug.Assert(certainty > 0); - Debug.Assert(BitLength > 2); + Debug.Assert(bits > 2); Debug.Assert(TestBit(0)); + int itersFor100Cert = bits >= 1024 ? 4 + : bits >= 512 ? 8 + : bits >= 256 ? 16 + : 50; + + int iterations; + if (certainty < 100) + { + iterations = System.Math.Min(itersFor100Cert, ((certainty - 1) / 2) + 1); + } + else + { + iterations = itersFor100Cert + ((certainty - 100 + 1) / 2); + } + // let n = 1 + d . 2^s BigInteger n = this; int s = n.GetLowestSetBitMaskFirst(-1 << 1); @@ -1449,10 +1466,8 @@ namespace Org.BouncyCastle.Math return false; } } - - certainty -= 2; // composites pass for only 1/4 possible 'a' } - while (certainty > 0); + while (--iterations > 0); return true; } -- cgit 1.4.1