Miller–Rabin primality test

Builds on Primality test Fermat's little theorem Modular exponentiation

Summary

The Miller–Rabin test is a probabilistic primality test for an odd integer $n > 2$ . Write $n - 1 = 2^s d$ with $d$ odd, and choose a base $a$ with $1 < a < n - 1$ . The number $n$ passes for base $a$ if $a^d \equiv 1 \pmod n$ , or if $a^{2^r d} \equiv -1 \pmod n$ for some $r$ with $0 \le r < s$ . Each odd prime $n$ passes for each base. If $n$ fails for some base, then $n$ is composite.

Remarks

The prime case follows from Fermat's little theorem and the fact that $\pm 1$ are the only square roots of $1$ modulo a prime. If $n$ is an odd composite number, then at most $\frac{1}{4}$ of the bases let it pass. So $k$ random bases give an error probability of at most $4^{-k}$ . Gary Miller found the test in 1976, in a deterministic form that depends on the extended Riemann hypothesis. Michael Rabin made it an unconditional probabilistic test in 1980.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Where this leads

2 pages build on this one.

Tag	`0SZCSYHW60`
URI	`m2://0SZCSYHW60`
Aliases	`rabin-miller-primality-test`
Kind	concept
Writing	W1 stated
MSC	11Y11
Specializes	Primality test
Uses	Primality test, Fermat's little theorem, Modular exponentiation
Same as	Wikidata Q980224 Wikipedia Miller–Rabin primality test

Miller–Rabin primality test

Summary

Remarks

Reading path

Where this leads

Further reading

What this page needs for W2

What links here

Used by