Verificador de pseudoprimo Euler-Jacobi
O 561 é um pseudoprimo de Euler–Jacobi na base 2: a potência com expoente 280 deixa resto 1, igual ao seu símbolo de Jacobi, embora 561 seja composto. Digite um composto ímpar e uma base para ver cada valor do veredito. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- N
- 561
- A
- 2
- Gcd
- 1
- Símbolo de Jacobi
- 1
- Expoente
- 280
- Resto
- 1
Um pseudoprimo de Euler–Jacobi em relação a uma base dada é um inteiro composto ímpar que obedece ao critério de Euler como se fosse primo. Para uma base a coprima, isso significa que a elevado a (n menos um) sobre dois é congruente ao símbolo de Jacobi de a sobre n, módulo n. Todo primo ímpar que não divide a satisfaz a mesma congruência, de modo que os compostos que ainda passam são as falhas interessantes de um teste no estilo Solovay–Strassen. Este verificador existe para exatamente essa pergunta: dados n composto ímpar e a base a, decidir se n é um pseudoprimo de Euler–Jacobi nessa base. A resposta informa o gcd, o símbolo de Jacobi, a potência modular, se a congruência vale e um booleano verdadeiro somente quando a definição completa se cumpre.
O que é um pseudoprimo de Euler–Jacobi e como difere dos testes de Fermat e de Euler
O critério de Euler diz que se p é um primo ímpar e a não é divisível por p, então a elevado a (p menos um) sobre dois é congruente ao símbolo de Legendre de a sobre p, módulo p. O símbolo de Jacobi (a/n) estende esse caráter quadrático dos primos ímpares a qualquer inteiro positivo ímpar n, então é tentador escrever a mesma congruência com n no lugar de p. Quando n é um primo ímpar os dois símbolos coincidem e a congruência é um teorema.
Quando n é ímpar e composto, a congruência ainda pode valer para algumas bases embora n não seja primo. Esses n chamam-se pseudoprimos de Euler–Jacobi na base a, desde que gcd(a, n) seja um. A condição é estritamente mais forte que o teste de Fermat (a elevado a n menos um congruente a um módulo n) e também mais forte que o teste de Euler fraco, que só pede que a potência modular seja mais um ou menos um.
O exemplo clássico é trezentos e quarenta e um na base dois: é pseudoprimo de Fermat, dois elevado a cento e setenta vale um módulo trezentos e quarenta e um, mas o símbolo de Jacobi (2/341) é menos um, de modo que a congruência de Euler–Jacobi falha. Quinhentos e sessenta e um, o menor número de Carmichael, satisfaz a congruência na base dois e portanto é um pseudoprimo de Euler–Jacobi nessa base. Noventa e um na base dez é outro exemplo de sala que este verificador confirma.
Onde um verificador de pseudoprimo de Euler–Jacobi se justifica
Cursos de teoria dos números e plataformas de olimpíadas usam um verificador de pseudoprimo de Euler–Jacobi para que os alunos separem mentirosos de Fermat de mentirosos de Solovay–Strassen sem implementar à mão a reciprocidade de Jacobi nem a exponenciação modular.
Cadernos de pesquisa e varreduras recreativas chamam o mesmo contrato quando querem um oráculo independente para uma lista publicada: quinhentos e sessenta e um, mil cento e cinco, mil setecentos e vinte e nove e os demais exemplos clássicos na base dois devem devolver verdadeiro, enquanto trezentos e quarenta e um na base dois deve devolver falso.
Oficinas de criptografia que apresentam o teste de primalidade de Solovay–Strassen precisam de uma ferramenta que recuse n primo, porque o ponto pedagógico é o composto que imita o critério de Euler, não reiterar que primos passam. Equipes de engenharia que escrevem testes de propriedades para as próprias bibliotecas de Jacobi ou de potência modular podem fixar esta resposta como contraste.
Prefira esta ferramenta quando a pergunta for estritamente se um composto ímpar dado satisfaz a congruência de Euler–Jacobi numa base dada — não quando você precisa de uma busca em todas as bases, um teste só de Fermat, um relatório de testemunhas Miller–Rabin ou certificados para inteiros de milhares de bits.
Casos de uso
Checagens de sala dos mentirosos de Solovay–Strassen
Peça que os alunos enviem n igual a 561 com base 2 e confirmem uma marca Euler–Jacobi verdadeira; depois contraste com 341 na base 2, que é apenas mentiroso de Fermat.
Oráculo independente para tabelas publicadas
Valide listas offline de pseudoprimos de Euler–Jacobi contra uma implementação determinística de Jacobi mais potência modular.
Testes de propriedades para bibliotecas de teoria dos números
Fixe gcd, o símbolo de Jacobi, remainder e o booleano nos testes unitários para que uma rotina local de reciprocidade não se desvie da definição.
Perguntas frequentes
O que torna n um pseudoprimo de Euler–Jacobi na base a?
n deve ser ímpar e composto, gcd(a, n) deve ser 1, e a^((n−1)/2) deve ser congruente ao símbolo de Jacobi (a/n) módulo n.
Por que n par e n primo são rejeitados?
Pseudoprimos de Euler–Jacobi definem-se como compostos ímpares que imitam o critério de Euler.
Em que isso difere de um pseudoprimo de Fermat?
Um pseudoprimo de Fermat na base a só precisa de a^{n−1} ≡ 1 (mod n). O teste de Euler–Jacobi exige ainda que a raiz quadrada modular dessa condição de Fermat coincida com o símbolo de Jacobi. 341 é mentiroso de Fermat na base 2, mas não é um pseudoprimo de Euler–Jacobi na base 2.
O 561 é pseudoprimo de Euler–Jacobi na base 2?
Sim. Ao elevar 2 à potência 280 e dividir por 561 sobra resto 1, e o símbolo de Jacobi de 2 sobre 561 também vale 1, então a congruência vale mesmo com 561 composto. É o menor número de Carmichael.
E se a base tiver um fator em comum com o número?
Nesse caso o número não é pseudoprimo de Euler–Jacobi nessa base, porque a definição exige que os dois sejam coprimos. A resposta é não, e o divisor comum aparece para você ver o motivo.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/numth/euler-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":561,"a":2}'const res = await fetch("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 561,
"a": 2
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/euler-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 561,
"a": 2
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":561,"a":2}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":561,"a":2}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/euler-pseudoprime-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"n": 561,
"a": 2
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.euler_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
max_abs | 9007199254740991 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Um n par ou primo é rejeitado com invalid_input em vez de um falso negativo enganoso, porque a definição vale só para compostos ímpares. O mesmo módulo determinístico roda grátis no navegador e no caminho da API a US$ 0,002 por chamada bem-sucedida.
O que é um pseudoprimo de Euler–Jacobi e como difere dos testes de Fermat e de Euler
A capacidade nunca chama primo a um composto nem pseudoprimo a um primo: entradas primas ou pares são erros, e o booleano is_euler_jacobi_pseudoprime é verdadeiro só quando n é um composto ímpar admitido, o par é coprimo e a congruência de Jacobi completa vale.
Contrato de entrada, campos da resposta e comportamento de erro
A cadeia criterion reitera a^((n-1)/2) ≡ (a/n) (mod n) para que uma página ou caderno mostre a definição ao lado do veredito. Quando gcd é maior que um, Jacobi vale zero e o par não é de Euler–Jacobi mesmo que alguma potência acidental se anule. Exemplo: n igual a quinhentos e sessenta e um e a igual a dois produz jacobi um, remainder um e uma marca verdadeira; n igual a trezentos e quarenta e um e a igual a dois produz jacobi menos um, remainder um e uma marca falsa. Toda a aritmética é BigInt exato; não há ponto flutuante nem testemunha aleatória. Envie um corpo JSON via POST com dois inteiros obrigatórios: n, o candidato composto ímpar (aliases modulus e number), e a, a base (alias base). Cada campo pode chegar como número JSON ou como cadeia de dígitos decimais; os valores devem ser inteiros completos cujo valor absoluto fique no intervalo seguro de inteiros do JavaScript, para que a primalidade de n seja decidida por um conjunto fixo de testemunhas Miller–Rabin, determinístico nesse bound. Campos ausentes, frações, booleanos, cadeias vazias e valores grandes demais falham com invalid_input nomeando o campo. Em caso de sucesso o corpo devolve n e a como números, informa gcd e o booleano coprime, devolve jacobi no conjunto menos um, zero ou um, dá exponent como (n menos um) sobre dois e remainder como a elevado a esse expoente módulo n, define congruence_holds quando remainder coincide com o símbolo de Jacobi reduzido ao sistema de resíduos módulo n, e define is_euler_jacobi_pseudoprime só quando o par é coprimo e a congruência vale.
Onde um verificador de pseudoprimo de Euler–Jacobi se justifica
Como a capacidade é parse de nível A puro, cada chamada bem-sucedida é determinística, offline e custa US$ 0,002, sem tokens de modelo. Mantenha n ímpar e composto, trate invalid_input como correção do cliente e fixe remainder e jacobi nos testes para que uma refatoração futura não altere em silêncio o resultado modular.
Perguntas técnicas
E se gcd(a, n) for maior que um?
O par não é de Euler–Jacobi. A resposta ainda devolve gcd, jacobi 0 e o resto modular, mas is_euler_jacobi_pseudoprime é falso porque a definição exige coprimalidade.
Quanto custa o verificador de pseudoprimo de Euler–Jacobi?
A ferramenta do navegador é gratuita. Pedidos API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.