Teste de primalidade de Miller–Rabin
A calculadora verifica se o número é primo ou não através do teste de primalidade de Miller–Rabin
Esta calculadora verifica se um inteiro é um número primo utilizando o teste de primalidade de Miller–Rabin. O teste utiliza uma série de números inteiros como bases de teste, que também são chamadas de testemunhas de teste. As testemunhas de teste podem ser obtidas de duas maneiras - sendo inseridas ou geradas aleatoriamente. Se o teste retornar não, o número fornecido é definitivamente composto; se o teste retornar sim, o número é primo com alta probabilidade. Quanto maior o número de testemunhas, melhor a precisão do teste. Você pode entender melhor a saída detalhada da calculadora através da leitura sobre os princípios do algoritmo de Miller–Rabin descritos logo abaixo da calculadora.
Teste de primalidade de Miller–Rabin
Algoritmo do teste de primalidade de Miller–Rabin
Para aplicar o teste de primalidade de Miller–Rabin a um número inteiro ímpar n, representamos um número inteiro par n-1 como 2sd, onde d - inteiro ímpar, s - potência inteira de 2. Nós obtemos os números s e d dividindo sequencialmente n-1 por 2 até que o resto seja ímpar.
Em seguida, verificamos sequencialmente, se uma das seguintes opções é verdadeira:
onde:- a - uma testemunha de teste, número inteiro no intervalo [2..n-1]
- r - um número natural menor que s.
Se pelo menos uma condição for atendida, então o a escolhido é uma testemunha de primalidade do número n, e o número n pode ser primo com alta probabilidade. Para aumentar essa probabilidade, nós repetimos o teste para outras bases a geradas aleatoriamente.
Se ambas as condições não forem atendidas, então o número n é composto e os testes futuros podem ser interrompidos.
O teste de primalidade de Miller–Rabin lida com sucesso com os números de Carmichael, que não são viáveis para o teste de primalidade de Fermat.
Por exemplo, o número 29341, erroneamente declarado pelo teste de Fermat como primo, é determinado como um composto pelo teste Miller–Rabin.
Ao contrário do teste de Fermat, não há números de teste "ruins" para o teste de Miller–Rabin. Para qualquer número, o teste fornece a resposta correta com alta probabilidade. O resultado incorreto do algoritmo é determinado apenas por uma escolha aleatória de testemunhas de teste, cuja probabilidade é pequena1.
De acordo com a pesquisa de Rabin, não mais do que um quarto dos números no intervalo [1..n-1] não são testemunhas2 (isto é, eles dão um resultado errôneo no teste de Miller–Rabin). Portanto, a probabilidade de erro final do teste da rodada-k é menor que 1/4k.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to algorithms (Introdução aos algoritmos)
Comentários