Teste de primalidade de Fermat

Keywords: Teste de primalidade de Fermat, Máximo divisor comum, Número primo, Pierre de Fermat, Pseudoprimo

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

(Assuma-se $m d c (a, b)$ como o Máximo divisor comum entre $a$ e $b$ ).

Se $m$ é primo, então para qualquer $a$ tal que $m d c (a, m) = 1$ , temos:

$a^{m-1} = 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 $m d c (a, m) = 1$ e

$a^{m-1} = 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.

Contrapartidas

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 = 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 4^r. Se $m$ passar o teste para 100 bases diferentes, então a probabilidade de $m$ ser composto é menor que 10^-60.

Ver Também

Pseudoprimalidade