The Error Probability of the Miller–Rabin Primality Test
- Authors: Ishmukhametov S.T.1, Rubtsova R.1, Savelyev N.1
-
Affiliations:
- Institute of Computer Mathematics and Informational Technologies
- Issue: Vol 39, No 7 (2018)
- Pages: 1010-1015
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202836
- DOI: https://doi.org/10.1134/S1995080218070132
- ID: 202836
Cite item
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 \).
About the authors
S. T. Ishmukhametov
Institute of Computer Mathematics and Informational Technologies
Author for correspondence.
Email: Shamil.Ishmukhametov@kpfu.ru
Russian Federation, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
R. Rubtsova
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Russian Federation, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
N. Savelyev
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Russian Federation, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008