Changeset 1455


Ignore:
Timestamp:
May 21, 2010, 12:43:20 AM (12 years ago)
Author:
Sven Rech
Message:

some additional BigIntegerHelper stuff (added probable prime test)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs

    r1454 r1455  
    197197
    198198        /*
    199          * Returns the modulo inverse of this.  Throws ArithmeticException if
     199         * Returns the modulo inverse of "input".  Throws ArithmeticException if
    200200         * the inverse does not exist.  (i.e. gcd(this, modulus) != 1)
    201201         *
    202          * This method is taken from the BigInteger class of
     202         * This method is taken from the BigInteger class written by
    203203         * Chew Keong TAN (source: http://www.codeproject.com/KB/cs/biginteger.aspx)
    204204         * (but modified by us)
    205         */
     205         */
    206206
    207207        public static BigInteger ModInverse(BigInteger input, BigInteger modulus)
     
    251251        }
    252252
    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 Rabin-Miller 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 = p-1 for some 0 <= j <= s-1
     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
    259351    }
    260352}
Note: See TracChangeset for help on using the changeset viewer.