GCD calculation in the search task of pseudoprime and strong pseudoprime numbers

Abstract

Integer n is called pseudoprime (psp) relative to base a if n is composite, (a, n) = 1, and aⁿ⁻¹ 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 = 2^s * 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.