Recentemente, ao ler o SICP, uma nota de rodapé diz:
Os números que enganam o teste de Fermat são chamados de números de Carmichael, e pouco se sabe sobre eles, exceto que são extremamente raros. Existem 255 números de Carmichael abaixo de 100 milhões. Os menores são 561, 1105, 1729, 2465, 2821 e 6601. Ao testar a primalidade de números muito grandes escolhidos aleatoriamente, a chance de encontrar um valor que engane o teste de Fermat é menor do que a chance de que a radiação cósmica cause o computador cometa um erro ao executar um algoritmo “correto”. Considerar um algoritmo inadequado pela primeira razão, mas não pela segunda, ilustra a diferença entre matemática e engenharia.
A nota de rodapé é referida em:
Infelizmente, esta afirmação não é totalmente correta. Existem números que enganam o teste de Fermat : números n que não são primos e ainda assim possuem a propriedade de que an é congruente com a módulo n para todos os inteiros a < n . Esses números são extremamente raros, portanto o teste de Fermat é bastante confiável na prática. [47]
Está falando sobre o algoritmo de teste de Fermat:
; calculate: a^n mod n
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
; check `times` count although it will fail for Carmichael numbers.
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
A Wikipedia tem o acima como referência ao dizer
Em alguns casos, os algoritmos probabilísticos são o único meio prático de resolver um problema.
Alguém que leu este livro poderia me dizer o que significa a última frase da primeira referência?
Talvez este problema não seja apropriado perguntar aqui. Mas como o SICP é sobre programação, perguntei aqui.
Há um pouco de humor nessa citação.
O teste de Fermat, se tomado como um algoritmo para resolver o problema “ N é um número primo?”, teoricamente não está correto .
Não está correto, no sentido de que existem números n para os quais n passa no teste de Fermat, mas n não é primo, então a saída do algoritmo está errada para esses números.
No entanto, o autor ressalta que tais números são extremamente raros: se n for um número aleatório, então a probabilidade de o algoritmo estar errado em n por razões teóricas é menor do que a probabilidade de um computador executando o algoritmo dar o resultado errado para razões físicas absurdamente improváveis.
Então, para chamar o teste de Fermat de “inadequado” porque não se enquadra na definição teórica de correção, é preciso estar um pouco desconectado da realidade. Aqui, "inadequado pela primeira razão" refere-se a "inadequado porque não é teoricamente correto", e "inadequado pela segunda razão" significa "poderia falhar na prática devido à interferência de raios cósmicos na eletrônica", algo com o qual nenhum engenheiro se importa, exceto talvez Engenheiros da NASA e do CERN.
A conclusão humorística é que um matemático não se preocupa com a execução prática, mas apenas com a correção teórica.
Isso tudo é um pouco irônico. Se você usar o teste de Fermat em um aplicativo, ainda deverá estar ciente de que os números de Carmichael existem e que, se um usuário adversário puder escolher n , o teste de Fermat poderá ser inadequado. Mas se n for verdadeiramente aleatório, não escolhido, então a existência de números de Carmichael não deveria importar para você.