GCD calculation in the search task of pseudoprime and strong pseudoprime numbers
Dmitry Aleksandrovich Dolgov · Lobachevskii Journal of Mathematics · 2016
Integer n is called pseudoprime (psp) relative to base a if n is composite, (a, n) = 1, and a n−1 mod n = 1. Integer n is called strong pseudoprime (spsp) relative to base a if n is composite, (a, n) = 1, and, a d mod n = 1, or, $${a^{d{2^i}}}$$ mod n = −1, where n −1 = 2s * d, d is odd, 0 ≤ i < s. Pseudoprime and strong pseudoprime numbers are used in public-key cryptography in probabilistic tests. We use recurrent sequences in the task of search pseudoprime and strong pseudoprime numbers. This article describes acceleration of GCD calculation.