Teste de primalidade Pocklington
Prova que um número é primo a partir de uma fatoração parcial de n − 1: para 31, os primos 2, 3 e 5 de 30 dão uma parte fatorada de 30, e como 900 é pelo menos 31, uma testemunha por primo o certifica. 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
- 31
- Fatores
- 2, 3, 5
- N
- 31
- N menos 1
- 30
- F
- 30
- R
- 1
O critério de Pocklington–Lehmer transforma uma fatoração parcial de n menos um em um certificado rigoroso de primalidade. Diferente da divisão por tentativa isolada ou de uma única congruência de Fermat, basta fatorar o suficiente de n−1 para que a parte fatorada F satisfaça F ao quadrado pelo menos n, mais uma testemunha modular curta para cada primo que divide F. Alunos, tutores de criptografia e cadernos de teoria dos números usam este teste de primalidade de Pocklington para provar primos pequenos e médios sem crivar até a raiz quadrada de n. Você informa o candidato n e os primos cujo produto é F; o motor verifica o limite de tamanho, busca ou valida bases a e devolve um certificado estruturado ou um erro claro quando a parte fatorada é pequena demais.
O que o critério de Pocklington–Lehmer afirma
Escreva n menos um como o produto F vezes R, onde F está completamente fatorado nos primos que você já conhece e R é o cofator restante.
O teorema clássico de Pocklington diz: se F é grande o bastante para que F ao quadrado seja pelo menos n, e para todo primo q que divide F existe uma base inteira a tal que a elevado a n menos um é congruente a um módulo n, e o máximo divisor comum de a elevado a (n menos um) dividido por q, menos um, com n, vale um, então n é primo.
De forma intuitiva, essas duas condições modulares forçam a ordem multiplicativa de a módulo n a ser múltiplo de q para cada um desses primos, logo a ordem é múltiplo de F; combinado com F maior que a raiz de n, nenhum n composto pode esconder um fator próprio do modo usual. Isso é mais forte que o pequeno teorema de Fermat sozinho, que só checa um resíduo de potência e pode ser enganado por pseudoprimos.
Também é mais econômico que fatorar n por completo ou dividir até sqrt(n) quando você já conhece muitos fatores de n−1—por exemplo se n é um número de Proth, uma construção de primo seguro ou um inteiro de exercício feito para n−1 fatorar com facilidade.
Esta capacidade implementa exatamente essa lista de verificação: o produto dos seus fatores vira F, R é (n−1)/F, a barreira F² ≥ n é imposta, e cada primo distinto q de F recebe uma testemunha a (buscada automaticamente a partir de dois, ou tirada da lista opcional bases).
Provas em sala, demos de cripto e automação
Cursos de teoria dos números usam um teste de primalidade de Pocklington para que aprendizes certifiquem primos como trinta e um, sessenta e um ou noventa e sete após fatorar n−1 à mão, em vez de só acionar um botão opaco de is-prime. Autores de bibliotecas com property tests afirmam que certified true implica que a própria rotina de primalidade concorda no mesmo n, e que F insuficiente sempre lança o erro documentado de parte pequena demais.
Mantenha n e factors dentro dos limites de dígitos e comprimento, prefira inteiros em string além dos inteiros seguros de JavaScript e trate certified como o booleano autoritativo de «Pocklington provou primo». Quando você só tiver uma fatia minúscula de n−1 fatorada, fatore mais primeiro ou use um verificador de primalidade geral; esta landing permanece dedicada à intenção de busca Pocklington–Lehmer para SEO, exemplos e forma da resposta ficarem focados.
Casos de uso
Certificados de primalidade em lições e provas
Alunos fatoram n−1, enviam n e os primos de F e recebem testemunhas que provam que n é primo sob Pocklington–Lehmer quando F é grande o bastante.
Corretores de olimpíadas e LMS
Corrija itens de teoria dos números com um oráculo de certificado determinístico que rejeita F pequeno demais e listas de fatores não primos em vez de falsos positivos silenciosos.
Perguntas frequentes
O que é o teste de primalidade de Pocklington?
Um critério que certifica que n é primo a partir de uma fatoração parcial n−1=F·R com F totalmente fatorado, F²≥n e testemunhas modulares a para cada primo q que divide F.
Quando a parte fatorada é pequena demais?
Quando F² < n (equivalente a F ≤ R na divisão n−1=F·R).
Quais entradas devo enviar?
Obrigatórios n (≥3) e factors (array de primos com multiplicidade cujo produto é F).
Se certified for false, n é composto?
Não. Significa que não se achou testemunha válida com o F e as bases dados. n ainda pode ser primo; tente mais bases, uma parte fatorada maior ou outro método de primalidade.
Posso escolher as bases testemunha?
Sim. Informe números inteiros de pelo menos 2: uma única base para todos os primos ou uma para cada primo distinto, em ordem. Se não informar nenhuma, o teste procura bases de 2 a 200 sozinho.
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/pocklington-test \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":31,"factors":[2,3,5]}'const res = await fetch("https://api.kit.forhosting.com/numth/pocklington-test", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 31,
"factors": [
2,
3,
5
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/pocklington-test",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 31,
"factors": [
2,
3,
5
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pocklington-test", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":31,"factors":[2,3,5]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":31,"factors":[2,3,5]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pocklington-test", 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": 31,
"factors": [
2,
3,
5
]
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.pocklington_test",
"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.
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
A mesma lógica pura BigInt alimenta a ferramenta gratuita do navegador e o caminho API a US$ 0,002 por solicitação bem-sucedida.
O que o critério de Pocklington–Lehmer afirma
Quando todos os primos passam, a resposta define certified e is_prime como true e lista as testemunhas para você refazer a aritmética à mão ou em outro sistema.
Contrato de entrada, erros de tamanho e leitura do certificado
Exemplo: n igual a trinta e um e factors igual a dois, três, cinco porque trinta é dois vezes três vezes cinco; então F é trinta, R é um e F ao quadrado supera largamente trinta e um. O campo opcional bases é um array de inteiros pelo menos dois—uma testemunha compartilhada para todos os primos, ou uma por primo distinto em ordem ordenada—ou omita e o motor busca a de dois até duzentos. Se o produto F não divide n−1, a tarefa falha porque a fatoração parcial é inconsistente. Se F ao quadrado é estritamente menor que n, a tarefa falha com mensagem de que a parte fatorada é pequena demais—esse é o erro duro intencional quando você não fatorou o suficiente de n−1 para aplicar Pocklington–Lehmer. Envie por POST um corpo JSON com o inteiro obrigatório n (pelo menos três) e o array obrigatório factors: os fatores primos, com multiplicidade, da parte fatorada F de n−1. Cada fator listado deve ser primo; entradas compostas falham com invalid_input para que uma lista forjada não finja certificado. Respostas de sucesso ecoam n, n_minus_1, F, R, F_squared, floor_sqrt_n, os primos distintos, o multiconjunto de fatores e um array witnesses com a por primo, o resíduo de potência, a checagem gcd e as flags ok. O booleano certified é true só quando todo primo tem testemunha válida; is_prime espelha certified aqui porque um passe completo de Pocklington é prova de primalidade, enquanto falha na busca de testemunhas não prova compostidade por si só. O preço é um fixo US$ 0,002 por chamada bem-sucedida na unidade item; falhas de validação não são cobradas. Inteiros grandes podem ser enviados como strings decimais dentro do limite de dígitos publicado para o JSON nunca truncá-los.
Provas em sala, demos de cripto e automação
Ferramentas de preparação para olimpíadas geram candidatos com n−1 suave, enviam os fatores conhecidos a este endpoint e guardam as testemunhas retornadas como um objeto de prova curto ao lado do gabarito. Como a implementação é parse pura de nível A, cada chamada bem-sucedida custa o US$ 0,002 publicado sem tokens de modelo nem rede de saída; o caminho gratuito do navegador executa a mesma função solve.
Casos de integração
Checagens em cadernos de cripto e CAS
Fixe certificados golden de Pocklington para primos fixos em testes unitários sem reimplementar modPow e checagens gcd em cada linguagem.
Perguntas técnicas
Quanto custa o teste de primalidade de Pocklington?
A ferramenta do navegador é gratuita. Solicitações API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida nunca é cobrada.