Category:Miller-Rabin primality test

From LiteratePrograms
Jump to: navigation, search

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]

[edit] References

  1. 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.