Teste de primalidade de Proth com testemunha

Primeiro, confirma que k é positivo e ímpar, n é positivo e k é menor que 2^n. Depois, calcula exatamente a potência modular necessária. Uma congruência válida prova que o número de Proth é primo; uma testemunha que falha gera resultado inconclusivo, exceto quando revela um fator.

Informe um número de Proth legítimo e uma testemunha

Um número de Proth tem a forma exata N = k × 2^n + 1, na qual k é um inteiro positivo ímpar, n é um inteiro positivo e k é estritamente menor que 2^n. Todas essas condições são essenciais. A calculadora recebe k e a testemunha como texto decimal para preservar valores grandes, sem arredondamento de ponto flutuante. Informe n como inteiro entre 1 e 10,000. A ferramenta constrói N em vez de pedir esse valor separadamente, evitando divergências entre o número declarado e os parâmetros que o definem. Ela também verifica se a testemunha está estritamente entre 1 e N. Entradas com k par, valor não positivo ou k maior ou igual a 2^n são rejeitadas por não serem de Proth, em vez de serem submetidas a um teorema cujas hipóteses não se aplicam. O número, o expoente, a testemunha e o resíduo são devolvidos como strings decimais quando necessário, permitindo que você audite o cálculo e copie os valores para outra ferramenta de aritmética exata.

Entenda o que a congruência realmente prova

Para um número de Proth válido N, o teorema afirma que N é primo se existir um inteiro a para o qual a^((N−1)/2) seja congruente a −1 módulo N. A testemunha fornecida corresponde a a, e a calculadora avalia a potência modular por quadrados sucessivos, sem construir primeiro a gigantesca potência comum. Na saída, `residue` é o menor resíduo não negativo, e `passes_test` é true exatamente quando ele equivale a N−1, a representação modular de −1. Nesse caso, `prime_proven` é true e o veredito é `prime`: trata-se de um certificado determinístico sob as condições de Proth já validadas, e não de um palpite de primo provável. A resposta inclui o expoente exato (N−1)/2 para que você reproduza a congruência de forma independente. O algoritmo usa somente operações inteiras, não seleciona testemunhas aleatoriamente e não consulta tabelas nem serviços remotos. Assim, a mesma entrada sempre produz o mesmo resultado e expõe todos os valores importantes empregados no teorema.

Interprete corretamente uma testemunha que falha

Uma testemunha que não produz −1 não prova, por si só, que o número é composto. Ela apenas indica que essa testemunha específica não satisfez a condição suficiente do teorema de Proth. Por isso, a calculadora retorna `inconclusive`, e não `composite`, quando o resíduo é diferente e a testemunha é coprima com N. Você pode então tentar outra testemunha escolhida matematicamente ou usar um método determinístico de primalidade diferente. Há uma exceção útil: antes de interpretar a congruência, a calculadora determina o máximo divisor comum entre a testemunha e N. Se esse valor for um fator próprio, o resultado será conclusivamente `composite`, e o fator será apresentado. Essa distinção evita o erro comum de transformar um teorema de sentido único em um teste bidirecional inválido. Ela também ajuda em fluxos automatizados: aceite `prime` como prova, rejeite `composite` quando surgir um fator e encaminhe `inconclusive` para outro teste, sem tratá-lo silenciosamente como uma falha definitiva.