# 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 $2^s \cdot d$, where d is odd. Then, provided that all of the following formulas hold, n is composite:

$a^{d} \not\equiv 1\pmod{n}$
$a^{2^rd} \not\equiv -1\pmod{n}$ for all $0 \le r \le s-1$

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 / 4k 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]

##  References

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

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

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