Editing Miller–Rabin primality test (section)

=== 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 [[#Accuracy|earlier section]]) and the asymptotic behavior of <math>\Pr(P)</math> (shown just before), this error measure can be given a coarse upper bound:

: <math>\Pr(\lnot P \mid M\!R_k)
<
\Pr(M\!R_k \mid \lnot P) \left( \tfrac{1}{\Pr(P)} - 1 \right)
\leq
4^{-k} \left( \tfrac{\ln2}{2} b - 1 + \mathcal{O}\left(b^{-1}\right) \right).
</math>

Hence, for large enough ''b'', this error measure is less than <math>\tfrac{\ln2}{2} 4^{-k} b</math>. However, much better bounds exist.

Using the fact that the Miller–Rabin test itself often has an error bound much smaller than 4<sup>−''k''</sup> (see [[#Accuracy|earlier]]), [[Ivan Damgård|Damgård]], [[Peter Landrock|Landrock]] and [[Carl Pomerance|Pomerance]] derived several error bounds for the generator, with various classes of parameters ''b'' and ''k''.<ref name="damgård-landrock-pomerance"/> These error bounds allow an implementor to choose a reasonable ''k'' for a desired accuracy.

One of these error bounds is 4<sup>−''k''</sup>, 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<ref name="burthe">{{Citation |last=Burthe Jr. |first=Ronald J. |year=1996 |title=Further investigations with the strong probable prime test |journal=Mathematics of Computation |volume=65 |issue=213 |pages=373–381 |url=https://www.ams.org/journals/mcom/1996-65-213/S0025-5718-96-00695-3/S0025-5718-96-00695-3.pdf |doi=10.1090/S0025-5718-96-00695-3 |bibcode=1996MaCom..65..373B |doi-access=free }}</ref>). Again this simple bound can be improved for large values of ''b''. For instance, another bound derived by the same authors is:
: <math>\left(\frac{1}{7} b^\frac{15}{4} 2^{-\frac b 2}\right) 4^{-k}</math>
which holds for all ''b'' ≥ 21 and ''k'' ≥ ''b''/4. This bound is smaller than 4<sup>−''k''</sup> as soon as ''b'' ≥ 32.