Algoritmos Eficientes para Geração de Números Primos
Dr. Orion de Oliveira Silva
Departamento de Computação
Universidade Braz Cubas
E-mail: [email protected]
Ricardo Teixeira de Carvalho, PhD
Instituto de Estudos Avançados
Centro Técnico Aero-Espacial
De
partamento de LASER
RESUMO
Existem vários métodos computacionais para
se encontrar os números primos. Neste artigo
nós propusemos algoritmos baseados no
teorema: “Se um número é primo, então ele é
da
forma
6.k+1
ou
6.k-1,
onde
k=1,2,3,...”.Criamos estes algoritmos para
aqueles que procuram números primos
gigantes (com mais de 10.000.000 de dígitos),
para uso em criptografia. O algoritmo
proposto para gerar números primos foi
confrontado com o algoritmo que usa crivo de
Eratóstene, e se mostrou mais eficiente
computacionalmente.
Também
serão
apresentado alguns teoremas e funções de “k”
que fazem que as fórmulas 6.k+1 e 6.k-1
gerem números que não são primos e por
conseqüência o complemento desse conjunto
gerado é o conjunto dos números primos.
Referencias
[1] Hardy, G. H. and Wright, E. M. An
Introduction to the Theory of Numbers,
Oxford: Oxford University Press, first
edition 1938, fifth edition 1979.
[2] Rosen, K. H. Elementary Numbers Theory
and its Application, Reading, Mass.:
Addison- Wesley., second edition, 1988.
[3] Niven, I., Zuckerman, H. S. and
Montgomery, H. L. And Introduction to
the Theory of Numbers, New York: Jonh
Wiley, fifth edition, 1991.
[4] Giblin, P. Primes and Programming: An
Introduction to Number Theory with
Computing. Cambridge University Press,
1984.
[5] Agrawal, M., Kayal, N. Saxema,
N.PRIMES is in P. Department of
Computer Science & Engineering, Indian
Institute of Technology Kanpur, Kanpur208016, INDIA. August 6. 2002.