Por que Miller – Rabin em vez do teste de primalidade de Fermat?

A partir da prova de Miller-Rabin , se um número passa no teste de primalidade de Fermat , ele também deve passar no teste de Miller-Rabin com a mesma base (uma variável na prova). E a complexidade da computação é a mesma.$a$

O seguinte é do teste de primalidade de Fermat :

Embora os números de Carmichael sejam substancialmente mais raros que os números primos, 1 existem o suficiente para que o teste de primalidade de Fermat geralmente não seja usado na forma acima. Em vez disso, outras extensões mais poderosas do teste de Fermat, como Baillie-PSW, Miller-Rabin e Solovay-Strassen, são mais comumente usadas.

Qual é o benefício de Miller-Rabin e por que se diz ser mais poderoso que o teste de primalidade de Fermat?

O algoritmo de Rabin-Miller também testa, dado um número , se Z n tem uma raiz não trivial do Unity.$n$$Z_n$

Números Carmichael passar no teste Fermat (para cada base ), mas para cada número Carmichael n , existem muitos números de uma tal forma que o teste para raízes unidade falha em um (isto é, a sequência de um , dois um , . . . , 2 r a eventualmente exibe uma raiz não trivial da unidade).$a$$n$$a$$a$$a,2a,...,2^ra$

Assim nós temos o seguinte:

Para o teste de Fermat, se um número composto não é Carmichael, então a probabilidade de que o teste irá detectar compositeness é de pelo menos 1 / 2 . No entanto, o teste falhará em todos os números de Carmichael.$n$$1/2$

Para o teste de Rabin-Miller, cada número composto será detectado com probabilidade de pelo menos . Isso significa que a probabilidade de correção é independente da entrada (não há entradas "rígidas"). É isso que torna esse algoritmo mais forte.$1/2$

Acredito que sua afirmação é o oposto do que acontece. Passar no teste de Miller-Rabin para uma determinada base significa que passará no teste de Fermat para a mesma base. Por outro lado, existem muitos compostos que passarão no teste de Fermat para uma determinada base, mas serão reprovados no teste de Miller-Rabin para a mesma base.

Veja, por exemplo, o artigo de Pomerance / Selfridge / Wagstaff na página da Wikipedia Miller-Rabin:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

onde vemos um diagrama na página 2, mostrando os pseudoprimes de Euler sendo um subconjunto dos pseudoprimes de Fermat e os pseudoprimes fortes sendo um subconjunto desses. O teste de Solovay-Strassen é, portanto, mais exigente que o teste de Fermat, e o teste de Miller-Rabin, mais do que qualquer um. Ambos evitam o problema crítico dos números de Carmichael. Eles têm essencialmente o mesmo desempenho, portanto, preferimos usar o teste de Miller-Rabin.

Deveria ser óbvio que Miller-Rabin é melhor que Fermat.

$a^{p-1}$

Com o teste de Miller-Rabin, para calcular , encontramos k e s ímpares tais que $a^{p-1}$$p-1 = s·2^k$$a^s$$a^{p-1}$

Novamente, se o resultado não for 1 (módulo p), então p é composto. Mas se o resultado for 1 módulo p, verificamos se obtivemos 1 ao quadrado de um resultado intermediário que não era +1 ou -1 e, nesse caso, x também é comprovadamente composto.

Portanto, fazemos exatamente a mesma quantidade de trabalho, mas há mais maneiras de provar que x é composto.