Página dos Números Primos
 
Página projecto da cadeira de ICM do DEFCUL
  

Algoritmos para calcular números primos

No artigo 329 de Disquisitiones Arithmeticae, Gauss (1801), escreveu:
 
" O problema da distinção de números primos, dos números compostos e a resolução posterior destes últimos, nos seus factores primos, é conhecido como um dos mais importantes e úteis da/na aritmética. Tem inspirado a sabedoria e o trabalho de anciãos e modernos geometras, a uma extensão tal que eu seria supérfluo a discutir esse assunto extensivamente …. Mais, a dignidade da ciência  só por si, parece requerer, todos e quaisquer meios, com vista, a explorar a solução de um problema tão elegante e tão célebre."
Apesar do que Gauss escreveu, o reconhecimento da primalidade de um número ou a procura da factorização de números muito grandes, pode ao início parecer como um exercício pontual. No entanto é uma sensação errada. A factorização e a primalidade de um número têm-se tornado muito importantes na criptografia da chave pública, e esta representa, hoje em dia, uma das aplicações mais imediatas  da teoria dos números nas comunicações. Mais pode ser dito sobre a factorização. Eis uma transcrição de uma carta de um famoso teoricista dos números, Brillhart:
 
" É irrelevante para um teoricista dos números, quem trabalha com exemplos; sendo a capacidade da factorizar como uma das mais importantes  das técnicas analíticas, porque o segredo do problema passa pela revelação (e apenas quando) se descobrem os factores primos dos números em questão, pela sua factorização. Eu sei que muitas pessoas - de facto a maioria das pessoas - não se apercebe disso, porque nunca foram confrontados realisticamente com a necessidade de saber a factorização de alguns números; mas eu asseguro-vos, que quando precisarem de tal, ficarão completamente frustados pelo facto de o não conseguirem, porque os números serão grandes demais para serem factorizados. Não é uma questão de desporto ou de excentricidade."
A primeira observação no que concerne ao problema de primalidade e factorização é claro : existe um algoritmo para cada problema. Por algoritmo, entende-se um processo envolvendo uma quantidade finita de passos, aplicáveis a qualquer número N e que nos vão indicar se N é um número primo, ou, se N é composto, e quais são os seus factores primos. Nomeadamente, dado um número natural N, tenta-se sucessivamente cada número n = 2, 3, … até N1/2  (o maior inteiro não superior a N1/2  ), para se tentar perceber se divide N. Se tal não acontecer N é um número primo. Se, digamos, N0 dividir N, escreve-se N = N0N1, com N1 < N, então repete-se o mesmo processo com N0, e N1. Eventualmente tal dar-nos-à a factorização completa de N em números primos.

Note-se no entanto que para N muito grande, pode ser que este algoritmo seja muito demorado, na determinação da sua factorização ou primalidade. Este é o aspecto prático mais importante da tarefa, de achar um algoritmo eficiente, tal que este contenha tão poucas operações quantas as possíveis, e que além disso necessite de menos tempo e menos custo, ao ser realizado.

São apresentados alguns algoritmos: O Crivo de Erastotenes , dois algoritmos de Lucas, um algoritmo de três matemáticos,  Brillhart, Lehmer & Selfridge; algoritmo de Pepin para determinar a primalidade dos números de Fermat (Fn), um algoritmo para determinar a primalidade dos números de Mersenne (Mn).
 


 [Página anterior]   [Página inicial] [Próxima página]

O crivo de Erastotenes

Como já foi analisado anteriormente , é possível saber-se se N é um número primo utilizando divisões triviais para cada número n tal que n2  seja menor ou igual a N. Tendo em conta que a multiplicação é uma operação mais fácil de realizar do que a divisão, Erastotenes (no século III a.C.) teve a brilhante ideia de organizar estas maravilhosas computações, na forma de um bem conhecido crivo. Tal crivo, serve para determinar todos os números primos, assim como as factorizações dos números compostos, até um dado número N. Vamos ilustrar para N= 101.
 
Seguem-se os seguintes passos:

1. Escrevem-se todos os números até 101
2. Cortam-se, com um traço, todos os múltiplos de 2;
3. A cada passo seguinte cortam-se todos os números múltiplos do seguinte menor número restante de p, que seja maior do que p.
4. É suficiente fazê-lo até p2 < 101.

