Optimize the number of Rabin-Miller rounds used for probable primality testing

1 files changed, 19 insertions, 4 deletions

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;
         }