[pgsqlclient-checkins] pgsqlclient_10/Mono.Security/Mono.Security/Mono.Math.Prime PrimalityTests.cs,1.2,1.3

[Carlos G. Á. <car...@us...>]

Update of /cvsroot/pgsqlclient/pgsqlclient_10/Mono.Security/Mono.Security/Mono.Math.Prime
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1264

Modified Files:
	PrimalityTests.cs 
Log Message:
Updated Mono.Security sources to mono Beta 2

Index: PrimalityTests.cs
===================================================================
RCS file: /cvsroot/pgsqlclient/pgsqlclient_10/Mono.Security/Mono.Security/Mono.Math.Prime/PrimalityTests.cs,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** PrimalityTests.cs	9 May 2004 11:59:12 -0000	1.2
--- PrimalityTests.cs	12 Jun 2004 09:27:51 -0000	1.3
***************
*** 62,68 ****
  					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");
--- 62,68 ----
  					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");
***************
*** 107,125 ****
  			BigInteger a = null;
  			BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi);
  
! 			for (int round = 0; round < Rounds; round++) {
  				while (true) {		           // generate a < n
  					a = BigInteger.GenerateRandom (bits);
  
! 					// 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;
--- 107,145 ----
  			BigInteger a = null;
  			BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi);
+ 			
+ 			// Applying optimization from HAC section 4.50 (base == 2)
+ 			// not a really random base but an interesting (and speedy) one
+ 			BigInteger b = mr.Pow (2, t);
+ 			if (b != 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)
! 					return false;
! 			}
! 
! 			// still here ? start at round 1 (round 0 was a == 2)
! 			for (int round = 1; round < Rounds; round++) {
  				while (true) {		           // generate a < n
  					a = BigInteger.GenerateRandom (bits);
  
! 					// make sure "a" is not 0 (and not 2 as we have already tested that)
! 					if (a > 2 && a < bi)
  						break;
  				}
  
! 				if (a.GCD (bi) != 1)
! 					return false;
  
! 				b = mr.Pow (a, t);
  
! 				if (b == 1)
! 					continue;              // a^t mod p = 1
  
  				bool result = false;
***************
*** 134,138 ****
  				}
  
! 				if (result == false)
  					return false;
  			}
--- 154,158 ----
  				}
  
! 				if (!result)
  					return false;
  			}
***************
*** 174,178 ****
  			}
  			return true;
- 
  		}
  
--- 194,197 ----