diff options
Diffstat (limited to 'src/DotNetOpenAuth.OpenId/OpenId/DiffieHellman/mono/PrimalityTests.cs')
| -rw-r--r-- | src/DotNetOpenAuth.OpenId/OpenId/DiffieHellman/mono/PrimalityTests.cs | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/src/DotNetOpenAuth.OpenId/OpenId/DiffieHellman/mono/PrimalityTests.cs b/src/DotNetOpenAuth.OpenId/OpenId/DiffieHellman/mono/PrimalityTests.cs new file mode 100644 index 0000000..b2ddc74 --- /dev/null +++ b/src/DotNetOpenAuth.OpenId/OpenId/DiffieHellman/mono/PrimalityTests.cs @@ -0,0 +1,177 @@ +// <auto-generated /> +// +// Mono.Math.Prime.PrimalityTests.cs - Test for primality +// +// Authors: +// Ben Maurer +// +// Copyright (c) 2003 Ben Maurer. All rights reserved +// + +using System; +using System.Security.Cryptography; + +namespace Mono.Math.Prime { + + //[CLSCompliant(false)] + internal delegate bool PrimalityTest (BigInteger bi, ConfidenceFactor confidence); + + //[CLSCompliant(false)] + internal sealed class PrimalityTests { + + #region SPP Test + + private static int GetSPPRounds (BigInteger bi, ConfidenceFactor confidence) + { + int bc = bi.bitCount(); + + int Rounds; + + // Data from HAC, 4.49 + if (bc <= 100 ) Rounds = 27; + else if (bc <= 150 ) Rounds = 18; + else if (bc <= 200 ) Rounds = 15; + else if (bc <= 250 ) Rounds = 12; + else if (bc <= 300 ) Rounds = 9; + else if (bc <= 350 ) Rounds = 8; + else if (bc <= 400 ) Rounds = 7; + else if (bc <= 500 ) Rounds = 6; + else if (bc <= 600 ) Rounds = 5; + else if (bc <= 800 ) Rounds = 4; + else if (bc <= 1250) Rounds = 3; + else Rounds = 2; + + switch (confidence) { + case ConfidenceFactor.ExtraLow: + Rounds >>= 2; + return Rounds != 0 ? Rounds : 1; + case ConfidenceFactor.Low: + Rounds >>= 1; + return Rounds != 0 ? Rounds : 1; + case ConfidenceFactor.Medium: + return Rounds; + case ConfidenceFactor.High: + return Rounds <<= 1; + case ConfidenceFactor.ExtraHigh: + return Rounds <<= 2; + case ConfidenceFactor.Provable: + throw new Exception ("The Rabin-Miller test can not be executed in a way such that its results are provable"); + default: + throw new ArgumentOutOfRangeException ("confidence"); + } + } + + /// <summary> + /// Probabilistic prime test based on Rabin-Miller's test + /// </summary> + /// <param name="bi" type="BigInteger.BigInteger"> + /// <para> + /// The number to test. + /// </para> + /// </param> + /// <param name="confidence" type="int"> + /// <para> + /// The number of chosen bases. The test has at least a + /// 1/4^confidence chance of falsely returning True. + /// </para> + /// </param> + /// <returns> + /// <para> + /// True if "this" is a strong pseudoprime to randomly chosen bases. + /// </para> + /// <para> + /// False if "this" is definitely NOT prime. + /// </para> + /// </returns> + public static bool RabinMillerTest (BigInteger bi, ConfidenceFactor confidence) + { + int Rounds = GetSPPRounds (bi, confidence); + + // calculate values of s and t + BigInteger p_sub1 = bi - 1; + int s = p_sub1.LowestSetBit (); + + BigInteger t = p_sub1 >> s; + + int bits = bi.bitCount (); + BigInteger a = null; + RandomNumberGenerator rng = RandomNumberGenerator.Create (); + BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi); + + for (int round = 0; round < Rounds; round++) { + while (true) { // generate a < n + a = BigInteger.genRandom (bits, rng); + + // make sure "a" is not 0 + if (a > 1 && a < bi) + break; + } + + if (a.gcd (bi) != 1) return false; + + BigInteger b = mr.Pow (a, t); + + if (b == 1) continue; // a^t mod p = 1 + + bool result = false; + for (int j = 0; j < s; j++) { + + if (b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1 + result = true; + break; + } + + b = (b * b) % bi; + } + + if (result == false) + return false; + } + return true; + } + + public static bool SmallPrimeSppTest (BigInteger bi, ConfidenceFactor confidence) + { + int Rounds = GetSPPRounds (bi, confidence); + + // calculate values of s and t + BigInteger p_sub1 = bi - 1; + int s = p_sub1.LowestSetBit (); + + BigInteger t = p_sub1 >> s; + + + BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi); + + for (int round = 0; round < Rounds; round++) { + + BigInteger b = mr.Pow (BigInteger.smallPrimes [round], t); + + if (b == 1) continue; // a^t mod p = 1 + + bool result = false; + for (int j = 0; j < s; j++) { + + if (b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1 + result = true; + break; + } + + b = (b * b) % bi; + } + + if (result == false) + return false; + } + return true; + + } + + #endregion + + + // TODO: Implement the Lucus test + // TODO: Implement other new primality tests + // TODO: Implement primality proving + } +} |