diff options
Diffstat (limited to 'crypto/src/math/Primes.cs')
| -rw-r--r-- | crypto/src/math/Primes.cs | 56 |
1 files 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; |