Primalidade e polinômios de Chebyshev
Visualizar/abrir
Data
2000Autor
Orientador
Nível acadêmico
Mestrado
Tipo
Resumo
Este trabalho faz uma relação entre primalidade de números inteiros e os polinômios de Chebyshev, estudando resultados recentemente descobertos. Um dos principais resultados é uma generalização do Pequeno Teorema de Fermat, que mostra a congruência, Tn(a) =a ( mod n) para n primo, em que Tn(x) é o n- ésimo polinômio de Chebyshev. A recíproca desse resultado, se verdadeira, conduziria a um teste de primalidade determinístico eficiente. Através de cálculo computacional, mostramos que para n < 1,9 ...
Este trabalho faz uma relação entre primalidade de números inteiros e os polinômios de Chebyshev, estudando resultados recentemente descobertos. Um dos principais resultados é uma generalização do Pequeno Teorema de Fermat, que mostra a congruência, Tn(a) =a ( mod n) para n primo, em que Tn(x) é o n- ésimo polinômio de Chebyshev. A recíproca desse resultado, se verdadeira, conduziria a um teste de primalidade determinístico eficiente. Através de cálculo computacional, mostramos que para n < 1,9 x 104 , a recíproca é verdadeira. Além disso, os resultados dessa simulação, podem servir de base para o desenvolvimento de um algoritmo probabilístico para verificação da primalidade. Alguns testes de primalidade existentes na literatura, assim como definições e propriedades algébricas dos polinômios de Chebyshev também são apresentadas. ...
Abstract
This work makes a relation between integer primality and Chebyshev polynomials, discussing recently found results. One of the most important results is a generalization of Fermat's little theorem. lt shows that Tn(a) =a ( mod n ), for n prime, where Tn(x) is the ndegree Chebyshev polynomial. The converse o f this result, if true, would lead to an efficient deterministic primality test. Tbrough a machine computation, we show that for n < 1,9 x 1 04 , the converse is true. The results of this sim ...
This work makes a relation between integer primality and Chebyshev polynomials, discussing recently found results. One of the most important results is a generalization of Fermat's little theorem. lt shows that Tn(a) =a ( mod n ), for n prime, where Tn(x) is the ndegree Chebyshev polynomial. The converse o f this result, if true, would lead to an efficient deterministic primality test. Tbrough a machine computation, we show that for n < 1,9 x 1 04 , the converse is true. The results of this simulation may serve to structure a probabilistic primality testing algorithm. Also, some existent primality tests, as well as definitions and algebraic properties o f Chebyshev polynomials are presented. ...
Instituição
Universidade Federal do Rio Grande do Sul. Instituto de Matemática. Programa de Pós-Graduação em Matemática Aplicada.
Coleções
-
Ciências Exatas e da Terra (5136)Matemática Aplicada (285)
Este item está licenciado na Creative Commons License