Aug 15, 2010

With the release of .NET Framework 4, developers have access to arbitrary precision integer mathematics through the BigInteger structure in the System.Numerics namespace. With exponentiation/modulus functions, it is fairly easy to implement number theory computations requiring very large integer mathematics. The most common algorithm to test for probabilistic primality of a number is the Rabin-Miller method (Ref. 1, 2). This algorithm can indicate with certainty if a number is not prime but can only indicate the highly-probable prime status of a number with the level of certainty dependent on the number of iterations used with the algorithm. The algorithm does not provide information on the prime factorization of a number found to be composite.

rabinmiller [numberfile | numberstring] [Rabin-Miller iterations] [simple mode]After initial startup, the application loops and prompts the user for more numbers to test. The Rabin-Miller iterations and mode status are fixed at the initial startup values.

(1) If the first argument (numberfile) is a file name (with correct path specification), the application attempts to parse the file as a decimal integer text file. There can be artibrary spaces and CR/LF sequences in the file which are removed on parsing to an integer value. Any non-numeric characters cause the parsing to fail. If a file with the specified name isn't found, the number is assumed to be specified directly by the argument. In this case the argument can be parsed as a decimal integer value. The first argument also supports specifying common numeric expressions in which case the first character of the argument (M, N, R or Q) indicates the expression type with the remaining numbers indicating the exponent value which must be an int32 value <= 2,147,483,647. For example, the expression forms for an exponent of 127 are:

M127 --> 2^{127}- 1 (A Mersenne number) N127 --> 2^{127}+ 1 R127 --> (10^{127}- 1)/9 (A Repunit number) Q127 --> 10^{127}+ 1

If the first argument numberstring is "+", "*" or "/", the application prompts for several numbers to add, multiply or divide respectively.

The first argument numberstring also allows specification of a polynomial expression, using "Pm" and further prompting, with up to 3 different powers and a constant:

a0 + a1*b1In this case, a0, a1, a2, a3, b1, b2, b3 can be arbitrarily large numbers. The exponents e1, e2 and e2 must be int32 <= 2,147,483,647. The values a0, a1, a2, a3 can be negative values. In all cases, the resultant number to be factored must be a positive number greater than one.^{e1}+ a2*b2^{e2}+ a3*b3^{e3}

(2) The second optional argument is the number of Rabin-Miller iterations which defaults to 64 which provides a certainty for primality of

(3) If three arguments are specified, the final argument simply disables the verbose display so that large prime numbers are not displayed, and the detailed Rabin-Miller iterations are not shown, but the same test is performed and status of the test is displayed.

Before the Rabin-Miller algorithm is executed, the application uses a list of smaller primes for a simple initial factoring check. If the binary file

The application displays (in default verbose mode) the entire number in both decimal (base 10) and hex (base 16) and also indicates the number of bits, bytes and decimal digits in the number to be tested which can be useful. The progress of the iterations is shown and a final result of either composite certainty or highly probably primality is reported.

Download rabinmiller.zip (915,625 bytes)

