El desarrollo de un algoritmo eficaz en busca de fuertes números pseudoprimos
Palabras clave:
Números estrictamente pseudoprimos, números fuertemente pseudo-simples, algoritmo para construir números estrictamente pseudoprimos, prueba de Miller-Rabin, forma especial de un número.Resumen
El problema de la búsqueda de números estrictamente pseudoprimos es relevante en el campo de la teoría de números, y también tiene varias aplicaciones en criptografía: en particular, con la ayuda de números en esta clase se puede fortalecer la eficiencia de la simplicidad de Miller-Rabin Prueba transformándolo de probabilístico en determinístico. En la actualidad, se conocen varios algoritmos para construir secuencias de tales números, pero tienen una complejidad bastante alta, lo que hace imposible obtener números estrictamente pseudoprimos de gran magnitud en un tiempo aceptable. El tema de este artículo es la construcción de números estrictamente pseudoprime de la forma especial n = pq = (u + 1) (2u + 1), donde p, q son números primos, u es un número natural. Los números de este tipo están presentes en la secuencia ?k, utilizada para estimar el número de iteraciones en la prueba de simplicidad de Miller-Rabin. Denotamos por Fk el número compuesto impar más pequeño del tipo mencionado anteriormente, que pasa con éxito la prueba de Miller-Rabin con k primeros números primos. El documento propone un nuevo algoritmo para construir números Fk, proporciona datos sobre su velocidad y eficiencia en la memoria utilizada y especifica las características de la implementación del software.
Descargas
Citas
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.
Descargas
.gif)
