Author: spouliot
Date: 2007-07-03 13:46:35 -0400 (Tue, 03 Jul 2007)
New Revision: 81283
Modified:
trunk/mcs/class/Mono.Security/Mono.Math/BigInteger.cs
trunk/mcs/class/Mono.Security/Mono.Math/ChangeLog
Log:
2007-07-03 Sebastien Pouliot <[EMAIL PROTECTED]>
* BigInteger.cs: Avoid Miller-Rabin test for small primes (we have a
complete list of them) in IsProbablePrime.
Modified: trunk/mcs/class/Mono.Security/Mono.Math/BigInteger.cs
===================================================================
--- trunk/mcs/class/Mono.Security/Mono.Math/BigInteger.cs 2007-07-03
17:31:23 UTC (rev 81282)
+++ trunk/mcs/class/Mono.Security/Mono.Math/BigInteger.cs 2007-07-03
17:46:35 UTC (rev 81283)
@@ -894,18 +894,22 @@
public bool IsProbablePrime ()
{
- if (this <= smallPrimes [smallPrimes.Length - 1]) {
+ // can we use our small-prime table ?
+ if (this <= smallPrimes[smallPrimes.Length - 1]) {
for (int p = 0; p < smallPrimes.Length; p++) {
- if (this == smallPrimes [p])
+ if (this == smallPrimes[p])
return true;
}
+ // the list is complete, so it's not a prime
+ return false;
}
- else {
- for (int p = 0; p < smallPrimes.Length; p++) {
- if (this % smallPrimes [p] == 0)
- return false;
- }
+
+ // otherwise check if we can divide by one of the small
primes
+ for (int p = 0; p < smallPrimes.Length; p++) {
+ if (this % smallPrimes[p] == 0)
+ return false;
}
+ // the last step is to confirm the "large" prime with
the Miller-Rabin test
return PrimalityTests.RabinMillerTest (this,
Prime.ConfidenceFactor.Medium);
}
Modified: trunk/mcs/class/Mono.Security/Mono.Math/ChangeLog
===================================================================
--- trunk/mcs/class/Mono.Security/Mono.Math/ChangeLog 2007-07-03 17:31:23 UTC
(rev 81282)
+++ trunk/mcs/class/Mono.Security/Mono.Math/ChangeLog 2007-07-03 17:46:35 UTC
(rev 81283)
@@ -1,3 +1,8 @@
+2007-07-03 Sebastien Pouliot <[EMAIL PROTECTED]>
+
+ * BigInteger.cs: Avoid Miller-Rabin test for small primes (we have a
+ complete list of them) in IsProbablePrime.
+
2007-07-03 Sebastien Pouliot <[EMAIL PROTECTED]>
* BigInteger.cs: Fix possible IndexOutOfRangeException inside method
_______________________________________________
Mono-patches maillist - [email protected]
http://lists.ximian.com/mailman/listinfo/mono-patches
