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