Abstract
In our paper we give theoretical and practical estimations of the error probability in the well-known Miller–Rabin probabilistic primality test. We show that a theoretical probability of error 0.25 for a single round of the test is very overestimated and, in fact, error is diminishing with the growth of length of numbers involved by a rate limited with ln n/\(\sqrt n \).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G. L. Miller, “Riemann’s hypothesis and tests for primality,” J. Comput. Syst. Sci. 13, 300–317 (1976).
M. O. Rabin, “Probabilistic algorithm for testing primality,” J. Numb. Theory 12, 128–138 (1980).
R. M. Solovay and V. Strassen, “A fastMonte-Carlo test for primality,” SIAM J. Comput. 6, 84–85 (1977).
R. M. Solovay and V. Strassen, “V. Erratum: A fast Monte-Carlo test for primality,” SIAM J. Comput. 7, 118 (1978).
R. Baillie and S. S. Wagstaff, Jr., “Lucas pseudoprimes,” Math. Comp. 35 (152), 1391–1417 (1980).
R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM 21, 120–126 (1978).
N. Ferguson and B. Schneier, Practical Cryptography (Wiley, Chichester, 2003).
S. Ishmukhametov, Factorization Methods for Natural Numbers (Kazan Federal Univ., Kazan, Russia, 2011) [in Russian].
C. Pomerance, J. L. Selfridg, and S. Wagstaff, Jr., “The pseudoprimes to 25 · 109,” Math. Comp. 35 (151), 1003–1026 (1980).
G. Jaeschke, “On strong pseudoprimes to several bases,” Math. Comp. 61 (204), 915–926 (1993).
J. Yupeng and D. Yingpu, “Strong pseudoprimes to the first eight prime bases,” Math. Comp. 83 (290), 2915–2924 (2014).
Z. Zhang, “Two kinds of strong pseudoprimes up to 1036,” Math. Comp. 76 (260), 2095–2107 (2007).
J. Sorenson and J. Webster, “Strong pseudoprimes to twelve prime bases,” arXiv:1509.00864 [math.NT] (2015).
S. Ishmukhametov and B. Mubarakov, “On practical aspects of the Miller–Rabin primality test,” Lobachevskii J.Math. 34, 304–312 (2013).
S. Ishmukhametov and B. Mubarakov, “On the number of witnesses in the Miller–Rabin primality test,” (to be published).
S. Ishmukhametov and F. F. Sharifullina, On distribution of semiprime numbers, Russ. Math. (Iz. VUZ) 58 (8), 43–48 (2014).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed. (Clarendon, Oxford, 1959).
Author information
Authors and Affiliations
Corresponding author
Additional information
Submitted by F.M. Ablayev
Rights and permissions
About this article
Cite this article
Ishmukhametov, S.T., Rubtsova, R. & Savelyev, N. The Error Probability of the Miller–Rabin Primality Test. Lobachevskii J Math 39, 1010–1015 (2018). https://doi.org/10.1134/S1995080218070132
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080218070132