Changeset 1455 for trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs
 Timestamp:
 May 21, 2010, 12:43:20 AM (12 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs
r1454 r1455 197 197 198 198 /* 199 * Returns the modulo inverse of this. Throws ArithmeticException if199 * Returns the modulo inverse of "input". Throws ArithmeticException if 200 200 * the inverse does not exist. (i.e. gcd(this, modulus) != 1) 201 201 * 202 * This method is taken from the BigInteger class of202 * This method is taken from the BigInteger class written by 203 203 * Chew Keong TAN (source: http://www.codeproject.com/KB/cs/biginteger.aspx) 204 204 * (but modified by us) 205 */205 */ 206 206 207 207 public static BigInteger ModInverse(BigInteger input, BigInteger modulus) … … 251 251 } 252 252 253 254 public static bool isProbablePrime(BigInteger p) 255 { 256 return true; //TODO: Implement this!! 257 throw new NotImplementedException(); 258 } 253 #region primesBelow2000 254 // primes smaller than 2000 to test the generated prime number (taken from BigInteger class written by Chew Keong TAN) 255 256 public static readonly int[] primesBelow2000 = { 257 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 258 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 259 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 260 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 261 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 262 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 263 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 264 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 265 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 266 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 267 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 268 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 269 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 270 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 271 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 272 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 273 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 274 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 275 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 276 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 }; 277 278 #endregion 279 280 /* 281 * This code is heavily inspired by the code from the BigInteger class written by Chew Keong TAN 282 */ 283 public static bool isProbablePrime(BigInteger thisVal) 284 { 285 thisVal = BigInteger.Abs(thisVal); 286 287 //test small numbers 288 if (thisVal == 0  thisVal == 1) 289 return false; 290 if (thisVal == 2  thisVal == 3) 291 return true; 292 293 if (thisVal.IsEven) // even numbers 294 return false; 295 296 // test for divisibility by primes < 2000 297 for (int p = 0; p < primesBelow2000.Length; p++) 298 { 299 BigInteger divisor = primesBelow2000[p]; 300 301 if (divisor >= thisVal) 302 break; 303 304 BigInteger resultNum = thisVal % divisor; 305 if (resultNum == 0) 306 return false; 307 } 308 309 // Perform BASE 2 RabinMiller Test 310 311 // calculate values of s and t 312 int s = 0; 313 314 BigInteger t = thisVal  1; 315 while ((t & 0x01) == 0) //TODO: This could be implemented more efficient 316 { 317 t = t >> 1; 318 s++; 319 } 320 321 BigInteger a = 2; 322 323 // b = a^t mod p 324 BigInteger b = BigInteger.ModPow(a, t, thisVal); 325 bool result = false; 326 327 if (b == 1) // a^t mod p = 1 328 result = true; 329 330 BigInteger p_sub1 = thisVal  1; 331 for (int j = 0; result == false && j < s; j++) 332 { 333 if (b == p_sub1) // a^((2^j)*t) mod p = p1 for some 0 <= j <= s1 334 { 335 result = true; 336 break; 337 } 338 339 b = (b * b) % thisVal; 340 } 341 342 /* TODO: Implement this: 343 // if number is strong pseudoprime to base 2, then do a strong lucas test 344 if (result) 345 result = LucasStrongTestHelper(thisVal); 346 */ 347 348 return result; 349 } 350 259 351 } 260 352 }
Note: See TracChangeset
for help on using the changeset viewer.