ForHosting KIT · Matemática

Fatoração de Pollard p−1

Encontra um fator de um número composto quando um de seus primos p tem um p − 1 suave: 1003 com limite 16 se divide em 17 e 59, porque 17 − 1 é 16. Se nada aparecer, aumente o limite. Grátis no seu navegador.

Grátis
Funciona no seu navegador
Sem cadastro
Seus dados não saem do seu aparelho

Executar grátis Ver a API

Use pelo WebAPIE-mailTelegramApp em breve

Exemplo resolvido

Se você digitar

N: 1003
Limite: 16

Você obtém

Fator: 17
Cofator: 59
Base: 2

O método p menos um de Pollard é um algoritmo clássico de fatoração de inteiros que encontra um fator não trivial de um módulo composto n quando pelo menos um fator primo p de n tem a propriedade de que p menos um é suave em relação a um limite B escolhido — ou seja, toda potência prima na fatoração de p menos um é no máximo B. Estudantes de teoria elementar dos números, competidores de CTF e aprendizes de criptografia encontram este algoritmo ao estudar por que módulos RSA devem evitar primos com totientes suaves. Esta capacidade executa uma busca determinística de estágio um de Pollard p−1: constrói o produto de potências primas até B, eleva uma base pequena a esse expoente módulo n e devolve o mdc dessa potência menos um com n sempre que o mdc for um fator próprio.

Como Pollard p−1 encontra um fator a partir de um p−1 suave

Fixe um inteiro composto n e um limite de suavidade positivo B. A observação de Pollard é simples: se p é um divisor primo de n e toda potência prima que divide p menos um é no máximo B, então o mínimo múltiplo comum dos inteiros de um até B é múltiplo de p menos um.

Pelo pequeno teorema de Fermat, qualquer base a coprima com p satisfaz a elevado a p menos um congruente a um módulo p, e portanto a elevada a esse grande mmc também é congruente a um módulo p. Calcular a mesma potência módulo n e tomar o máximo divisor comum do resultado menos um com n frequentemente produz p ou outro fator não trivial.

Na prática a implementação nunca constrói o mmc completo de forma explícita; ela criva os primos até B e, para cada primo q, eleva o acumulador em curso à maior potência de q que não ultrapassa B, tudo módulo n. Após cada passo de potência prima avalia o mdc do acumulador menos um com n. Um mdc intermediário não trivial é devolvido imediatamente.

Se o mdc colapsa para n, um percurso de recuperação mais fino sobre expoentes menores tenta isolar um único fator primo antes de abandonar essa base. Várias bases pequenas são tentadas para que ordens azaradas da base dois não ocultem um fator que de outra forma seria B-suave. O método não é um algoritmo de fatoração completa: devolve um fator não trivial e o cofator correspondente.

Quem precisa da fatoração prima completa pode alimentar cada peça composta a uma ferramenta de fatoração em primos ou elevar B e executar de novo. O sucesso só é garantido no cenário de p−1 suave; fatores primos grandes de p menos um exigem um B maior ou outro algoritmo, como o método das curvas elípticas ou a peneira quadrática.

Quando este método de fatoração compensa

Cursos de criptografia usam Pollard p−1 para mostrar por que primos com predecessores suaves são perigosos na geração de parâmetros RSA e Diffie–Hellman; uma ferramenta ao vivo que aceita n e B permite ao instrutor demonstrar uma divisão em aula sem escrever à mão a potenciação modular.

Plataformas CTF e de lições de casa precisam de um oráculo determinístico que ou devolve um fator documentado para semiprimos clássicos como mil e três com limite dezesseis, ou rejeita limites pequenos demais para que avaliadores possam marcar tanto fatores corretos quanto raciocínios de falha corretos. Engenheiros de segurança que auditam geração de chaves legada podem varrer módulos candidatos em busca de fatores com p−1 suave antes que esses módulos cheguem à produção.

Mantenha n dentro do limite de dígitos, escolha B grande o suficiente para cobrir o maior fator primo de p menos um de algum primo p que divida n, e você obtém fatores reproduzíveis para ensino, write-ups de CTF e auditorias leves sem montar um sistema completo de álgebra computacional.

Casos de uso

Higiene de módulos candidatos

Varra módulos candidatos RSA ou Diffie–Hellman em busca de fatores com p−1 suave antes do deploy, sem importar um suite completo de fatoração.

Perguntas frequentes

O que é o método de fatoração p−1 de Pollard?

É um algoritmo de estágio um que calcula uma grande potência suave de uma base módulo n e devolve gcd(a^M − 1, n). Encontra um fator p quando p−1 é B-suave para o limite B escolhido.

Quando o método falha em encontrar um fator?

