homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightNumber theory

Miller–Rabin primality test

The calculator checks whether or not a number is prime by Miller-Rabin primality test

This calculator checks if an integer is a prime number using Miller–Rabin primality test. The test uses a series of integers as test bases, which are also called test witnesses. The test witnesses can be obtained in two ways - by entering or randomly generated. If the test returns no, then the given number is definitely composite, if the test returns yes, then the number is prime with a high probability. The larger the number of witnesses the better the test accuracy. You can better understand the detailed output produced by the calculator by reading about the principles of the Miller–Rabin algorithm described just below the calculator.

PLANETCALC, Miller–Rabin primality test

Miller–Rabin primality test

Can be prime
 
Powers of 2 factoring
 

Miller–Rabin primality test algorithm

To apply the Miller-Rabin primality test to an odd integer n we represent an even n-1 integer as 2sd, where d - odd integer, s - integer power of 2. We get the numbers s and d by sequentially dividing n-1 by 2 until the remainder is odd.
After that we sequentially check, one of the following is true:

  1. a^{d}\equiv 1{\pmod {n}}
  2. a^{2^{r}d}\equiv -1{\pmod {n}}
    where:
    • a - a test witness, integer number in the range [2..n-1]
    • r - a natural number less than s.

If at least one condition is met, then the chosen a is a primality witness of the number n, and the number n can be prime with a high probability. To increase this probability we repeat the test for other randomly generated bases a.
If both conditions are not met, then the number n is composite and further testing can be stopped.
The Miller-Rabin primality test successfully handles the Carmichael numbers, which are not feasible for the Fermat primality test.
E.g. the number 29341, erroneously stated by Fermat's test as prime, is determined as a composite by the Miller-Rabin test.

Unlike Fermat's test, there are no "bad" test numbers for the Miller-Rabin test. For any number the test gives correct answer with a high probability. The incorrect result of the algorithm is determined only by a random choice of test witnesses, the probability of which is small1.
According to Rabin's research, no more than a quarter of the numbers in the range [1..n-1] are not witnesses2 (that is, they give an erroneous result in the Miller-Rabin test). Therefore the final error probability of the k-round test is less than 1/4k.


  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to algorithms 

  2. Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of number theory 12, 128-138 (1980) 

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Miller–Rabin primality test

Comments