An Intelligent Choice of Witnesses in the Miller–Rabin Primality Test. Reinforcement Learning Approach
Nikolai Andreevich Antonov, Sh. T. Ishmukhametov · Lobachevskii Journal of Mathematics · 2022
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