Teste de primalidade de Miller–Rabin
O teste Miller-Rabin (por Gary Miller e Michael Rabin) é um teste probabilístico da primitividade de um dado número n. Se um número n não passar pelo teste, n com certeza é um número composto (ou seja, não-primo). Se o número passar no teste, ele é primo, com uma probabilidade , sendo que denomina o conjunto de todos números primos.
A margem de erro pode ser diminuída arbitrariamente, aplicando-se o teste várias vezes ao mesmo número n.
O teste é parecido com o teste Solovay-Strassen, portanto sua margem de erro é bem menor.
A importância desse algoritmo se deve à criptografia assimétrica, onde a necessidade de uma grande quantidade de números primos grandes é vital para a segurança dos algoritmos. Tais números são tão grandes que testes não probabilísticos como o da simples divisão por números primos menores que o número gerado ou o tabelamento de todos os números primos são impraticáveis.
É importante dizer que o teste Miller-Rabin, ou Rabin-Miller, como as vezes também é chamado, não dá indícios sobre a fatoração no número n. Devido suas caraterísticas, esse teste é o mais utilizado para o teste da primalidade.
Funcionamento
[editar | editar código-fonte]Seja um número primo e um número inteiro escolhido aleatoriamente, tal que . Seja . é o maior expoente, tal que .
Seja . Por definição de , é, necessariamente ímpar.
Teorema: Se é um número primo e não tiver um divisor em comum com , então
ou, existe um , tal que
Um número que não satisfaz o teorema acima é denominado de testemunha contra a primalidade de .