Email this article GCD calculation in the search task of pseudoprime and strong pseudoprime numbers
- Authors: Dolgov D.1
-
Affiliations:
- Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
- Issue: Vol 37, No 6 (2016)
- Pages: 734-739
- Section: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198444
- DOI: https://doi.org/10.1134/S1995080216060111
- ID: 198444
Cite item
Open Access
Access granted
Subscription Access
Abstract
Integer n is called pseudoprime (psp) relative to base a if n is composite, (a, n) = 1, and an−1 mod n = 1. Integer n is called strong pseudoprime (spsp) relative to base a if n is composite, (a, n) = 1, and, ad 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.
About the authors
D. Dolgov
Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
Author for correspondence.
Email: Dolgov.kfu@gmail.com
Russian Federation, Kremlevskaya ul. 35, Kazan, Tatarstan, 420008
