PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
Miller-Rabin prime test (Algorithm)

The Miller-Rabin prime test is a probabilistic test based on the following

Theorem 1   Let $ N\geq 3$ be an odd number and $ N-1=2^tn$, $ n$ odd. If and only if for every $ a\in\mathbb{Z}$ with $ \gcd(a,N)=1$ we have
\begin{subequations}\begin{gather}a^n\equiv 1\quad\text{mod }N\qquad\text{or}\\ a^{2^sn}\equiv-1\quad\text{mod }N \end{gather}\end{subequations}    

for some $ s\in\{0,\dots,t-1\}$, then $ N$ is prime. If $ N$ is not prime, then let $ A$ be the set of all $ a$ satisfying the above conditions. We have
Card$\displaystyle (A)\leq\frac{1}{4}\varphi(N),$
where $ \varphi$ is Euler's Phi-function.
A composite number $ N$ satisfying conditions (1) for some $ a\in\mathbb{Z}$ is called a strong pseudoprime in the basis $ a$. Note that this theorem states that there are no such things as Carmichael numbers for strong pseudoprimes (i.e. composite numbers that are strong pseudoprimes for all values of $ a$). From this theorem we can construct the following algorithm:
  1. Choose a random $ 2\leq a\leq N-1$.
  2. If $ \gcd(a,N)\neq 1$, we have a non-trivial divisor of $ N$, so $ N$ is not prime.
  3. If $ \gcd(a,N)=1$, check if the conditions (1) are satisfied. If not, $ N$ is not prime, otherwise the probability that $ N$ is not prime is less than $ \frac{1}{4}$.
In general the probability, that the test falsely reports $ N$ as a prime is far less than $ \frac{1}{4}$. Of course the algorithm can be applied several times in order to reduce the probability, that $ N$ is not a prime but reported as one.

When comparing this test with the related Solovay-Strassen test one sees that this test is superior is several ways:

  • There is no need to calculate the Jacobi symbol.
  • The amount of false witnesses, i.e. numbers $ a$ that report $ N$ as a prime when it is not, is at most $ \frac{N}{4}$ instead of $ \frac{N}{2}$.
  • One can even show that $ N$ which passes Miller-Rabin for some $ a$ also passes Solovay-Strassen for that $ a$, so Miller-Rabin is always better.
Note that when the test returns that $ N$ is composite, then this is indeed the case, so it is really a compositeness test rather than a test for primality.



"Miller-Rabin prime test" is owned by mathwizard.
(view preamble)

View style:

See Also: Solovay-Strassen test, Fermat compositeness test

Other names:  Rabin prime test
Also defines:  strong pseudoprime
Log in to rate this entry.
(view current ratings)

Cross-references: primality, even, numbers, witnesses, Jacobi symbol, calculate, Solovay-Strassen test, order, divisor, algorithm, Carmichael numbers, basis, composite number, Euler's, prime, odd, odd number

This is version 6 of Miller-Rabin prime test, born on 2004-12-21, modified 2005-02-23.
Object id is 6589, canonical name is MillerRabinPrimeTest.
Accessed 8682 times total.

Classification:
AMS MSC: 11Y11 (Number theory :: Computational number theory :: Primality)
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)