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