Rabin-Miller Primality Tester for .NET 4

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.cs is a .NET Framework 4 C# console application for WinXP SP3 and higher which attempts to factor a number of ANY size into component primes using a pre-generated list of small primes. If the factorization into component primes is NOT complete, the application invokes the Rabin-Miller algorithm to check probablistic primality of the final factor. The .NET Framework 4 is required for this application since it uses BigInteger functionality. Since .NET 3.5 is included with Windows 7, .NET Framework 4 must be downloaded for all current versions of Windows to use this application. The command line form takes at most 3 arguments: 

       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 --> 2127 - 1              (A Mersenne number)

        N127 --> 2127 + 1

        R127 --> (10127 - 1)/9         (A Repunit number)

        Q127 --> 10127 + 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*b1e1 + a2*b2e2 + a3*b3e3
In 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.

(2) The second optional argument is the number of Rabin-Miller iterations which defaults to 64 which provides a certainty for primality of at least 1 - 2-128 . For numbers that are KNOWN to be properly randomly generated, the number of iterations needed to achieve a required certainty of primality is considerably less than this upper bound suggests and is dependent on the size of the number. However if the origin of the number to be tested with Rabin-Miller is unknown, as discussed in Ref. 2 the number of iterations associated with the upper bound of probability expression is required.

(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 binprimes is found in the same directory as rabinmiller.exe, the file is read into an integer array which contains all prime numbers less than 10,000,000, i.e. 664579 primes. These prime numbers are packed in binprimes as little-endian 4 byte int32 values. If the file binprimes is not found, rabinmiller.exe simple uses a short internal list of all primes less than 1000. In either case, for a number n, the application tries all small primes in the array up to Sqrt(n) (or to the maximum value prime in the array). If the number can be factored using the small primes list so that the remaining FINAL factor is less than or equal to the square of the maximum small prime in the list, pmaxsq, the factorization is complete. However, if the FINAL factor (including the case where no factors are found) is GREATER THAN pmaxsq, then the final factor MAY be prime or composite. In this case, the Rabin-Miller test is executed and the result displayed.

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 rabinmiller.exe v 1.2.0.0 (27,776 bytes) for .NET 4, digitally signed, and binprimes (2,658,316 bytes) with all primes <10,000,000)

[Note: This application does NOT enforce a limit on the size of the number that may be entered via either the command line or an associated file.]

Sample Outputs


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.
--------------------------------------------------------------------------

References