# MillerâRabin primality test Information

*https://en.wikipedia.org/wiki/MillerâRabin_primality_test*

The **MillerâRabin primality test** or **RabinâMiller primality test** is a probabilistic
primality test: an
algorithm which determines whether a given number is
likely to be prime, similar to the
Fermat primality test and the
SolovayâStrassen primality test.

It is of historical significance in the search for a polynomial-time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known.

Gary L. Miller discovered the test in 1976; Miller's version of the test is
deterministic, but its correctness relies on the unproven
extended Riemann hypothesis.^{
[1]}
Michael O. Rabin modified it to obtain an unconditional
probabilistic algorithm in 1980.^{
[2]}^{
[a]}

## Mathematical concepts

Similarly to the Fermat and SolovayâStrassen tests, the MillerâRabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.

### Strong probable primes

The property is the following. For a given odd integer *n* > 2, letâs write *n* â 1 as 2^{s}*d* where *s* is a positive integer and *d* is an odd positive integer. Letâs consider an integer *a*, called a *base*, which is
coprime to *n*.
Then, *n* is said to be a **strong
probable prime to base a** if one of these
congruence relations holds:

- ;
- for some 0 â€ r <
*s*.

The idea beneath this test is that when *n* is an odd prime, it passes the test because of two facts:

- by
Fermat's little theorem, (this property alone defines the weaker notion of
*probable prime to base a*, on which the Fermat test is based); - the only
square roots of 1 modulo
*n*are 1 and â1.

Hence, by
contraposition, if *n* is not a strong probable prime to base *a*, then *n* is definitely composite, and *a* is called a **
witness** for the compositeness of *n* (sometimes misleadingly called a *strong witness*).

However, this property is not an exact characterization of prime numbers. If *n* is composite, it may nonetheless be a strong probable prime to base *a*, in which case it is called a **
strong pseudoprime**, and *a* is a **strong liar**.

### Choices of bases

Thankfully, no composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the
Carmichael numbers). However no simple way of finding a witness is known. A naĂŻve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see
section *Miller test* below).

Another solution is to pick a base at random. This yields a fast
probabilistic test. When *n* is composite, most bases are witnesses, so the test will detect *n* as composite with a reasonably high probability (see
section *Accuracy* below). We can quickly reduce the probability of a
false positive to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the MillerâRabin test. The number of bases to try does not depend on *n*. There seems to be diminishing returns in trying many bases, because if *n* is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base.^{
[4]}^{: Â§8 }

Note that *a*^{d} âĄ 1 (mod *n*) holds trivially for *a* âĄ 1 (mod *n*), because the congruence relation is
compatible with exponentiation. And *a*^{d} = *a*^{20d} âĄ â1 (mod *n*) holds trivially for *a* âĄ â1 (mod *n*) since d is odd, for the same reason. That is why random a are usually chosen in the interval 1 < *a* < *n* â 1.

For testing arbitrarily large n, choosing bases at random is essential, as we don't know the distribution of witnesses and strong liars among the numbers 2, 3, âŠ, *n* â 2.^{
[b]}

However, a pre-selected set of a few small bases guarantees the identification of all composites up to a pre-computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough *n* (see
section *Testing against small sets of bases* below).

### Proofs

Here is a proof that if *n* is a prime then the only square roots of 1 modulo *n* are 1 and â1 modulo *n*.

**Proof**

