The development of an effective algorithm searching for strong pseudoprime numbers

Nikolai A. Antonov

Nikolai A. Antonov Kazan Federal University

Keywords: Strictly pseudoprime numbers, strongly pseudo-simple numbers, algorithm for constructing strictly pseudoprime numbers, Miller-Rabin test, special form of a number

Abstract

The problem of searching for strictly pseudoprime numbers is relevant in the field of number theory, and it also has a number of applications in cryptography: in particular, with the help of numbers in this class one can strengthen the efficiency of the Miller-Rabin simplicity test by transforming it from probabilistic into deterministic. At the present time, several algorithms for constructing sequences of such numbers are known, but they have a rather high complexity, which makes it impossible to obtain strictly pseudoprime numbers of large magnitude in an acceptable time. The theme of this paper is the construction of strictly pseudoprime numbers of the special form n = pq = (u + 1) (2u + 1), where p, q are prime numbers, u is a natural number. Numbers of this kind are present in the sequence Ψk, used to estimate the number of iterations in the Miller-Rabin simplicity test. We denote by Fk the smallest odd composite number of the above-mentioned type, which successfully passes the Miller-Rabin test with k first prime numbers. The paper proposes a new algorithm for constructing Fk numbers, gives data on its speed and efficiency on the memory used, and specifies the features of the software implementation.

Downloads

Download data is not yet available.

Author Biography

Nikolai A. Antonov, Kazan Federal University

Kazan Federal University

References

Crandall R., Pomerance K. (2011). The prime numbers: Cryptographic and computational aspects. Trans. from English / Ed. and with an introduction by V.N. Chubarikov. - Moscow.: USSR: Book House "LIBROKOM", 664 p.

Crandall R., Pomerance K. (2005). The prime numbers: a computational perspective. – 2nd Ed., Springer-Verlag, Berlin, 604 p.

Sh. T. Ishmukhametov. (2011). Methods of factorization of natural numbers: a tutorial. - Kazan, KFU, 190 p.

Sh. T. Ishmukhametov, B.G. Mubarakov. (2014). On a class of strictly pseudoprime number // Heuristic Algorithms and Distributed Computing. - Book 1, No. 1, P. 64-73.

S. Ishmukhametov, B. Mubarakov. (2013). On practical aspects of the Miller-Rabin Primality Test // Lobachevskii Journal of Mathematics. – Vol. 34, No. 4, P.304–312.

C. Pomerance, C. Selfridge, S. Wagstaff. (1980). The Pseudoprimes to 25*109 // Math. Comput. P. 1003-1026.

G. Jaeschke. (1993). On Strong Pseudoprimes to Several Bases // Math. Comput. 61. P. 915-926.

J. Jiang, Y. Deng. (2012). Strong pseudoprimes to the first 9 prime bases // ArXiv:1207.0063v1 [math.NT]. P.1–12.

J. Jiang, Y. Deng. (2012). Strong pseudoprimes to the first 9 prime bases // ArXiv:1207.0063v1 [math.NT]. P.1–12.

STRONG PSEUDOPRIMES TO TWELVE PRIME BASES JONATHAN SORENSON AND JONATHAN WEBSTER Date: September 4, 2015. 2010 Mathematics Subject Classi_cation. Primary 11Y16, 11Y16; Secondary 11A41, 68W40, 68W10.

Ivan B. Damgard, Peter Landrock, and Carl Pomerance. (1993). Average case error estimates for the strong probable prime test. Math. Comp. 61(203), P. 177-194.

Golovchun A., Karimova B., Zhunissova M., Ospankulova G., Mukhamadi K. (2017). Content And Language Integrated Learning In Terms Of Multilingualism: Kazakhstani Experience, Astra Salvensis, Supplement No. 10, p. 297-306.

Villalobos Antúnez J.V. (2013). José Vicente Villalobos Antúnez. Opcón, 29 (72), Pp. 10-19.