The Error Probability of the Miller–Rabin Primality Test
- Autores: Ishmukhametov S.1, Rubtsova R.1, Savelyev N.1
-
Afiliações:
- Institute of Computer Mathematics and Informational Technologies
- Edição: Volume 39, Nº 7 (2018)
- Páginas: 1010-1015
- Seção: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202836
- DOI: https://doi.org/10.1134/S1995080218070132
- ID: 202836
Citar
Resumo
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 \).
Sobre autores
S. Ishmukhametov
Institute of Computer Mathematics and Informational Technologies
Autor responsável pela correspondência
Email: Shamil.Ishmukhametov@kpfu.ru
Rússia, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
R. Rubtsova
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Rússia, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
N. Savelyev
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Rússia, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
![](/img/style/loading.gif)