Miller–Rabin primality test
The calculator checks whether or not a number is prime by Miller-Rabin primality test
This page exists due to the efforts of the following people:
Anton
| |
 | Timur
|
This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8995/. Also, please do not modify any references to the original work (if any) contained in this content.
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
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:
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 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.
Comments