(The zip archive contains

C:\........>rabinmiller 12345678901234567890123456789 n: 12345678901234567890123456789 0x27E41B3246BEC9B16E398115 n has 12 bytes (96 bits) or 29 decimal digits Using small primes file "binprimes" with 664579 primes up to 9999991 Testing n for composite with small primes ... n is composite with COMPLETE factorization: 3 x 3 x 3 x 7 x 13 x 31 x 37 x 211 x 241 x 2161 x 3607 x 3803 x 2906161 Verified the composite product. -------------------------------------------------------------------------- C:\.........>rabinmiller M99 M99 = 2^99 - 1 : 633825300114114700748351602687 0x7FFFFFFFFFFFFFFFFFFFFFFFF n has 13 bytes (104 bits) or 30 decimal digits Using small primes file "binprimes" with 664579 primes up to 9999991 Testing n for composite with small primes ... n is composite with COMPLETE factorization: 7 x 23 x 73 x 89 x 199 x 153649 x 599479 x 33057806959 Verified the composite product. -------------------------------------------------------------------------- C:\......>rabinmiller M189 Using small primes file "binprimes" with 664579 primes up to 9999991 M189 = 2^189 - 1 : 784637716923335095479473677900958302012794430558004314111 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF n has 24 bytes (192 bits) or 57 decimal digits Testing n for composite with small primes ... n is composite with potentially PARTIAL factorization: 7 x 7 x 73 x 127 x 337 x 92737 x 262657 x 649657 x 1560007 x 207617485544258392970753527 Verified the composite product. The final factor 207617485544258392970753527 *MAY* be prime Continuing with Rabin-Miller... Found s and t; verified that 2^t*s = n-1 Start of 64 iterations ... Iteration # 1 Iteration # 2 Iteration # 3 a^s mod n != 1 ... checking powers ... Iteration # 4 Iteration # 5 a^s mod n != 1 ... checking powers ... Iteration # 6 ...... Iteration # 64 a^s mod n != 1 ... checking powers ... The final factor is prime with a certainty of at LEAST 1- 2^-128 -------------------------------------------------------------------------- C:\.........>rabinmiller Q31 Q31 = 10^31 + 1 : 10000000000000000000000000000001 0x7E37BE2022C0914B2680000001 n has 13 bytes (104 bits) or 32 decimal digits Using small primes file "binprimes" with 664579 primes up to 9999991 Testing n for composite with small primes ... n is composite with potentially PARTIAL factorization: 11 x 909090909090909090909090909091 Verified the composite product. The final factor 909090909090909090909090909091 *MAY* be prime Continuing with Rabin-Miller... Found s and t; verified that 2^t*s = n-1 Start of 64 iterations ... Iteration # 1 a^s mod n != 1 ... checking powers ... Iteration # 2 a^s mod n != 1 ... checking powers ... Iteration # 3 a^s mod n != 1 ... checking powers ... Iteration # 4 .... .... Iteration # 62 Iteration # 63 Iteration # 64 The final factor is prime with a certainty of at LEAST 1- 2^-128 -------------------------------------------------------------------------- C:\.........>rabinmiller R23 R23 = (10^23 - 1)/9 : 11111111111111111111111 0x25A55A46E5DA99C71C7 n has 10 bytes (80 bits) or 23 decimal digits Using small primes file "binprimes" with 664579 primes up to 9999991 Testing n for composite with small primes ... 11111111111111111111111 *MAY* be prime Continuing with Rabin-Miller... Found s and t; verified that 2^t*s = n-1 Start of 64 iterations ... Iteration # 1 Iteration # 2 Iteration # 3 Iteration # 4 Iteration # 5 a^s mod n != 1 ... checking powers ... Iteration # 6 a^s mod n != 1 ... checking powers ... ..... ..... Iteration # 63 Iteration # 64 n is prime with a certainty of at LEAST 1- 2^-128 -------------------------------------------------------------------------- C:\......>rabinmiller P6 Enter 6 numbers a1, b1, e1, a2, b2 and e2 for form: a1*(b1^e1) + a2*(b2^e2) .. 1 8 25 1 3 25 a1*(b1^e1) + a2*(b2^e2) = 1*8^25 + 1*3^25 : 37778931863804450319011 0x0800000000C546562AA3 n has 10 bytes (80 bits) or 23 decimal digits Using small primes file "binprimes" with 664579 primes up to 9999991 Testing n for composite with small primes ... n is composite with COMPLETE factorization: 11 x 101 x 151 x 3001 x 16301 x 4603396951 Verified the composite product. --------------------------------------------------------------------------

- Rabin-Miller Strong Pseudoprime Test.
- Practical Cryptography, N. Ferguson and Bruce Schneier, Wiley 2003.
- Prime Numbers and Computer Methods for Factorization, Progress in Mathematics Vol. 57, H. Riesel, Birkhauser,1985.
- Prime Curios!, C. Caldwell and G. Honaker, Jr., Create Space, 2009.
- The Largest Known Prime by Year: A Brief History (The Prime Pages @ UTM).