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 $P(n\in \mathbb{P})\ge 0,75$, sendo que $\mathbb{P}$ 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

Seja $n$ um número primo e $a$ um número inteiro escolhido aleatoriamente, tal que $1<a<n$. Seja $s=\max \{r\in \mathbb{N}:2^{r}divide(n-1)\}$. $s$ é o maior expoente, tal que $2^s\mid (n-1)$.

Seja $d=(n-1)/2^s$. Por definição de $s$, $d$ é, necessariamente ímpar.

Teorema: Se $n$ é um número primo e $a$ não tiver um divisor em comum com $n$, então

$a^d\equiv 1modn$

ou, existe um $r\in \{0,1,\cdots ,s-1\}$, tal que

$a^{2^{r}d}\equiv -1modn$

Um número $a$ que não satisfaz o teorema acima é denominado de testemunha contra a primalidade de $n$.