diff options
author | Sebastien Pouliot <sebastien@ximian.com> | 2004-05-07 15:08:26 +0400 |
---|---|---|
committer | Sebastien Pouliot <sebastien@ximian.com> | 2004-05-07 15:08:26 +0400 |
commit | 66c031d6aad77e176e0b40e51558d23aa3db10d1 (patch) | |
tree | f060b09932f84f0992399c5f55f734ed716bf27a /mcs/class/Mono.Security | |
parent | 1b5ee8c867fa91ec7317327d42b1fb1c9d6cb09d (diff) |
2005-05-07 Sebastien Pouliot <sebastien@ximian.com>
* BigInteger.cs: Faster scan of smallPrimes in IsProbablePrime.
Commented the methods OddModTwoPow and EvenModTwoPow as they are broken
in some cases (well tested primes test case).
svn path=/trunk/mcs/; revision=26900
Diffstat (limited to 'mcs/class/Mono.Security')
-rw-r--r-- | mcs/class/Mono.Security/Mono.Math/BigInteger.cs | 48 | ||||
-rw-r--r-- | mcs/class/Mono.Security/Mono.Math/ChangeLog | 6 |
2 files changed, 40 insertions, 14 deletions
diff --git a/mcs/class/Mono.Security/Mono.Math/BigInteger.cs b/mcs/class/Mono.Security/Mono.Math/BigInteger.cs index dddfca39638..adb9705a0f7 100644 --- a/mcs/class/Mono.Security/Mono.Math/BigInteger.cs +++ b/mcs/class/Mono.Security/Mono.Math/BigInteger.cs @@ -834,11 +834,17 @@ namespace Mono.Math { public bool IsProbablePrime () { - for (int p = 0; p < smallPrimes.Length; p++) { - if (this == smallPrimes [p]) - return true; - if (this % smallPrimes [p] == 0) - return false; + if (this < smallPrimes [smallPrimes.Length - 1]) { + for (int p = 0; p < smallPrimes.Length; p++) { + if (this == smallPrimes [p]) + return true; + } + } + else { + for (int p = 0; p < smallPrimes.Length; p++) { + if (this % smallPrimes [p] == 0) + return false; + } } return PrimalityTests.RabinMillerTest (this, Prime.ConfidenceFactor.Medium); } @@ -1095,13 +1101,18 @@ namespace Mono.Math { [CLSCompliant (false)] public BigInteger Pow (uint b, BigInteger exp) { - if (b != 2) { - if ((mod.data [0] & 1) == 1) return OddPow (b, exp); - else return EvenPow (b, exp); +// if (b != 2) { + if ((mod.data [0] & 1) == 1) + return OddPow (b, exp); + else + return EvenPow (b, exp); +/* buggy in some cases (like the well tested primes) } else { - if ((mod.data [0] & 1) == 1) return OddModTwoPow (exp); - else return EvenModTwoPow (exp); - } + if ((mod.data [0] & 1) == 1) + return OddModTwoPow (exp); + else + return EvenModTwoPow (exp); + }*/ } [CLSCompliant (false)] @@ -1165,8 +1176,16 @@ namespace Mono.Math { // We would rather have this estimate overshoot, // so we add one to the divisor - uint divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) / - (mod.data [mod.length-1] + 1)); + uint divEstimate; + if (mod.data [mod.length - 1] < UInt32.MaxValue) { + divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) / + (mod.data [mod.length-1] + 1)); + } + else { + // guess but don't divide by 0 + divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) / + (mod.data [mod.length-1])); + } uint t; @@ -1308,6 +1327,7 @@ namespace Mono.Math { return resultNum; } +/* known to be buggy in some cases private unsafe BigInteger EvenModTwoPow (BigInteger exp) { exp.Normalize (); @@ -1440,7 +1460,7 @@ namespace Mono.Math { resultNum = Montgomery.Reduce (resultNum, mod, mPrime); return resultNum; } - +*/ #endregion } diff --git a/mcs/class/Mono.Security/Mono.Math/ChangeLog b/mcs/class/Mono.Security/Mono.Math/ChangeLog index f3e0836eb61..c2241f882c5 100644 --- a/mcs/class/Mono.Security/Mono.Math/ChangeLog +++ b/mcs/class/Mono.Security/Mono.Math/ChangeLog @@ -1,3 +1,9 @@ +2005-05-07 Sebastien Pouliot <sebastien@ximian.com> + + * BigInteger.cs: Faster scan of smallPrimes in IsProbablePrime. + Commented the methods OddModTwoPow and EvenModTwoPow as they are broken + in some cases (well tested primes test case). + 2004-04-22 Sebastien Pouliot <sebastien@ximian.com> * BigInteger.cs: FxCop-ized. CLS compliance. |