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 ∈ P ) ≥ 0 , 75 {\displaystyle P(n\in \mathbb {P} )\geq 0,75} , sendo que P {\displaystyle \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 {\displaystyle n} um número primo e a {\displaystyle a} um número inteiro escolhido aleatoriamente, tal que 1 < a < n {\displaystyle 1<a<n} . Seja s = max { r ∈ N : 2 r d i v i d e ( n − 1 ) } {\displaystyle s=\max\{r\in \mathbb {N} :2^{r}divide(n-1)\}} . s {\displaystyle s} é o maior expoente, tal que 2 s ∣ ( n − 1 ) {\displaystyle 2^{s}\mid (n-1)} .

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

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

a d ≡ 1 mod n {\displaystyle a^{d}\equiv 1\mod n}

ou, existe um r ∈ { 0 , 1 , ⋯ , s − 1 } {\displaystyle r\in \{0,1,\cdots ,s-1\}} , tal que

a 2 r d ≡ − 1 mod n {\displaystyle a^{2^{r}d}\equiv -1\mod n}

Um número a {\displaystyle a} que não satisfaz o teorema acima é denominado de testemunha contra a primalidade de n {\displaystyle n} .