Quando n é primo, quando todo fator primo p de n tem um divisor primo de p−1 maior que B, ou quando a recuperação não isola um fator próprio.

Ela devolve a fatoração prima completa?

Não. Devolve um fator não trivial e o cofator n/factor (o menor primeiro). Fatore cada peça com uma ferramenta de fatoração em primos se precisar de todas as potências primas.

Qual limite devo escolher?

Comece com um pequeno e aumente se nenhum fator aparecer. O limite precisa cobrir cada potência de primo de p − 1 para pelo menos um fator primo p do seu número. Qualquer inteiro de 2 a 50.000 é aceito.

Quantos dígitos o número pode ter?

Até 18 dígitos, escrito como inteiro sem pontos, vírgulas ou espaços. Números pares devolvem o fator 2 na hora, e um número primo não dá fator, porque não há nada para dividir.

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

POSThttps://api.kit.forhosting.com/numth/pollard-p-minus-one

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/pollard-p-minus-one \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":"1003","bound":16}'

const res = await fetch("https://api.kit.forhosting.com/numth/pollard-p-minus-one", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": "1003",
    "bound": 16
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/pollard-p-minus-one",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": "1003",
    "bound": 16
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/pollard-p-minus-one", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":"1003","bound":16}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":"1003","bound":16}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/pollard-p-minus-one", 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": "1003",
  "bound": 16
}

Exemplo de resposta

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.pollard_p_minus_one",
  "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

por chamadaUS$ 0,002

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

Quando o limite é apertado demais, n é primo ou todo fator resiste ao método, a tarefa falha com invalid_input em vez de inventar um fator. O caminho gratuito do navegador e a API paga compartilham o mesmo módulo BigInt puro, de modo que verificações de lição de casa e automação nunca discordam.

Contrato de entrada, formato da resposta e modos de falha

O campo n é o inteiro a fatorar: um inteiro seguro de JavaScript ou uma string decimal simples sem vírgulas, espaços ou notação científica, com pelo menos dois e no máximo dezoito dígitos decimais. Exemplo: n igual a mil e três e bound igual a dezesseis devolve fator dezessete e cofator cinquenta e nove porque dezessete menos um é dezesseis, que é dezesseis-suave. Se n for par o fator dois é devolvido imediatamente sem uma busca completa de estágio um. Essa falha é desenho intencional do produto: um sucesso silencioso com fator um ou n quebraria automações que tratam qualquer resposta duzentos como uma divisão real. Envie por POST um objeto JSON com dois campos obrigatórios. O campo bound é o limite de suavidade B, um inteiro de dois a cinquenta mil; os aliases B, b, smoothness_bound e smoothness são aceitos por conveniência. Em caso de sucesso o corpo ecoa n como string decimal e bound como inteiro, e informa factor e cofactor como strings decimais com o fator menor primeiro, a base que produziu o fator e method definido como a string fixa pollard_p_minus_one. Campos ausentes, não inteiros, n abaixo de dois, bound fora do intervalo publicado e n com mais de dezoito dígitos falham com invalid_input e não são cobrados. Quando o estágio um termina todas as bases sem um fator próprio — por exemplo n é primo, ou todo fator primo p tem um divisor primo de p menos um maior que B — o manipulador também falha com invalid_input e uma mensagem de que Pollard p−1 não encontrou fator não trivial dentro do limite, convidando a elevar B ou tentar outro n.

Onde uma API de fator p−1 realmente vale a pena

Autores de notebooks que já têm uma rotina geral de fatoração em primos ainda se beneficiam de um endpoint p−1 explícito quando a lição é o método em si e não a lista completa de fatores. Como a implementação é parse puro de nível A, cada chamada bem-sucedida custa o preço base publicado US$ 0,002 sem tokens de modelo e sem rede de saída, e a validação falha nunca consome saldo.

Casos de integração

Demonstrações em sala de p−1 suave

Mostre como um limite B que cobre p−1 de um fator primo de um semiprimo produz uma divisão não trivial, com exemplos clássicos como n=1003 com B=16.

Avaliadores automáticos CTF e de tarefas

Avalie exercícios de Pollard p−1 com um oráculo determinístico que devolve o fator quando B basta e invalid_input quando o limite é apertado demais.

Perguntas técnicas

Quais entradas a API exige?

O campo n (inteiro ≥ 2, ≤ 18 dígitos) e o campo bound (suavidade B de 2 a 50000). Os aliases incluem number/value para n e B/smoothness_bound para bound.

Quanto custa a fatoração de Pollard p−1?

A ferramenta do navegador é gratuita. Solicitações API usam saldo pré-pago do KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida e limites falhos não são cobrados.

Ver a documentação completa do KIT →

Executar grátis