# Category:Miller-Rabin primality test

The Miller-Rabin primality test is a simple probabilistic algorithm for determining whether a number is prime or composite that is easy to implement. It proves compositeness of a number using the following formulas:

Suppose 0 < *a* < *n* is coprime to *n* (this is easy to test using the GCD). Write the number *n*−1 as , where *d* is odd. Then, provided that all of the following formulas hold, *n* is composite:

- for all

If *a* is chosen uniformly at random and *n* is prime, these formulas hold with probability 1/4. Thus, repeating the test for *k* random choices of *a* gives a probability of 1 − 1 / 4^{k} that the number is prime. Moreover, Jaeschke showed that any 32-bit number can be deterministically tested for primality by trying only *a*=2, 7, and 61.^{[1]}

## [edit] References

- ↑ Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", Mathematics of Computation 61 (204): 915–926, doi:10.2307/2153262.

## Pages in category "Miller-Rabin primality test"

The following 4 pages are in this category, out of 4 total.