Verificador de pseudoprimos de Fermat para qualquer base

Um composto aprovado é pseudoprimo de Fermat para a base escolhida: ele se comporta como primo nesse teste específico, embora não seja primo. O resultado também apresenta o máximo divisor comum, facilitando sua análise e explicação.

O que um resultado positivo realmente significa

O pequeno teorema de Fermat afirma que, se n é primo e a não é divisível por n, então a elevado a n menos um deixa resto um módulo n. A recíproca não é garantida. Alguns inteiros compostos também produzem resto um para determinadas bases; eles são chamados de pseudoprimos de Fermat nessas bases. Este verificador exige que n seja composto, confirma primeiro essa condição e depois avalia a congruência com exatidão. Quando passes_fermat_test e is_fermat_pseudoprime são verdadeiros, isso significa que o composto informado enganou o teste de Fermat para aquela base específica. Não significa que n seja primo, provavelmente primo ou pseudoprimo em todas as bases. A base faz parte da afirmação e deve sempre acompanhar o resultado. O resto retornado fornece a evidência aritmética direta: um representa aprovação e qualquer outro valor representa reprovação. O máximo divisor comum também é exibido porque um divisor não trivial explica muitas falhas e ajuda você a distinguir experiências com bases coprimas de entradas que já revelam uma relação de fatores.

Como o cálculo permanece exato

As duas entradas são strings decimais para que inteiros acima do intervalo numérico seguro do JavaScript não sejam arredondados antes do cálculo. O intervalo aceito termina no maior inteiro sem sinal de 64 bits, estabelecendo um limite claro e verificável para o teste de primalidade. Antes do teste de Fermat, o verificador usa Miller–Rabin determinístico com um conjunto de testemunhas suficiente para todo esse intervalo. Se um primo for detectado, ocorre um erro de entrada, pois números primos satisfazem o teorema, mas não podem ser pseudoprimos por definição. Para um composto válido, a exponenciação modular usa quadrados sucessivos em vez de construir o enorme valor a^(n-1). Cada multiplicação é reduzida módulo n, mantendo os valores intermediários limitados e exatos com BigInt. O algoritmo de Euclides calcula gcd(a,n) separadamente. A base precisa satisfazer 2 <= a <= n - 2. Nenhuma testemunha aleatória, data, chamada de rede ou operação de ponto flutuante interfere na resposta, portanto entradas idênticas sempre geram saídas idênticas.

Uso em estudos e fluxos de verificação

Um exemplo clássico usa n = 341 e a base a = 2. Como 341 é composto, mas 2^340 é congruente a um módulo 341, ele passa e é pseudoprimo de Fermat na base dois. Ao mudar a base, o mesmo composto pode falhar, razão pela qual um único teste de Fermat não é um certificado geral de primalidade. Em uma aula, a saída estruturada permite ligar diretamente a definição ao resto calculado. Em testes de software, você pode guardar vetores conhecidos de pseudoprimos e não pseudoprimos sem depender de uma biblioteca matemática ou de conversões numéricas específicas da máquina. Para explorar, compare várias bases permitidas mantendo n fixo e observe a importância da escolha da testemunha. Trate um resultado verdadeiro como demonstração da limitação do teste de Fermat, não como permissão para aceitar o número como primo em código criptográfico ou sensível à segurança. A API custa US$ 0,002 por par verificado, enquanto a versão no navegador executa localmente o mesmo cálculo determinístico.