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)