Princípio do Algoritmo:
Miller-Rabin é um teste de primalidade probabilístico baseado em uma extensão do Pequeno Teorema de Fermat. Para um número ímpar n, escreva n-1 como 2^r × d e teste se satisfaz:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Número de rodadas de teste e precisão:
- Teste Probabilístico:Seleciona aleatoriamente uma base a; cada rodada de teste reduz a taxa de erro para 1/4
- k rodadas de teste:Taxa de erro teórica ≤ (1/4)^k, a taxa de erro real é muito menor
- Teste Determinístico:Para n < 3.317.044.064.679.887.385.961.981, usando o conjunto de bases específico {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} obtém resultados 100% precisos
Casos Especiais:
- Primos Pequenos:Números como 2, 3, 5, 7 são identificados diretamente
- Números Pares:Todos os números pares exceto 2 são compostos
- Números de Carmichael:Números que passam no teste de Fermat mas são realmente compostos (ex.: 561) podem ser corretamente identificados pelo Miller-Rabin