Certainly 1 and â1, when squared modulo *n*, always yield 1. It remains to show that there are no other square roots of 1 modulo *n*. This is a special case, here applied with the
polynomial X^{2} â 1 over the
finite field **Z**/*n***Z**, of the more general fact that a polynomial over some
field has no more
roots than its degree (this theorem follows from the existence of an
Euclidean division for polynomials). Here follows a more elementary proof. Suppose that *x* is a square root of 1 modulo *n*. Then:

In other words, *n* divides the product (*x* â 1)(*x* + 1). By
Euclid's lemma, since *n* is prime, it divides one of the factors *x* â 1 or *x* + 1, implying that *x* is congruent to either 1 or â1 modulo *n*.

Here is a proof that if *n* is an odd prime then it is a strong probable prime to base *a*.

**Proof**

If *n* is an odd prime and we write *n* â 1= 2^{s}*d* where *s* is a positive integer and *d* is an odd positive integer, by Fermat's little theorem:

Each term of the sequence is a square root of the previous term. Since the first term is congruent to 1, the second term is a square root of 1 modulo *n*. By the previous
lemma, it is congruent to either 1 or â1 modulo *n*. If it is congruent to â1, we are done. Otherwise, it is congruent to 1 and we can
iterate the reasoning. At the end, either one of the terms is congruent to â1, or all of them are congruent to 1, and in particular the last term, *a*^{d}, is.

## Example

Suppose we wish to determine if *n* = 221 is prime. We write *n* â 1 as 2^{2} Ă 55, so that we have *s* = 2 and *d* = 55. We randomly select a number *a* such that 1 < *a* < *n*, say *a* = 174. We proceed to compute:

*a*^{20d}mod*n*= 174^{55}mod 221 = 47 â 1,*n*â 1*a*^{21d}mod*n*= 174^{110}mod 221 = 220 =*n*â 1.

Since 220 âĄ â1 mod *n*, either 221 is prime, or 174 is a strong liar for 221. We try another random *a*, this time choosing *a* = 137:

*a*^{20d}mod*n*= 137^{55}mod 221 = 188 â 1,*n*â 1*a*^{21d}mod*n*= 137^{110}mod 221 = 205 â*n*â 1.

Hence 137 is a witness for the compositeness of 221, and 174 was in fact a strong liar. Note that this tells us nothing about the factors of 221 (which are 13 and 17). However, the example with 341 in
a later section shows how these calculations can sometimes produce a factor of *n*.

## MillerâRabin test

The algorithm can be written in
pseudocode as follows. The parameter *k* determines the accuracy of the test. The greater the number of rounds, the more accurate the result.^{
[6]}

Input #1:n> 2, an odd integer to be tested for primalityInput #2:k, the number of rounds of testing to performOutput: âcompositeâ ifnis found to be composite, âprobably primeâ otherwise lets> 0 anddodd > 0 such thatnâ 1 = 2^{s}d# by factoring out powers of 2 fromnâ 1repeatktimes:aâ random(2,nâ 2) #nis always a probable prime to base 1 andnâ 1xâa^{d}modnrepeatstimes:yâx^{2}modnify= 1 andxâ 1 andxânâ 1then# nontrivial square root of 1 modulonreturnâcompositeâxâyifyâ 1thenreturnâcompositeâreturnâprobably primeâ

### Complexity

Using
repeated squaring, the running time of this algorithm is
O(*k* log^{3} *n*), where *n* is the number tested for primality, and *k* is the number of rounds performed; thus this is an efficient, polynomial-time algorithm.
FFT-based multiplication (
Harvey-Hoeven algorithm) can decrease the running time to O(*k* log^{2} *n* log log *n*) =
Ă(*k* log^{2} *n*).

### Accuracy

The error made by the primality test is measured by the probability that a composite number is declared probably prime. The more bases *a* are tried, the better the accuracy of the test. It can be shown that if *n* is composite, then at most 1⁄4 of the bases *a* are strong liars for *n*.^{
[2]}^{
[7]} As a consequence, if *n* is composite then running *k* iterations of the MillerâRabin test will declare *n* probably prime with a probability at most 4^{âk}.

This is an improvement over the
SolovayâStrassen test, whose worstâcase error bound is 2^{âk}. Moreover, the MillerâRabin test is strictly stronger than the SolovayâStrassen test in the sense that for every composite *n*, the set of strong liars for *n* is a subset of the set of
Euler liars for *n*, and for many *n*, the subset is proper.

In addition, for large values of *n*, the probability for a composite number to be declared probably prime is often significantly smaller than 4^{âk}. For instance, for most numbers *n*, this probability is bounded by 8^{âk}; the proportion of numbers *n* which invalidate this upper bound vanishes as we consider larger values of *n*.^{
[8]} Hence the *average* case has a much better accuracy than 4^{âk}, a fact which can be exploited for *generating* probable primes (see
below). However, such improved error bounds should not be relied upon to *verify* primes whose
probability distribution is not controlled, since a
cryptographic adversary might send a carefully chosen pseudoprime in order to defeat the primality test.^{
[c]}
In such contexts, only the *worstâcase* error bound of 4^{âk} can be relied upon.

The above error measure is the probability for a composite number to be declared as a strong probable prime after *k* rounds of testing; in mathematical words, it is the
conditional probability
where *P* is the
event that the number being tested is prime, and *MR _{k}* is the event that it passes the MillerâRabin test with

*k*rounds. We are often interested instead in the inverse conditional probability : the probability that a number which has been declared as a strong probable prime is in fact composite. These two probabilities are related by Bayes' law:

In the last equation, we simplified the expression using the fact that all prime numbers are correctly reported as strong probable primes (the test has no false negative). By dropping the left part of the denominator, we derive a simple upper bound:

Hence this conditional probability is related not only to the error measure discussed above ââŻwhich is bounded by 4^{âk}âŻâ but also to the
probability distribution of the input number. In the general case, as said earlier, this distribution is controlled by a cryptographic adversary, thus unknown, so we cannot deduce much about . However, in the case when we use the MillerâRabin test to *generate* primes (see
below), the distribution is chosen by the generator itself, so we can exploit this result.

## Deterministic variants

### Miller test

The MillerâRabin algorithm can be made deterministic by trying all possible *a* below a certain limit. Taking *n* as the limit would imply O(*n*) trials, hence the running time would be exponential with respect to the size log *n* of the input. To improve the running time, the challenge is then to lower the limit as much as possible while keeping the test reliable.

If the tested number *n* is composite, the strong liars *a* coprime to *n* are contained in a proper
subgroup of the group (**Z**/*n***Z**)*, which means that if we test all *a* from a set which
generates (**Z**/*n***Z**)*, one of them must lie outside the said subgroup, hence must be a witness for the compositeness of *n*. Assuming the truth of the
generalized Riemann hypothesis (GRH), it is known that the group is generated by its elements smaller than O((
ln *n*)^{2}), which was already noted by Miller.^{
[1]} The constant involved in the
Big O notation was reduced to 2 by
Eric Bach.^{
[10]} This leads to the following deterministic primality testing algorithm, known as the **Miller test**:

Input:n> 2, an odd integer to be tested for primalityOutput: âcompositeâ ifnis composite, âprimeâ otherwise lets> 0 anddodd > 0 such thatnâ 1 = 2^{s}d# by factoring out powers of 2 fromnâ 1for allainthe range [2, min(nâ 2, â2(lnn)^{2}â)]:xâa^{d}modnrepeatstimes:yâx^{2}modnify= 1 andxâ 1 andxânâ 1then# nontrivial square root of 1 modulonreturnâcompositeâxâyifyâ 1thenreturnâcompositeâreturnâprimeâ

The full power of the generalized Riemann hypothesis is not needed to ensure the correctness of the test: as we deal with subgroups of even
index, it suffices to assume the validity of GRH for
quadratic
Dirichlet characters.^{
[7]}

The running time of the algorithm is, in the
soft-O notation, Ă((log *n*)^{4}) (using FFTâbased multiplication).

The Miller test is not used in practice. For most purposes, proper use of the probabilistic MillerâRabin test or the BaillieâPSW primality test gives sufficient confidence while running much faster. It is also slower in practice than commonly used proof methods such as APR-CL and ECPP which give results that do not rely on unproven assumptions. For theoretical purposes requiring a deterministic polynomial time algorithm, it was superseded by the AKS primality test, which also does not rely on unproven assumptions.

### Testing against small sets of bases

When the number *n* to be tested is small, trying all *a* < 2(ln *n*)^{2} is not necessary, as much smaller sets of potential witnesses are known to suffice. For example, Pomerance, Selfridge, Wagstaff^{
[4]} and Jaeschke^{
[11]} have verified that

- if
*n*< 2,047, it is enough to test*a*= 2; - if
*n*< 1,373,653, it is enough to test*a*= 2 and 3; - if
*n*< 9,080,191, it is enough to test*a*= 31 and 73; - if
*n*< 25,326,001, it is enough to test*a*= 2, 3, and 5; - if
*n*< 3,215,031,751, it is enough to test*a*= 2, 3, 5, and 7; - if
*n*< 4,759,123,141, it is enough to test*a*= 2, 7, and 61; - if
*n*< 1,122,004,669,633, it is enough to test*a*= 2, 13, 23, and 1662803; - if
*n*< 2,152,302,898,747, it is enough to test*a*= 2, 3, 5, 7, and 11; - if
*n*< 3,474,749,660,383, it is enough to test*a*= 2, 3, 5, 7, 11, and 13; - if
*n*< 341,550,071,728,321, it is enough to test*a*= 2, 3, 5, 7, 11, 13, and 17.

Using the work of Feitsma and Galway enumerating all base 2 pseudoprimes in 2010, this was extended (see
OEIS:
A014233), with the first result later shown using different methods in Jiang and Deng:^{
[12]}

- if
*n*< 3,825,123,056,546,413,051, it is enough to test*a*= 2, 3, 5, 7, 11, 13, 17, 19, and 23. - if
*n*< 18,446,744,073,709,551,616 = 2^{64}, it is enough to test*a*= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.

Sorenson and Webster^{
[13]} verify the above and calculate precise results for these larger than 64âbit results:

- if
*n*< 318,665,857,834,031,151,167,461, it is enough to test*a*= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37. - if
*n*< 3,317,044,064,679,887,385,961,981, it is enough to test*a*= 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

Other criteria of this sort, often more efficient (fewer bases required) than those shown above, exist.^{
[14]}^{
[15]}^{
[16]}^{
[17]} They give very fast deterministic primality tests for numbers in the appropriate range, without any assumptions.

There is a small list of potential witnesses for every possible input size (at most *b* values for *b*âbit numbers). However, no finite set of bases is sufficient for all composite numbers. Alford, Granville, and Pomerance have shown that there exist infinitely many composite numbers *n* whose smallest compositeness witness is at least (ln *n*)^{1/(3ln ln ln n)}.^{
[18]} They also argue heuristically that the smallest number *w* such that every composite number below *n* has a compositeness witness less than *w* should be of order
Î(log *n* log log *n*).

## Variants for finding factors

By inserting
greatest common divisor calculations into the above algorithm, we can sometimes obtain a factor of *n* instead of merely determining that *n* is composite. This occurs for example when *n* is a probable prime to base *a* but not a strong probable prime to base *a*.^{
[19]}^{: 1402 }

If *x* is a nontrivial square root of 1 modulo *n*,

- since
*x*^{2}âĄ 1 (mod*n*), we know that*n*divides*x*^{2}â 1 = (*x*â 1)(*x*+ 1); - since
*x*âą Â±1 (mod*n*), we know that*n*does not divide*x*â 1 nor*x*+ 1.

From this we deduce that *A* = gcd(*x* â 1, *n*) and *B* = gcd(*x* + 1, *n*) are nontrivial (not necessarily prime) factors of *n* (in fact, since *n* is odd, these factors are coprime and *n* = *AB*). Hence, if factoring is a goal, these gcd calculations can be inserted into the algorithm at little additional computational cost. This leads to the following pseudocode, where the added or changed code is highlighted:

Input #1:n> 2, an odd integer to be tested for primalityInput #2:k, the number of rounds of testing to performOutput: (âmultiple ofâ,m) if a nontrivial factormofnis found, âcompositeâ ifnis otherwise found to be composite, âprobably primeâ otherwise lets> 0 anddodd > 0 such thatnâ 1 = 2^{s}d# by factoring out powers of 2 fromnâ 1repeatktimes:aâ random(2,nâ 2) #nis always a probable prime to base 1 andnâ 1xâa^{d}modnrepeatstimes:yâx^{2}modnify= 1 andxâ 1 andxânâ 1then# nontrivial square root of 1 modulonreturn(âmultiple ofâ, gcd(xâ 1,n))xâyifyâ 1thenreturnâcompositeâreturnâprobably primeâ

This is *not* a probabilistic
factorization algorithm because it is only able to find factors for numbers *n* which are pseudoprime to base *a* (in other words, for numbers *n* such that *a*^{nâ1} âĄ 1 mod *n*). For other numbers, the algorithm only returns â*composite*â with no further information.

For example, consider *n* = 341 and *a* = 2. We have *n* â 1 = 85 Ă 4. Then 2^{85} mod 341 = 32 and 32^{2} mod 341 = 1. This tells us that *n* is a pseudoprime base 2, but not a strong pseudoprime base 2. By computing a gcd at this stage, we find a factor of 341: gcd(32 â 1, 341) = 31. Indeed, 341 = 11 Ă 31.

In order to find factors more often, the same ideas can also be applied to the square roots of â1 (or any other number).
This strategy can be implemented by exploiting knowledge from previous rounds of the MillerâRabin test. In those rounds we may have identified a square root modulo *n* of â1, say *R*. Then, when *x*^{2} mod *n* = *n*â1, we can compare the value of *x* against *R*: if *x* is neither *R* nor *n*â*R*, then gcd(*x* â *R*, *n*) and gcd(*x* + *R*, *n*) are nontrivial factors of *n*.^{
[14]}

## Generation of probable primes

The MillerâRabin test can be used to generate strong probable primes, simply by drawing integers at random until one passes the test. This algorithm terminates
almost surely (since at each iteration there is a chance to draw a prime number). The pseudocode for generating *b*â
bit strong probable primes (with the most significant bit set) is as follows:

Input #1:b, the number of bits of the resultInput #2:k, the number of rounds of testing to performOutput: a strong probable primenwhileTrue: pick a random odd integernin the range [2^{bâ1}, 2^{b}â1]ifthe MillerâRabin test with inputsnandkreturns âprobably primeâthenreturnn

### Complexity

Of course the worst-case running time is infinite, since the outer loop may never terminate, but that happens with probability zero. As per the geometric distribution, the expected number of draws is (reusing notations from earlier).

As any prime number passes the test, the probability of being prime gives a coarse lower bound to the probability of passing the test. If we draw odd integers
uniformly in the range [2^{bâ1}, 2^{b}â1], then we get:

where Ï is the
prime-counting function. Using an
asymptotic expansion of Ï (an extension of the
prime number theorem), we can approximate this probability when *b* grows towards infinity. We find:

Hence we can expect the generator to run no more MillerâRabin tests than a number proportional to *b*. Taking into account the worst-case complexity of each MillerâRabin test (see
earlier), the expected running time of the generator with inputs *b* and *k* is then bounded by O(*k* *b*^{4}) (or Ă(*k* *b*^{3}) using FFT-based multiplication).

### Accuracy

The error measure of this generator is the probability that it outputs a composite number.

Using the relation between conditional probabilities (shown in an earlier section) and the asymptotic behavior of (shown just before), this error measure can be given a coarse upper bound:

Hence, for large enough *b*, this error measure is less than . However, much better bounds exist.

Using the fact that the MillerâRabin test itself often has an error bound much smaller than 4^{âk} (see
earlier),
DamgĂ„rd,
Landrock and
Pomerance derived several error bounds for the generator, with various classes of parameters *b* and *k*.^{
[8]} These error bounds allow an implementor to choose a reasonable *k* for a desired accuracy.

One of these error bounds is 4^{âk}, which holds for all *b* â„ 2 (the authors only showed it for *b* â„ 51, while Ronald Burthe Jr. completed the proof with the remaining values 2 â€ *b* â€ 50^{
[20]}). Again this simple bound can be improved for large values of *b*. For instance, another bound derived by the same authors is:

which holds for all *b* â„ 21 and *k* â„ *b*/4. This bound is smaller than 4^{âk} as soon as *b* â„ 32.

## Notes

**^**The MillerâRabin test is often incorrectly said to have been discovered by M. M. Artjuhov as soon as 1967; a reading of Artjuhov's paper^{ [3]}(particularly his Theorem E) shows that he actually discovered the SolovayâStrassen test.**^**For instance, in 1995, Arnault gives a 397-digit composite number for which all bases less than 307 are strong liars; this number was reported to be prime by the Maple`isprime()`

function, because it implemented the MillerâRabin test with the specific bases 2, 3, 5, 7 and 11.^{ [5]}**^**For instance, in 2018, Albrecht et al. were able to construct, for many cryptographic libraries such as OpenSSL and GNU GMP, composite numbers that these libraries declared prime, thus demonstrating that they were not implemented with an adversarial context in mind.^{ [9]}

## References

- ^
^{a}^{b}Miller, Gary L. (1976), "Riemann's Hypothesis and Tests for Primality",*Journal of Computer and System Sciences*,**13**(3): 300â317, doi: 10.1145/800116.803773, S2CID 10690396 - ^
^{a}^{b}Rabin, Michael O. (1980), "Probabilistic algorithm for testing primality",*Journal of Number Theory*,**12**(1): 128â138, doi: 10.1016/0022-314X(80)90084-0 **^**Artjuhov, M. M. (1966â1967), "Certain criteria for primality of numbers connected with the little Fermat theorem",*Acta Arithmetica*,**12**: 355â364, MR 0213289- ^
^{a}^{b}Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25 Ă 10^{9}" (PDF).*Mathematics of Computation*.**35**(151): 1003â1026. doi: 10.1090/S0025-5718-1980-0572872-7. **^**F. Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases".*Journal of Symbolic Computation*.**20**(2): 151â161. doi: 10.1006/jsco.1995.1042.**^**Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. "31".*Introduction to Algorithms*(3rd ed.). MIT Press and McGraw-Hill. pp. 968â971. ISBN 0-262-03384-4.- ^
^{a}^{b}Schoof, RenĂ© (2004), "Four primality testing algorithms" (PDF),*Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography*, Cambridge University Press, ISBN 978-0-521-80854-5 - ^
^{a}^{b}DamgĂ„rd, I.; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test" (PDF),*Mathematics of Computation*,**61**(203): 177â194, Bibcode: 1993MaCom..61..177D, doi: 10.2307/2152945, JSTOR 2152945 **^**Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 October 2018).*Prime and Prejudice: Primality Testing Under Adversarial Conditions*(PDF). ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery. pp. 281â298. doi: 10.1145/3243734.3243787.**^**Bach, Eric (1990), "Explicit bounds for primality testing and related problems",*Mathematics of Computation*,**55**(191): 355â380, Bibcode: 1990MaCom..55..355B, doi: 10.2307/2008811, JSTOR 2008811**^**Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases",*Mathematics of Computation*,**61**(204): 915â926, doi: 10.2307/2153262, JSTOR 2153262**^**Jiang, Yupeng; Deng, Yingpu (2014). "Strong pseudoprimes to the first eight prime bases".*Mathematics of Computation*.**83**(290): 2915â2924. doi: 10.1090/S0025-5718-2014-02830-5.**^**Sorenson, Jonathan; Webster, Jonathan (2015). "Strong Pseudoprimes to Twelve Prime Bases".*Mathematics of Computation*.**86**(304): 985â1003. arXiv: 1509.00864. Bibcode: 2015arXiv150900864S. doi: 10.1090/mcom/3134. S2CID 6955806.- ^
^{a}^{b}Caldwell, Chris. "Finding primes & proving primality â 2.3: Strong probable-primality and a practical test".*The Prime Pages*. Retrieved February 24, 2019. **^**Zhang, Zhenxiang & Tang, Min (2003), "Finding strong pseudoprimes to several bases. II",*Mathematics of Computation*,**72**(44): 2085â2097, Bibcode: 2003MaCom..72.2085Z, doi: 10.1090/S0025-5718-03-01545-X**^**Sloane, N. J. A. (ed.). "Sequence A014233 (Smallest odd number for which MillerâRabin primality test on bases <= n-th prime does not reveal compositeness)".*The On-Line Encyclopedia of Integer Sequences*. OEIS Foundation.**^**Izykowski, Wojciech. "Deterministic variants of the MillerâRabin primality test". Retrieved February 24, 2019.**^**Alford, W. R.; Granville, A.; Pomerance, C. (1994), "On the difficulty of finding reliable witnesses" (PDF),*Lecture Notes in Computer Science*, Springer-Verlag,**877**: 1â16, doi: 10.1007/3-540-58691-1_36, ISBN 978-3-540-58691-3**^**Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF).*Mathematics of Computation*.**35**(152): 1391â1417. doi: 10.1090/S0025-5718-1980-0583518-6. MR 0583518.**^**Burthe Jr., Ronald J. (1996), "Further investigations with the strong probable prime test" (PDF),*Mathematics of Computation*,**65**(213): 373â381, Bibcode: 1996MaCom..65..373B, doi: 10.1090/S0025-5718-96-00695-3

## External links

*Algorithm Implementation*has a page on the topic of:

**Primality testing**-
Weisstein, Eric W.
"Rabin-Miller Strong Pseudoprime Test".
*MathWorld*. - Interactive Online Implementation of the Deterministic Variant (stepping through the algorithm step-by-step)
- Applet (German)
- MillerâRabin primality test in C#
- MillerâRabin primality test in JavaScript using arbitrary precision arithmetic