An Intelligent Choice of Witnesses in the Miller–Rabin Primality Test. Reinforcement Learning Approach
Tóm tắt
The problem of testing natural numbers for primality is an important problem for the Theory of Numbers and Cryptography. The main instrument of Cryptography to determine, if a given odd integer is prime or composite, is the Miller–Rabin primality test. The latter is a probabilistic iterative algorithm consisting of rounds.At each round a special parameter
$$a,\,2\leq a
Tài liệu tham khảo
M. Agrawal, N. Kayal, and N. Saxena, ‘‘Primes is in P,’’ Ann. Math. 160, 781–793 (2002).
R. Baillie, A. Fiori, and S. S. Wagstaff, Jr., ‘‘Strengthening the Baillie-PSW primality test’’ Math. Comput. 90, 330 (2021).
R. Bellman, ‘‘A markovian decision process,’’ Indiana Univ. Math. J., No. 6, 679–684 (1957).
H. Cohen and H. W. Lenstra, ‘‘Primality testing and Jacobi sums,’’ Math. Comput. 42, 297–330 (1984).
R. Crandall and C. B. Pomerance, Prime Numbers: A Computational Perspective, Lecture Notes in Statistics (Springer, New York, 2006).
S. Ishmukhametov, B. Mubarakov, and R. Rubtsova, ‘‘On the number of witnesses in the Miller–Rabin primality test,’’ Symmetry 12, 890 (2020).
N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev, ‘‘Reinforcement learning for combinatorial optimization: A survey,’’ Comput. Operat. Res. 134, 105400 (2021).
G. L. Miller, ‘‘Riemann’s hypothesis and tests for primality,’’ J. Comput. Syst. Sci. 13, 300–317 (1976).
F. Morain, ‘‘Atkin’s test: News from the front,’’ Adv. Cryptol. 434, 626–635 (1989).
F. Morain, Elliptic Curves for Primality Proving. Encyclopedia of Cryptography and Security (Springer, New York, 2005).
M. J. Nelson and A. K. Hoover, ‘‘Notes on using google collaboratory in AI education,’’ in Proceedings of the ACM ITiCSE (2020), pp. 533–534.
M. O. Rabin, ‘‘Probabilistic algorithm for testing primality,’’ J. Number Theory 12, 128–138 (1980).
J. Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, T. P. Lillicrap, and D. Silver, ‘‘Mastering atari, go, chess and shogi by planning with a learned model,’’ CoRR, abs/1911.08265 (2019).
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, ‘‘Proximal policy optimization algorithms,’’ CoRR, abs/1707.06347 (2017).
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, et al., ‘‘Mastering the game of go with deep neural networks and tree search,’’ Nature (London, U.K.) 529 (7587), 484–489 (2016).
R. S. Sutton and A. G. Barto, Reinforcement Learning—An Introduction. Adaptive Computation and Machine Learning (MIT Press, Boston, MA, 1998).
S. Wolfram, Mathematica—A System for Doing Mathematics by Computer (Addison-Wesley, Boston, 1988).
Z. Zhang, ‘‘Finding c3-strong pseudoprimes,’’ Math. Comput. 74 (250), 1009–1024 (2005).
Z. Zhang, ‘‘Notes on some new kinds of pseudoprimes,’’ Math. Comput. 75 (253), 451–460 (2006).
Z. Zhang, ‘‘Two kinds of strong pseudoprimes up to 1036,’’ Math. Comput. 76 (260), 2095–2107 (2007).
Z. Zhang and M. Tang, ‘‘Finding strong pseudoprimes to several bases II,’’ Math. Comput. 72 (244), 2085–2097 (2003).