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