Embora todos os múltiplos de 2,3,5,7 < 1011/2 sejam cortados, resta-nos número 53, que é primo pois ficou sem ser cortado na tabela.

Então os números primos até 101 são, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101.

[Próximo algoritmo]

  [Voltar ao topo]

Algoritmos de Lucas

Este algoritmos são baseados no Pequeno Teorema de Fermat (para distinguir do  denominado Grande Teorema de Fermat).Que diz que: Seja n um número primo então para qualquer número inteiro a, tem-se que : ap ºa (mód. p)

Algoritmo de Lucas de 1876:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. aN-1º1 (mód. N),
2. am ¹1 (mód. N), para m =1,2, ..., N - 2.

Então N é um número primo.

Defeitos do algoritmo: pode parecer perfeito, mas requer N-2 sucessivas multiplicações por a, e a busca dos resíduos do módulo N : Demasiadas operações.

Algoritmo de Lucas de 1891:

Seja N>1. Assuma-se que existe um inteiro a>1 tal que:

1. aN-1 º1 (mód. N).
2. am ¹1 (mód. N) para cada m<N, tal que m seja divisor de N-1.

Então N é um número primo.

Defeitos apresentados por este algoritmo: requer o conhecimento prévio de todos os factores de N-1, embora seja fácil de aplicar quando N é da forma N= 2n + 1 ou quando N=3.2n  + 1.
 


[Algoritmo anterior]  [Próximo algoritmo]

 [Voltar ao topo]

Algoritmo de Brillhart, Lehmer & Selfridge

Em 1927, Lehmer tornou o algoritmo de Lucas datado de 1891 mais prático, mas este foi ainda tornado mais flexivel por Brillhart, Lehmer & Selfridge em 1975:

Algoritmo de Brillhart, Lehmer & Selfridge:

Seja N>1. Assuma-se que para cada factor primo q de N-1 existe um inteiro a = a(q)>1 tal que:

1. aN-1 º1 (mód. N).
2. a(N-1)/q ¹1 (mód.N).

Então N é um número primo.

Defeitos do algoritmo: mais uma vez, é necessário conhecer os factores primos de N-1, mas poucas congruências têm de satisfeitas.

[Algoritmo anterior] [Próximo algoritmo]

 [Voltar ao topo]

Algoritmo de Pepin para testar a primalidade dos números de Fermat


Como os números de Fermat (Fn  = 22^n +1) crescem muito rapidamente em função de n, torna-se muito laborioso testar a sua primalidade. No entanto Pepin obteve em 1877 um algoritmo para testa a primalidade de números de Fermat.

Algoritmo de Pepin:

Seja Fn  = 22^n +1, com n³2, e k³2. Então as seguintes condições são equivalentes:

1. Fn é um número primo e (k/Fn ) = -1;
2.  k(Fn -1)/2º -1 (mód.  Fn ).

Este algoritmo é praticamente uma aplicação da fórmula de Euler para os factores de Fn(Euler demonstrou que todos os factores de Fn , com n³2, são da forma k x 2n+2+1 e através do qual descobriu que 641 divide F5 : F5 = 641 x 6 700 417) . No entanto se Fn é composto este não nos indica qualquer factor deste.

[Algoritmo anterior] [Próximo algoritmo]

 [Voltar ao topo]

Algoritmo para testar a primalidade de números de Mersenne

Os números da forma Mn = 2n-1 com n um número primo são chamados de números de Mersenne, a sua consideração deriva do estudo de números perfeitos (um número perfeito, é um número cujo resultado da soma dos seus divisores naturais é ele mesmo; por exemplo o número 6 tem como divisores 1,  2,  3 e 1+2+3=6, 28 tem como divisores 1, 2, 4, 7, 14 e 1+2+4+7+14=28) efectuado por Marin Mersenne.

Algoritmo:

Mn =2n + 1 é um número primo se e só se Mn divide Sn-2, com (Sk)k³1, uma sucessão definida recursivamente por :
S0= 4, Sk+1=Sk2 -2.

[Algoritmo anterior]

 [Voltar ao topo]