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.

PLANETCALC, Teste de primalidade de Miller–Rabin

Teste de primalidade de Miller–Rabin

Pode ser primo
 
Fator de potência 2
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

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:

  1. a^{d}\equiv 1{\pmod {n}}
  2. a^{2^{r}d}\equiv -1{\pmod {n}}
    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)


  1. Co 

  2. Michael O. Rabin, Probabilistic Algorithm for Testing Primality (Algoritmo Probabilístico para Teste de Primalidade), Journal of number theory (Jornal da Teoria dos Números) 12, 128-138 (1980) 

URL copiado para a área de transferência
PLANETCALC, Teste de primalidade de Miller–Rabin

Comentários