[Mono-bugs] [Bug 81857][Nor] Changed - BigInteger reduction can fail on small values

[bugzilla-daemon at bugzilla.ximian.com]

Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.

Changed by sebastien at ximian.com.

http://bugzilla.ximian.com/show_bug.cgi?id=81857

--- shadow/81857	2007-07-05 07:45:40.000000000 -0400
+++ shadow/81857.tmp.1207	2007-07-05 11:09:04.000000000 -0400
@@ -10,13 +10,13 @@
 Component: Mono.Security
 AssignedTo: sebastien at ximian.com                            
 ReportedBy: atsushi at ximian.com               
 QAContact: mono-bugs at ximian.com
 TargetMilestone: ---
 URL: 
-Summary: BigInteger.IsProbablePrime() fails on some primes
+Summary: BigInteger reduction can fail on small values
 
 Kazuki found some BigInteger issues:
 1) new BigInteger (5987).IsProbablePrime() returns false.
 2) new BigInteger (65537).IsProbablePrime() causes IndexOutOfRangeException.
   http://primes.utm.edu/lists/small/10000.txt
 3) new BigInteger (5915587277).IsProbablePrime() returns false
@@ -121,6 +121,29 @@
 a random number matching MR criteria.
 
 This isn't something that's likely to occurs when testing random
 primes on very large numbers - which is the point of the code. But
 it's likely that I'll remove/comment/disable this case from the unit
 tests.
+
+------- Additional Comments From sebastien at ximian.com  2007-07-05 11:09 -------
+Added a workaround for small primes (SVN r81393-5) where we avoid
+using the base == 2 optimization. This "fixes" the IsProbablePrime issue.
+
+I'm keeping this issue open (but renamed) because the root cause isn't
+fixed. There's a unit test (commented) that shows the problem.
+
+		[Test]
+		public void Bug81857 ()
+		{
+			BigInteger b = BigInteger.Parse ("18446744073709551616");
+			BigInteger exp = new BigInteger (2);
+			BigInteger mod = BigInteger.Parse ("48112959837082048697");
+			BigInteger expected = BigInteger.Parse ("4970597831480284165");
+
+			BigInteger manual = b * b % mod;
+			Assert.AreEqual (expected, manual, "b * b % mod");
+// fails (inside Barrett reduction)
+//			BigInteger actual = b.ModPow (exp, mod);
+//			Assert.AreEqual (expected, actual, "b.ModPow (exp, mod)");
+		}
+