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 calculator's detailed output by reading about the principles of the Miller–Rabin algorithm described just below the calculator.

Miller–Rabin primality test

Integer number

Bases

Random

List

Number of rounds

Bases

Details

Calculate

Can be prime

 

Powers of 2 factoring

 

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

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 2^sd, 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. 
2. 
   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 the 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 small¹.
According to Rabin's research, no more than a quarter of the numbers in the range [1..n-1] are not witnesses² (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/4^k.