The Error Probability of the Miller–Rabin Primality Test
- Авторы: Ishmukhametov S.1, Rubtsova R.1, Savelyev N.1
-
Учреждения:
- Institute of Computer Mathematics and Informational Technologies
- Выпуск: Том 39, № 7 (2018)
- Страницы: 1010-1015
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202836
- DOI: https://doi.org/10.1134/S1995080218070132
- ID: 202836
Цитировать
Аннотация
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 \).
Об авторах
S. Ishmukhametov
Institute of Computer Mathematics and Informational Technologies
Автор, ответственный за переписку.
Email: Shamil.Ishmukhametov@kpfu.ru
Россия, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
R. Rubtsova
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Россия, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008
N. Savelyev
Institute of Computer Mathematics and Informational Technologies
Email: Shamil.Ishmukhametov@kpfu.ru
Россия, ul. Kremlevskaya 18, Kazan, Tatarstan, 420008