Teste de primalidade de Fermat

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Teorema de Fermat, que originou o Teste de primalidade de Fermat, oferece um teste simples e eficiente para ignorar números não-primos. Qualquer número que falhe o teste não é primo.

Teorema[editar | editar código-fonte]

(Assuma-se \operatorname{mdc}(a,b) como o Máximo divisor comum entre a e b).

Se m é primo, então para qualquer a tal que \operatorname{mdc}(a,m)=1, temos:

a^{m-1} \equiv 1 \pmod m

Se m não é primo, ainda é possível (embora pouco provável) que o supradito se verifique.

Se m é ímpar composto, e a um inteiro tal que \operatorname{mdc}(a,m)=1 e

a^{m-1} \equiv 1 \pmod m

diz-se que m é pseudoprimo para a base a, i.e., é um número não primo que passa o teste de Fermat.

Prova do teorema[editar | editar código-fonte]

Seja \operatorname{mdc}(a,m) = 1,

consideramos os conjuntos \{1 ,2 ,3, \ldots ,m-1 \} e \{a ,2a ,3a, \ldots ,(m-1)a \}

e percebemos que \{a ,2a ,3a, \ldots ,(m-1)a \}\not\equiv 0\pmod m.

Seja i, j \in \{1 ,2 ,3, \ldots ,m-1 \} e ia \equiv ja\pmod m

vemos que i \equiv j\pmod m

porque \operatorname{mdc}(a,m) = 1,

com isso i = j

porque 0 \le |i -  j| < m,

então os números \{a ,2a ,3a, \ldots ,(m-1)a \}\not\equiv 0\pmod m
são incongruentes entre si \pmod{m}.

Então \{a ,2a ,3a, \ldots ,(m-1)a \} são congruentes, em alguma ordem, com os números 1, 2, 3, \ldots ,m -1.

Conclui-se que:

(m - 1)! = 1\cdot 2\cdot 3\cdot 4 \cdots (m - 1) \equiv a\cdot 2a\cdot 3a\cdot 4a \cdots (m - 1)a \implies (m - 1)! \equiv a^{m - 1}\cdot(m - 1)!\pmod m

Já que

\operatorname{mdc}(m,(m - 1)!) = 1
podemos cancelar o fator (m - 1)! , e obtemos:
a^{m-1}\equiv 1\pmod m
o que conclui a prova.

Contrapartidas[editar | editar código-fonte]

Infelizmente existem números que passam o teste de Fermat para todas as bases para as quais são relativamente primos – são os chamados números de Carmichael, e são infinitos. Como tal, pode-se fazer o Teste de pseudoprimalidade forte:

  • Dado m
  • Escreve-se m-1 = 2^8t\,\!, em que t é ímpar
  • Escolher aleatoriamente a \in [1,m[
  • Calcular h \equiv a^t \pmod {m}\,\!
  • Se h = \pm 1, então m passa
  • Calcular h^i = a^{(2^i)t} para i = 1,2,...,8
  • Se h^i = -1\,\! para algum i<8, então m passa
  • Caso contrário m falha.

O teste deve ser repetido para r bases diferentes. A probabilidade de um número composto m passar r testes é de 1 em 4r. Se m passar o teste para 100 bases diferentes, então a probabilidade de m ser composto é menor que 10−60.

Um teste elementar e preciso de primalidade[editar | editar código-fonte]

Sabe-se que, com exceção dos números 2 e 3, todos os outros números primos são expresso pela fórmula Ip=6K±1. Mas sabe-se que a imensa maioria dos números expresso pela fórmula Ip=6K±1 não são números primos. O estudo dos não-primos da forma Ip=6K±1 leva à igualdade

K=6k2k3±k2±k3.

Então: dado um número inteiro positivo qualquer K, se não ocorrer nenhum par de números inteiros positivos k2,k3 que satisfaça a igualdade acima, afirma-se que os números Ip=6K±1 são números primos gêmeos.

Se não ocorrer nenhum par k2,k3 com sinais iguais e ocorrer ao menos um par k2,k3 com sinais diferentes que satisfaça a equação, afirma-se que Ip=6K+1 é primo e Ip=6K-1 não é primo.

Se não ocorrer nenhum par k2,k3 com sinais diferentes e ocorrer ao menos um par k2,k3 com sinais iguais que satisfaça a equação, afirma-se que Ip=6K-1 é primo e Ip=6K+1 não é primo.

Ver também[editar | editar código-fonte]