Teste de primitividade de Miller-Rabin
Origem: Wikipédia, a enciclopédia livre.
O teste Miller-Rabin (por Gary Miller e Michael O. Rabin) é um teste probabilistico 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 diminuida aleatoriamente, aplicando-se o teste várias vezes ao mesmo número n.
O teste é parecido com o o teste Solovay-Strassen, portanto sua margem de erro é bem menor.
A importância desse algoritmo se deve à criptografia asimétrica, onde a necessidade de uma grande quantidade de números primos grandes é vital para a segurânça dos algoritmos. Tais números são tão grandes que testes não probabilisticos 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 tabém é chamado, não dá indícios sobre a fatorização no número n. Devido suas caraterísticas, esse teste é o mais utilizado para o teste da primitividade.
[editar] Funcionamento
Seja n um número primo e a um número inteiro escolhido aleatóriamente, tal que 1 < a < p. Seja 
. s é o maior expoente, tal que 
.
Seja d = (n − 1) / 2s. Por definição de s, d é, necessáriamente ímpar.
Teorema: Se n é um número primo e a não tiver um divisor em comum com p, então
ou, existe um 
, tal que
Um número a que não satisfaz o teorema acima é denominado de testemunha contra a primitividade de n.
