Teste de primalidade de Lucas

Forneça um inteiro ímpar n, uma testemunha de Lucas proposta e a fatoração prima completa de n menos um. A calculadora valida a própria fatoração, avalia as potências modulares e os máximos divisores comuns exigidos e só certifica n quando todas as condições do teorema de Lucas são satisfeitas. Strings decimais preservam inteiros exatos, inclusive valores acima do intervalo numérico seguro comum do JavaScript.

Prepare um certificado completo

Comece com o inteiro ímpar que você deseja certificar e fatore completamente n menos um. Informe n e cada fator primo como uma string decimal canônica, pois as strings preservam valores exatos até o limite de 64 bits. Cada fator deve aparecer uma vez, com expoente positivo. Por exemplo, para n = 29, n menos um = 28 = 2 ao quadrado vezes 7; portanto, a lista contém 2 com expoente 2 e 7 com expoente 1. Você também deve fornecer uma base a que satisfaça 1 < a < n. Essa base é a testemunha de Lucas proposta. O verificador exige deliberadamente a testemunha em vez de procurá-la: verificar um certificado é rápido, limitado e repetível, enquanto uma busca pode ter duração dependente da entrada. Caso ainda não tenha uma testemunha, experimente bases pequenas em uma ferramenta separada de raízes primitivas e depois envie o certificado resultante. Espaços, sinais, zeros à esquerda, notação de ponto flutuante, primos duplicados, fatores compostos e fatores ausentes são rejeitados, e não normalizados silenciosamente, o que torna o certificado adequado para trilhas de auditoria e pipelines automatizados.

Entenda as duas condições de Lucas

O primeiro cálculo verifica se a elevado a n menos um é congruente a 1 módulo n. Essa é a conhecida condição de Fermat, mas ela não prova primalidade sozinha, pois pseudoprimos podem satisfazê-la. A segunda etapa, decisiva, usa cada primo distinto q que divide n menos um. Para cada q, o verificador calcula a elevado a (n menos um) dividido por q módulo n, subtrai um e confirma que o resultado tem máximo divisor comum 1 com n. A aprovação em todas essas verificações prova que a ordem multiplicativa de a módulo n é exatamente n menos um. Um elemento módulo n não pode ter essa ordem a menos que n seja primo; esse é o núcleo do teorema de Lucas. Os registros retornados exibem o resíduo modular e o máximo divisor comum para cada q distinto, enquanto o expoente continua visível como parte da fatoração validada. A exponenciação modular utiliza quadrados sucessivos com aritmética BigInt exata; assim, o cálculo nunca depende de arredondamento de ponto flutuante, bases aleatórias, serviço de rede ou confiança probabilística.

Interprete falhas e resultados bem-sucedidos

Uma resposta bem-sucedida é o resultado de um certificado de primalidade, não apenas um rótulo de primo provável. Ela repete n, identifica a testemunha aceita, informa o resíduo de Fermat e lista uma verificação bem-sucedida do máximo divisor comum para cada fator distinto de n menos um. Guarde a entrada original junto com a resposta quando outro sistema precisar reproduzir a prova. As falhas são intencionalmente específicas. Se as potências dos fatores não multiplicarem exatamente n menos um, a fatoração estará incompleta ou incorreta. Se um fator informado for composto ou o mesmo primo aparecer duas vezes, a fatoração estará malformada, mesmo que o produto bruto coincida. A falha de qualquer condição modular indica que a base fornecida não é uma testemunha de Lucas; isoladamente, isso não distingue um n composto de um primo acompanhado de uma base inadequada. Experimente outra testemunha matematicamente justificada se ainda houver expectativa de primalidade. As entradas são limitadas a inteiros ímpares de 3 até 2^64 menos 1, permitindo validar deterministicamente os fatores primos informados antes de avaliar o certificado. O preço da API é US$ 0,002 por solicitação.