Teste Miller–Rabin determinístico

O teste de Miller–Rabin determinístico decide se um inteiro n é primo executando o teste de testemunha de primo provavelmente forte contra uma lista curta e fixa de bases que resolvem todo inteiro abaixo de um limite de garantia publicado. Diferente de uma execução probabilística de Miller–Rabin que sorteia testemunhas e só estima o erro, esta capacidade usa sempre as mesmas bases, devolve sempre o mesmo veredito para o mesmo n e recusa entrada acima do limite em que essas bases deixam de ser comprovadamente suficientes. Você envia um único número inteiro no mínimo dois e no máximo o limite, e recebe um indicador de primalidade, a lista de testemunhas, o próprio limite e—quando o número é composto—a primeira testemunha que o provou.

Como funciona o teste de primo provavelmente forte com bases fixas

Miller–Rabin reescreve um candidato ímpar n como n menos um igual a d vezes dois elevado a s com d ímpar; em seguida, para cada testemunha a, calcula a elevado a d módulo n. Se essa potência for um ou n menos um, a testemunha passa. Caso contrário o algoritmo eleva o valor ao quadrado até s menos uma vezes e aceita a testemunha só se algum quadrado intermediário for n menos um; qualquer outro caminho prova que n é composto para essa base.

Um número que passa em todas as testemunhas chama-se primo provavelmente forte em relação a essas bases. Para conjuntos fixos bem escolhidos, resultados de teoria dos números mostram que não há composto abaixo de um limiar conhecido que engane todas as bases do conjunto—assim o desfecho de primo provavelmente forte vira primo verdadeiro dentro do limite.

Esta capacidade usa as sete bases dois, três, cinco, sete, onze, treze e vinte e três, suficientes para todo inteiro de sessenta e quatro bits e portanto para todo inteiro seguro de JavaScript até nove quatrilhões. Os primos minúsculos dois e três resolvem-se como primos. Quando uma testemunha divide n e é menor que n, essa testemunha é informada como base falha porque n é um múltiplo óbvio.

Quando um teste de primos com bases fixas ajuda

Cursos de criptografia e treinadores de CTF usam um teste de Miller–Rabin determinístico para mostrar aos alunos a diferença entre checagens probabilísticas com testemunhas aleatórias e certificados de bases fixas que nomeiam o limite de garantia na resposta. Autores de bibliotecas fixam testes unitários contra primos conhecidos, pseudoprimos fortes e compostos para que um refactor da exponenciação modular não inverta um veredito em silêncio.

Desenvolvedores de aplicações validam valores de configuração com forma de primo, sementes de quebra-cabeça ou parâmetros toy de Diffie–Hellman antes de um pipeline mais longo, capturando pares e compostos pequenos sem montar um sistema de álgebra computacional.

Prefira esta ferramenta quando a intenção de busca for especificamente o algoritmo de Miller–Rabin determinístico com testemunhas fixas e um limite rígido—não quando precisar do menor divisor de um composto, da fatoração prima completa, de Lucas–Lehmer para números de Mersenne ou de testes probabilísticos com uma lista de testemunhas personalizada que você mesmo forneça.