GCD calculation in the search task of pseudoprime and strong pseudoprime numbers
- Авторы: Dolgov D.1
-
Учреждения:
- Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
- Выпуск: Том 37, № 6 (2016)
- Страницы: 734-739
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/198444
- DOI: https://doi.org/10.1134/S1995080216060111
- ID: 198444
Цитировать
Аннотация
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.
Ключевые слова
Об авторах
D. Dolgov
Department of System Analysis and Information Technologies, Institute of Computational Mathematics and Information Technologies
Автор, ответственный за переписку.
Email: Dolgov.kfu@gmail.com
Россия, Kremlevskaya ul. 35, Kazan, Tatarstan, 420008
![](/img/style/loading.gif)