Teste de primalidade de Fermat
Origem: Wikipédia, a enciclopédia livre.
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.
[editar] Teorema
(Assuma-se mdc(a,b) como o Máximo divisor comum entre a e b).
Se m é primo, então para qualquer a tal que mdc(a,m) = 1, temos:
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 mdc(a,m) = 1 e
diz-se que m é pseudoprimo para a base a, i.e., é um número não primo que passa o teste de Fermat.
[editar] 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
, em que t é ímpar - Escolher aleatoriamente
- Calcular
- Se
, então m passa - Calcular
para i = 1,2,...,8 - Se
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.
