Raiz quadrada modular de Cipolla
O algoritmo de Cipolla entrega a raiz quadrada concreta módulo um primo ímpar, não só um sim ou não: para 2 módulo 7 ele devolve 3 e 4, porque 3 ao quadrado é 9, que equivale a 2 módulo 7. 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
- A
- 2
- Potência (W)
- 7
- A módulo
- 2
- Raízes
- 3, 4
- Raiz
- 3
- Ômega
- 0
O algoritmo de Cipolla é um método clássico da teoria dos números para extrair raízes quadradas módulo um primo ímpar. Dado um inteiro a e um primo ímpar p, devolve um inteiro x tal que x ao quadrado é congruente a a módulo p sempre que a for um resíduo quadrático. Tarefas de criptografia, programação competitiva e tutoriais de aritmética modular costumam precisar da raiz explícita — não só do teste sim ou não de residualidade do símbolo de Legendre.
O que é uma raiz quadrada modular e quando Cipolla se aplica
Na aritmética modular a congruência x ao quadrado congruente a a módulo p pede um inteiro x cujo quadrado caia na mesma classe de resíduo que a. Quando p é um primo ímpar a resposta teórica é nítida: ou a é divisível por p e a única raiz é zero, ou exatamente metade das classes não nulas são resíduos quadráticos e cada resíduo tem exatamente duas raízes r e p menos r. O símbolo de Legendre indica em qual caso você está, mas não constrói r.
O algoritmo de Cipolla preenche essa lacuna trabalhando em uma extensão quadrática escolhida do corpo com p elementos. Escolhe-se um inteiro auxiliar omega de modo que omega ao quadrado menos a seja um não resíduo quadrático módulo p; então o elemento omega mais uma raiz quadrada formal desse não resíduo, elevado à potência (p mais um) dividida por dois, volta ao corpo base e é uma raiz quadrada de a.
Também falha quando p é composto ou par, porque o algoritmo clássico e o critério de Euler assumem módulo primo ímpar. Em comparação com Tonelli–Shanks, Cipolla costuma ser mais curto de implementar para demos didáticas e primos de tamanho médio, e não exige fatorar p menos um. Esta capacidade visa estudantes, educadores e scripts que querem um caminho Cipolla transparente com raízes ordenadas estáveis e um contrato de erro documentado.
Onde as raízes quadradas modulares de Cipolla valem a pena
Plataformas de contes e corretores LMS precisam de um oráculo determinístico que rejeite não resíduos e módulos compostos em vez de devolver arrays vazios que um cliente com bug poderia tratar como sucesso. Notas de criptografia que introduzem cifragem Rabin ou descompressão de pontos sobre corpos primos costumam querer um passeio por Cipolla ao lado de Tonelli–Shanks; um módulo puro compartilhado mantém demos do navegador e checagens do servidor idênticas.
Mantenha p dentro do limite primo publicado, fixe o array de raízes ordenadas nos testes e obtenha raízes quadradas modulares reproduzíveis para ensino, automação e edge workers sem embutir uma pilha completa de álgebra computacional.
Casos de uso
Salas de aula e lições de teoria dos números
Alunos enviam a e um primo ímpar p e comparam as raízes ordenadas devolvidas com os passos de Cipolla feitos à mão ou com tabelas do livro.
Demos didáticas de cripto e cadernos
Ilustre Cipolla ao lado de checagens de Legendre em notas estilo Rabin ou de curvas elípticas sem importar uma biblioteca algébrica pesada.
Perguntas frequentes
Como calcular uma raiz quadrada modular com o algoritmo de Cipolla?
Envie inteiros a e um primo ímpar p.
E se a não for resíduo quadrático módulo p?
Nenhuma raiz é inventada e a chamada não é cobrada.
Por que p deve ser um primo ímpar?
O algoritmo de Cipolla e o critério de Euler são definidos para primos ímpares. Módulos pares ou compostos são rejeitados para que a resposta nunca finja que um corpo não primo se comporta como F_p.
Em que difere de uma calculadora do símbolo de Legendre?
Legendre só reporta residualidade (−1, 0 ou 1). Esta capacidade constrói as raízes quadradas explícitas quando existem, usando a potenciação no corpo de extensão de Cipolla.
Qual a diferença entre o algoritmo de Cipolla e o de Tonelli–Shanks?
Os dois encontram as mesmas raízes. O de Cipolla costuma ser mais curto de acompanhar em aula e não exige fatorar p menos um: ele trabalha numa extensão do corpo com p elementos e eleva um elemento à potência p mais um sobre dois.
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/cipolla-algorithm \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"p":7}'const res = await fetch("https://api.kit.forhosting.com/numth/cipolla-algorithm", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"p": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/cipolla-algorithm",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"p": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/cipolla-algorithm", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"p":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/cipolla-algorithm", 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
{
"a": 2,
"p": 7
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.cipolla_algorithm",
"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
Esta capacidade valida que p é um primo ímpar, rejeita não resíduos com um erro invalid_input claro, executa uma construção de Cipolla totalmente determinística (sem sorteios aleatórios de omega) e devolve ambas as raízes quando existem.
O que é uma raiz quadrada modular e quando Cipolla se aplica
A construção falha exatamente quando a é não resíduo, o que este endpoint reporta como invalid_input em vez de inventar uma raiz falsa.
Contrato de entrada, passos do algoritmo e formato da resposta
O valor absoluto de a não deve ultrapassar um trilhão. Em seguida multiplica no anel de elementos x mais y vezes raiz de w, elevando omega mais raiz de w à potência (p mais um) sobre dois com multiplicações modulares exatas BigInt. Exemplo: a igual a dois e p igual a sete produz as raízes três e quatro, porque três ao quadrado é nove, que é dois módulo sete. Envie um corpo JSON com dois campos inteiros obrigatórios: a, o número cuja raiz quadrada você deseja módulo p, e p, um primo ímpar entre três e um trilhão inclusive. Cada campo pode chegar como número JSON ou como string de dígitos com sinal opcional. Campos ausentes, não inteiros, fora da faixa, p par e p composto falham com invalid_input e não são cobrados. Se a_mod é zero a resposta é a raiz trivial zero com method trivial_zero e omega null. Caso contrário o símbolo de Legendre de a_mod módulo p é calculado via critério de Euler; o valor menos um significa que a é não resíduo quadrático e a tarefa falha com uma mensagem que nomeia a classe de resíduo. Quando o símbolo é mais um o algoritmo varre o menor omega não negativo tal que o Legendre de omega ao quadrado menos a_mod seja menos um — essa varredura é determinística, então o mesmo par sempre usa a mesma testemunha. O componente no corpo é uma raiz quadrada; a API devolve ambas as raízes ordenadas, a raiz primária menor preferida, a testemunha omega, method igual a cipolla e verified true após verificação interna do quadrado.
Onde as raízes quadradas modulares de Cipolla valem a pena
Salas que cobrem resíduos quadráticos podem mostrar que residualidade sozinha não basta e então chamar este endpoint para exibir as raízes reais de muitos resíduos sem calcular à mão potências no corpo de extensão. Cadernos de pesquisa que já calculam símbolos de Legendre ou Jacobi podem pedir a raiz só quando o símbolo é um, pagando US$ 0,002 por item bem-sucedido e nada em falhas de validação.
Casos de integração
Programação competitiva e correção LMS
Corretores verificam respostas de raiz quadrada modular, rejeitam não resíduos e módulos compostos com invalid_input e mantêm omega determinístico entre execuções.
Perguntas técnicas
Quanto custa a ferramenta de raiz quadrada modular de Cipolla?
A ferramenta do navegador é grátis. Pedidos API usam saldo pré-pago KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.