Raíz cuadrada modular de Cipolla
El algoritmo de Cipolla le da la raíz cuadrada concreta módulo un primo impar, no solo un sí o un no: para 2 módulo 7 devuelve 3 y 4, porque 3 al cuadrado es 9, que equivale a 2 módulo 7. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- A
- 2
- Potencia (W)
- 7
- A módulo
- 2
- Raíces
- 3, 4
- Raíz
- 3
- Omega
- 0
El algoritmo de Cipolla es un método clásico de teoría de números para extraer raíces cuadradas módulo un primo impar. Dado un entero a y un primo impar p, devuelve un entero x tal que x al cuadrado es congruente con a módulo p siempre que a sea un residuo cuadrático. Las tareas de criptografía, la programación competitiva y los tutoriales de aritmética modular suelen necesitar la raíz explícita, no solo la prueba de residualidad sí o no del símbolo de Legendre.
Qué es una raíz cuadrada modular y cuándo aplica Cipolla
En aritmética modular la congruencia x al cuadrado congruente con a módulo p pide un entero x cuyo cuadrado caiga en la misma clase de residuo que a. Cuando p es un primo impar la respuesta teórica es nítida: o bien a es divisible por p y la única raíz es cero, o bien exactamente la mitad de las clases no nulas son residuos cuadráticos y cada residuo tiene exactamente dos raíces r y p menos r.
El símbolo de Legendre indica en qué caso se encuentra, pero no construye r. El algoritmo de Cipolla cubre ese hueco trabajando en una extensión cuadrática elegida del cuerpo de p elementos. Se elige un entero auxiliar omega de modo que omega al cuadrado menos a sea un no residuo cuadrático módulo p; entonces el elemento omega más una raíz cuadrada formal de ese no residuo, elevado a la potencia (p más uno) dividida por dos, vuelve al cuerpo base y es una raíz cuadrada de a.
También falla cuando p es compuesto o par, porque el algoritmo clásico y el criterio de Euler asumen un módulo primo impar. Frente a Tonelli–Shanks, Cipolla suele ser más corto de implementar para demos docentes y primos de tamaño medio, y no requiere factorizar p menos uno. Esta capacidad se dirige a estudiantes, docentes y scripts que quieren un camino Cipolla transparente con raíces ordenadas estables y un contrato de error documentado.
Dónde aportan valor las raíces cuadradas modulares de Cipolla
Las plataformas de concursos y los correctores LMS necesitan un oráculo determinista que rechace no residuos y módulos compuestos en lugar de devolver arrays vacíos que un cliente defectuoso podría tratar como éxito. Las notas de criptografía que introducen cifrado Rabin o descompresión de puntos sobre cuerpos primos suelen querer un recorrido de Cipolla junto a Tonelli–Shanks; un módulo puro compartido mantiene idénticas las demos del navegador y las comprobaciones del servidor.
Mantenga p dentro de la cota prima publicada, fije el array de raíces ordenadas en las pruebas, y obtendrá raíces cuadradas modulares reproducibles para docencia, automatización y edge workers sin embeber un sistema completo de álgebra computacional.
Qué puede hacer con ella
Aulas y deberes de teoría de números
Los alumnos envían a y un primo impar p y comparan las raíces ordenadas devueltas con los pasos de Cipolla hechos a mano o con tablas del libro.
Demos docentes de cripto y cuadernos
Ilustre Cipolla junto a comprobaciones de Legendre en notas estilo Rabin o de curvas elípticas sin importar una biblioteca algebraica pesada.
Preguntas frecuentes
¿Cómo calculo una raíz cuadrada modular con el algoritmo de Cipolla?
Envíe enteros a y un primo impar p.
¿Qué ocurre si a no es un residuo cuadrático módulo p?
No se inventa ninguna raíz y la llamada no se factura.
¿Por qué p debe ser un primo impar?
El algoritmo de Cipolla y el criterio de Euler están definidos para primos impares. Los módulos pares o compuestos se rechazan para que la respuesta nunca pretenda que un cuerpo no primo se comporte como F_p.
¿En qué se diferencia de una calculadora del símbolo de Legendre?
Legendre solo informa residualidad (−1, 0 o 1). Esta capacidad construye las raíces cuadradas explícitas cuando existen, usando la potencia en el cuerpo de extensión de Cipolla.
¿En qué se diferencia el algoritmo de Cipolla del de Tonelli–Shanks?
Ambos dan las mismas raíces. El de Cipolla suele ser más corto de seguir en una clase y no necesita factorizar p menos uno: trabaja en una extensión del cuerpo de p elementos y eleva un elemento a la potencia p más uno entre dos.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su stack
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)Ejemplo de solicitud
{
"a": 2,
"p": 7
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.cipolla_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
Esta capacidad valida que p es un primo impar, rechaza los no residuos con un error invalid_input claro, ejecuta una construcción de Cipolla totalmente determinista (sin sorteos aleatorios de omega) y devuelve ambas raíces cuando existen.
Qué es una raíz cuadrada modular y cuándo aplica Cipolla
La construcción falla exactamente cuando a es un no residuo, lo que este endpoint reporta como invalid_input en lugar de inventar una raíz falsa.
Contrato de entrada, pasos del algoritmo y forma de la respuesta
El valor absoluto de a no debe superar un billón. Luego multiplica en el anillo de elementos x más y por raíz de w, elevando omega más raíz de w a la potencia (p más uno) entre dos con multiplicaciones modulares exactas BigInt. Ejemplo: a igual a dos y p igual a siete produce las raíces tres y cuatro, porque tres al cuadrado es nueve, que es dos módulo siete. Envíe un cuerpo JSON con dos campos enteros obligatorios: a, el número cuya raíz cuadrada desea módulo p, y p, un primo impar entre tres y un billón inclusive. Cada campo puede llegar como número JSON o como cadena de dígitos con signo opcional. Campos ausentes, no enteros, fuera de rango, p par y p compuesto fallan con invalid_input y no se facturan. Cuando p se acepta, el manejador reduce a a a_mod entre cero y p menos uno. Si a_mod es cero la respuesta es la raíz trivial cero con method trivial_zero y omega null. En caso contrario se calcula el símbolo de Legendre de a_mod módulo p vía el criterio de Euler; el valor menos uno significa que a es un no residuo cuadrático y la tarea falla con un mensaje que nombra la clase de residuo. Cuando el símbolo es más uno el algoritmo busca el menor omega no negativo tal que el Legendre de omega al cuadrado menos a_mod sea menos uno: este barrido es determinista, así que el mismo par siempre usa el mismo testigo. El componente en el cuerpo es una raíz cuadrada; la API devuelve ambas raíces ordenadas, la raíz primaria menor preferida, el testigo omega, method igual a cipolla y verified true tras una comprobación interna del cuadrado.
Dónde aportan valor las raíces cuadradas modulares de Cipolla
Las aulas que cubren residuos cuadráticos pueden mostrar que la residualidad sola no basta y luego llamar a este endpoint para exhibir las raíces reales de muchos residuos sin calcular a mano potencias en el cuerpo de extensión. Los cuadernos de investigación que ya calculan símbolos de Legendre o Jacobi pueden pedir la raíz solo cuando el símbolo es uno, pagando $0.002 por ítem exitoso y nada en fallos de validación.
Casos de integración
Programación competitiva y corrección LMS
Los correctores verifican respuestas de raíz cuadrada modular, rechazan no residuos y módulos compuestos con invalid_input y mantienen omega determinista entre ejecuciones.
Preguntas técnicas
¿Cuánto cuesta la herramienta de raíz cuadrada modular de Cipolla?
La herramienta del navegador es gratuita. Las peticiones API usan saldo prepago KIT a $0.002 por llamada exitosa; la entrada inválida no se factura.