From e170b76401181334ca92ff08a1a1374333eabd7a Mon Sep 17 00:00:00 2001
From: Peter Dettman <peter.dettman@bouncycastle.org>
Date: Fri, 12 Jun 2015 13:05:41 +0700
Subject: Performance optimization

---
 crypto/src/math/Primes.cs | 56 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 42 insertions(+), 14 deletions(-)

diff --git a/crypto/src/math/Primes.cs b/crypto/src/math/Primes.cs
index dda81b988..b57977983 100644
--- a/crypto/src/math/Primes.cs
+++ b/crypto/src/math/Primes.cs
@@ -124,16 +124,21 @@ namespace Org.BouncyCastle.Math
                 x = x.Mod(One.ShiftLeft(length - 1)).SetBit(length - 1);
 
                 BigInteger c0x2 = c0.ShiftLeft(1);
-                BigInteger t = x.Subtract(One).Divide(c0x2).Add(One);
+                BigInteger tx2 = x.Subtract(One).Divide(c0x2).Add(One).ShiftLeft(1);
+                int dt = 0;
 
-                BigInteger c = t.Multiply(c0x2).Add(One);
+                BigInteger c = tx2.Multiply(c0).Add(One);
 
+                /*
+                 * TODO Since the candidate primes are generated by constant steps ('c0x2'),
+                 * sieving could be used here in place of the 'mightBePrime' approach.
+                 */
                 for (;;)
                 {
                     if (c.BitLength > length)
                     {
-                        t = One.ShiftLeft(length - 1).Subtract(One).Divide(c0x2).Add(One);
-                        c = t.Multiply(c0x2).Add(One);
+                        tx2 = One.ShiftLeft(length - 1).Subtract(One).Divide(c0x2).Add(One).ShiftLeft(1);
+                        c = tx2.Multiply(c0).Add(One);
                     }
 
                     ++primeGenCounter;
@@ -149,7 +154,10 @@ namespace Org.BouncyCastle.Math
                         BigInteger a = HashGen(d, primeSeed, iterations + 1);
                         a = a.Mod(c.Subtract(Three)).Add(Two);
 
-                        BigInteger z = a.ModPow(t.ShiftLeft(1), c);
+                        tx2 = tx2.Add(BigInteger.ValueOf(dt));
+                        dt = 0;
+
+                        BigInteger z = a.ModPow(tx2, c);
 
                         if (c.Gcd(z.Subtract(One)).Equals(One) && z.ModPow(c0, c).Equals(One))
                         {
@@ -166,7 +174,7 @@ namespace Org.BouncyCastle.Math
                         throw new InvalidOperationException("Too many iterations in Shawe-Taylor Random_Prime Routine");
                     }
 
-                    t = t.Add(One);
+                    dt += 2;
                     c = c.Add(c0x2);
                 }
             }
@@ -264,16 +272,36 @@ namespace Org.BouncyCastle.Math
             /*
              * Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
              */
-            int m0 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
-            int r0 = x.Mod(BigInteger.ValueOf(m0)).IntValue;
-            if ((r0 & 1) != 0 && (r0 % 3) != 0 && (r0 % 5) != 0 && (r0 % 7) != 0 && (r0 % 11) != 0
-                && (r0 % 13) != 0 && (r0 % 17) != 0 && (r0 % 19) != 0 && (r0 % 23) != 0)
+            int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
+            int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+            if ((r & 1) != 0 && (r % 3) != 0 && (r % 5) != 0 && (r % 7) != 0 && (r % 11) != 0
+                && (r % 13) != 0 && (r % 17) != 0 && (r % 19) != 0 && (r % 23) != 0)
             {
-                int m1 = 29 * 31 * 37 * 41 * 43;
-                int r1 = x.Mod(BigInteger.ValueOf(m1)).IntValue;
-                if ((r1 % 29) != 0 && (r1 % 31) != 0 && (r1 % 37) != 0 && (r1 % 41) != 0 && (r1 % 43) != 0)
+                m = 29 * 31 * 37 * 41 * 43;
+                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                if ((r % 29) != 0 && (r % 31) != 0 && (r % 37) != 0 && (r % 41) != 0 && (r % 43) != 0)
                 {
-                    return true;
+                    m = 47 * 53 * 59 * 61 * 67;
+                    r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                    if ((r % 47) != 0 && (r % 53) != 0 && (r % 59) != 0 && (r % 61) != 0 && (r % 67) != 0)
+                    {
+                        m = 71 * 73 * 79 * 83;
+                        r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                        if ((r % 71) != 0 && (r % 73) != 0 && (r % 79) != 0 && (r % 83) != 0)
+                        {
+                            m = 89 * 97 * 101 * 103;
+                            r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                            if ((r % 89) != 0 && (r % 97) != 0 && (r % 101) != 0 && (r % 103) != 0)
+                            {
+                                m = 107 * 109 * 113 * 127;
+                                r = x.Mod(BigInteger.ValueOf(m)).IntValue;
+                                if ((r % 107) != 0 && (r % 109) != 0 && (r % 113) != 0 && (r % 127) != 0)
+                                {
+                                    return true;
+                                }
+                            }
+                        }
+                    }
                 }
             }
             return false;
-- 
cgit 1.4.1