GCD calculation in the search task of pseudoprime and strong pseudoprime numbers
- Autores: Dolgov D.1
-
Afiliações:
- Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
- Edição: Volume 37, Nº 6 (2016)
- Páginas: 734-739
- Seção: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198444
- DOI: https://doi.org/10.1134/S1995080216060111
- ID: 198444
Citar
Resumo
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.
Palavras-chave
Sobre autores
D. Dolgov
Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
Autor responsável pela correspondência
Email: Dolgov.kfu@gmail.com
Rússia, Kremlevskaya ul. 35, Kazan, Tatarstan, 420008