O desenvolvimento de um algoritmo eficiente em busca de números pseudo-primos fortes
Palavras-chave:
Números estritamente pseudoprimarios, números fortemente pseudo-simples, algoritmo para construção de números estritamente pseudoprimarios, teste de Miller-Rabin, forma especial de um número.Resumo
O problema de encontrar números pseudoprimos é estritamente relevante no campo da teoria dos números, e também tem muitas aplicações em criptografia: em particular, com a ajuda de números nesta classe pode fortalecer a eficiência da simplicidade de Miller Teste de Rabin transformando-o de probabilístico para determinístico. Atualmente, vários algoritmos são conhecidos por construir seqüências de tais números, mas eles têm uma complexidade bastante alta, o que torna impossível obter números estritamente pseudoprimo de grande magnitude em um tempo aceitável. O assunto deste artigo é a construção de números estritamente pseudoprimo forma especial com n = pq = (L + 1) (2u + 1) em que p, q são números primos, u é um número natural. Números desse tipo estão presentes na seqüência ?k, usada para estimar o número de iterações no teste de simplicidade de Miller-Rabin. Denotamos por Fk o menor número composto ímpar do tipo mencionado acima, que passa com sucesso no teste de Miller-Rabin com k primeiros números primos. O documento propõe um novo algoritmo para a construção de números Fk, fornece dados sobre sua velocidade e eficiência na memória utilizada e especifica as características da implementação do software.
Downloads
Referências
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.
Downloads
.gif)
