# Miller-Rabin primality test

The Miller-Rabin primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay-Strassen primality test. Its original version, due to G. L. Miller, is deterministic, but it relies on the unproven generalized Riemann hypothesis; M. O. Rabin modified it to obtain an unconditional probabilistic algorithm.

 Contents

## Concepts

Just like with the Fermat and Solovay-Strassen tests, with the Miller-Rabin test we will rely on an equality or set of equalities that hold true for prime values, and then see whether or not they hold for a number that we want to test for primality.

Let n be an odd prime, then we can write n − 1 as 2s × d, where s is an integer and d is odd -- this is the same as factoring out 2 from n repeatedly. Then, one of the following must be true for some [itex]a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*[itex]:

[itex]

a^{d} \equiv 1\pmod{n} [itex] or

[itex]

a^{2^r\cdot d} \equiv -1\pmod{n}[itex] for some [itex]0 \le r \le s-1 [itex]

To show that one of these must be true, recall Fermat's little theorem:

[itex]

a^{n-1} \equiv 1\pmod{n} [itex]

So, if we keep taking square roots of an − 1, we will either get 1 or −1. If we get −1 then the second equality holds and we are done.

In the case when we've taken out every power of 2 and the second equality never held, we are left with the first equality which also must be equal to 1 or −1, as it too is a square root. However, if the second equality never held, then it couldn't have held for r = 0, meaning that

[itex]

a^{2^0\cdot d} = a^d \not\equiv -1\pmod{n} [itex]

Thus in the case the second equality doesn't hold, the first equality must.

The Miller-Rabin primality test is based on the above equalities. If we want to test to see if n is prime, then if

[itex]

a^{d} \not\equiv 1\pmod{n} [itex] and

[itex]

a^{2^rd} \not\equiv -1\pmod{n}[itex] for all [itex]0 \le r \le s-1 [itex]

then a is called a strong witness for the compositeness of n. Otherwise a is called a strong liar and n is a probable prime.

## Algorithm and running time

The algorithm can be written as follows:

Inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s × d by factoring powers of 2 from n − 1
repeat k times:
pick a randomly in the range [1, n − 1]
if ad mod n ≠ 1 and [itex]a^{2^rd}[itex] mod n ≠ −1 for all r in the range [0, s − 1] then return composite
return probably prime

Using modular exponentiation by repeated squaring, the running time of this algorithm is O(k × log3 n), where k is the number of different values of a we test, furthermore fast FFT multiplication can push the running time down to Õ(k × log2 n), thus this algorithm is polynomial time and efficient.

## Additional information

Like all probabilistic primality tests, there are values of n that will repeatedly produce liars, thus claiming that n is prime when it is actually composite -- these values are known as pseudoprimes.

The more values of a we test, the better the accuracy of the test. It can be shown that there always exists a strong witness for any odd composite n, and that at least 3/4 of the values for a are strong witnesses for the compositeness of n. Thus, the set of strong liars is smaller than the set of Euler liars (used in the Solovay-Strassen primality test).

In general usage the actual number of witnesses is much greater than the lower bound. For instance if we test a 1024-bit odd integer n using the lower bound we would need to test 44 different values of a to guarantee that the chance a given n was declared prime when it was actually composite is less than 2-80, which means that the value of n could be used safely in cryptographic purposes. However, in practice we generally need to test only 6 different values of a to guarantee this probability. Compare this to 90 iterations for Solovay-Strassen.

Assuming the truth of the generalized Riemann hypothesis, one can prove that, if all the values of a up to 2(log n)2 have been tested and n is still pronounced a "probable prime", then it is in fact guaranteed to be prime. This leads to a deterministic primality test that has runtime Õ((log n)4).

## External links

##### Navigation

Academic Kids Menu

• Art and Cultures
• Art (http://www.academickids.com/encyclopedia/index.php/Art)
• Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
• Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
• Music (http://www.academickids.com/encyclopedia/index.php/Music)
• Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
• Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
• Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
• Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
• Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
• Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
• History (http://www.academickids.com/encyclopedia/index.php/History)
• Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
• Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
• Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
• Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
• Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• United States (http://www.academickids.com/encyclopedia/index.php/United_States)
• Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
• World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
• Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
• Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
• Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
• Science (http://www.academickids.com/encyclopedia/index.php/Science)
• Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
• Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
• Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
• Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
• Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
• Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
• Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
• Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
• Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
• Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
• Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
• Government (http://www.academickids.com/encyclopedia/index.php/Government)
• Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
• Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
• Space and Astronomy
• Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
• Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
• Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
• Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
• Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
• US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

• Home Page (http://academickids.com/encyclopedia/index.php)
• Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

• Clip Art (http://classroomclipart.com)