v. 7 n. 16 (2018)
Articles

O desenvolvimento de um algoritmo eficiente em busca de números pseudo-primos fortes

pdf (English)
  • Nikolai A. Antonov
Nikolai A. Antonov
Kazan Federal University
Biografia do Autor

Kazan Federal  University

Publicado 2018-10-30

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.

Como Citar

Antonov, N. A. (2018). O desenvolvimento de um algoritmo eficiente em busca de números pseudo-primos fortes. Amazonia Investiga, 7(16), 94–100. Recuperado de https://amazoniainvestiga.info/index.php/amazonia/article/view/381

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.

pdf (English)

Downloads

Não há dados estatísticos.

Referências

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.