Teste de primalidade Solovay-Strassen com base escolhida

O teste de primalidade de Solovay-Strassen verifica se um inteiro ímpar se comporta como primo para uma base escolhida por você. Ele calcula o símbolo de Jacobi da base módulo o candidato, eleva essa base à metade do candidato menos um e compara os dois valores módulo o candidato. O resultado identifica uma testemunha definitiva de composição ou informa que o número é provavelmente primo para essa base. As entradas são strings decimais, preservando inteiros grandes com exatidão, sem arredondamento de ponto flutuante.

O significado da comparação

Para um primo ímpar n e qualquer base a que não seja divisível por n, o critério de Euler afirma que a elevada a (n - 1) / 2 é congruente, módulo n, ao símbolo de Legendre de a. O símbolo de Jacobi estende esse cálculo a candidatos compostos ímpares, permitindo calculá-lo de modo eficiente sem conhecer a fatoração de n. Solovay-Strassen compara a potência modular com o símbolo de Jacobi representado como resíduo: 1 continua sendo 1, enquanto -1 se torna n - 1.

Uma divergência prova matematicamente que n é composto. Outra base válida pode revelar um composto que passou na primeira comparação. A resposta inclui os dois resíduos, o valor de Jacobi e o máximo divisor comum, para que você possa examinar a decisão em vez de receber um resultado booleano sem justificativa.

Como escolher e validar as entradas

Forneça n e a como strings decimais sem sinal. O candidato n deve ser ímpar e ter valor mínimo de 3; valores pares ou menores retornam erro de entrada inválida por estarem fora do domínio declarado. A base deve satisfazer 1 < a < n.

Você não precisa verificar antes se os números são coprimos: a capacidade calcula gcd(a, n), e um fator comum não trivial classifica imediatamente o candidato como composto. Cada entrada tem limite de 1,000 dígitos decimais, impondo uma fronteira computacional clara. Sinais, espaços, pontos decimais, notação exponencial e zeros à esquerda são rejeitados para evitar interpretações ambíguas.

Ao escolher bases manualmente, use várias bases distintas para obter evidência mais forte. A capacidade não sorteia uma base, o que mantém todas as execuções reproduzíveis e permite registrar exatamente qual testemunha foi verificada.

Como interpretar o resultado com responsabilidade

O campo passes informa se a congruência exata de Solovay-Strassen vale para o par fornecido. Quando ele é false, classification é composite e a base informada certifica que o candidato não pode ser primo. Repita o teste com bases selecionadas de maneira independente se Solovay-Strassen for exigido por um exercício ou protocolo, considerando cada rodada aprovada como evidência probabilística adicional, não como prova.

Em sistemas novos sensíveis à segurança, use um procedimento moderno de teste de primalidade, cuidadosamente especificado, com número adequado de rodadas e aleatoriedade revisada, em vez de confiar em uma única base manual.