Cipolla modular square root
Cipolla's algorithm gives the actual square root modulo an odd prime, not just a yes or no: for 2 modulo 7 it returns 3 and 4, since 3 squared is 9, which is 2 mod 7. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 2
- Power (W)
- 7
- A mod
- 2
- Roots
- 3, 4
- Root
- 3
- Omega
- 0
Cipolla's algorithm is a classical number-theoretic method for extracting square roots modulo an odd prime. Given an integer a and an odd prime p, it returns an integer x such that x squared is congruent to a modulo p whenever a is a quadratic residue. Cryptography homework, contest programming, and modular-arithmetic tutorials often need the explicit root—not only the Legendre yes-or-no residuosity test.
What a modular square root is and when Cipolla applies
In modular arithmetic the congruence x squared congruent to a modulo p asks for an integer x whose square lands in the same residue class as a. When p is an odd prime this question has a crisp answer theory: either a is divisible by p and the only root is zero, or exactly half of the nonzero classes are quadratic residues and each residue has exactly two roots r and p minus r. The Legendre symbol tells you which case you are in, but it does not construct r.
Cipolla's algorithm fills that gap by working in a carefully chosen quadratic extension of the field with p elements. You pick an auxiliary integer omega so that omega squared minus a is a quadratic non-residue modulo p; then the element omega plus a formal square root of that non-residue, raised to the power (p plus one) divided by two, collapses back into the base field and equals a square root of a.
Compared with Tonelli–Shanks, Cipolla is often shorter to implement for teaching demos and mid-size primes, and it needs no factorisation of p minus one. This capability therefore targets students, educators, and scripts that want a transparent Cipolla path with stable ordered roots and a documented error contract.
Where Cipolla modular square roots earn their keep
Contest platforms and LMS graders need a deterministic oracle that rejects non-residues and composite moduli instead of returning empty arrays that buggy clients might treat as success. Cryptography notes that introduce Rabin encryption or point decompression over prime fields often want a Cipolla walkthrough beside Tonelli–Shanks; a shared pure module keeps browser demos and server checks identical. Keep p within the published prime bound, pin the ordered roots array in tests, and you get reproducible modular square roots for teaching, automation, and edge workers without embedding a full computer-algebra stack.
What you can do with it
Number-theory classrooms and homework
Students submit a and odd prime p and compare the returned ordered roots against hand-worked Cipolla steps or textbook tables.
Crypto teaching demos and notebooks
Illustrate Cipolla beside Legendre checks in Rabin-style or elliptic-curve notes without importing a heavyweight algebra library.
FAQ
Why must p be an odd prime?
Cipolla's algorithm and Euler's criterion are defined for odd primes. Even or composite moduli are rejected so the response never pretends a non-prime field behaves like F_p.
How does this differ from a Legendre symbol calculator?
Legendre only reports residuosity (−1, 0, or 1). This capability constructs the explicit square roots when they exist, using Cipolla's extension-field powering.
How do I find the square root of 2 mod 7?
Enter 2 as the number and 7 as the prime. You get the two roots 3 and 4, because 3 squared is 9, which leaves 2 when divided by 7, and 4 is simply 7 minus 3.
What happens if a is not a quadratic residue modulo p?
No root is returned. You are told that the number has no square root modulo that prime instead of getting an invented one; modulo an odd prime, exactly half of the nonzero classes are residues.
How does Cipolla's algorithm compare with Tonelli–Shanks?
Both find the same roots. Cipolla is often shorter to follow in a lesson and does not need to factor p minus one: it works in an extension of the field with p elements and raises one element to the power p plus one over two.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your 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)Example request
{
"a": 2,
"p": 7
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.cipolla_algorithm",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
This capability validates that p is an odd prime, rejects non-residues with a clear invalid_input error, runs a fully deterministic Cipolla construction (no random omega draws), and returns both roots when they exist.
What a modular square root is and when Cipolla applies
The construction fails precisely when a is a non-residue, which this endpoint reports as invalid_input rather than inventing a fake root. It also fails when p is composite or even, because the classical algorithm and Euler's criterion both assume an odd prime modulus.
Input contract, algorithm steps, and response shape
Absolute values of a must not exceed one trillion. Example: a equals two and p equals seven yields roots three and four, because three squared is nine which is two mod seven. POST a JSON body with two required integer fields: a, the number whose square root you want modulo p, and p, an odd prime between three and one trillion inclusive. Each field may arrive as a JSON number or as a digit string with an optional sign. Missing fields, non-integers, out-of-range values, even p, and composite p all fail with invalid_input and are not billed. If a_mod is zero the response is the trivial root zero with method trivial_zero and omega null. Otherwise the Legendre symbol of a_mod modulo p is computed via Euler's criterion; a value of minus one means a is a quadratic non-residue and the task fails with a message that names the residue class. When the symbol is plus one the algorithm scans the smallest non-negative omega such that Legendre of omega squared minus a_mod is minus one—this scan is deterministic, so the same pair always uses the same witness. It then multiplies in the ring of elements x plus y times square-root of w, raising omega plus square-root of w to the power (p plus one) over two with exact BigInt modular multiplications. The resulting field component is a square root; the API returns both ordered roots, the preferred smaller primary root, the witness omega, method set to cipolla, and verified true after an internal square check.
Where Cipolla modular square roots earn their keep
Classrooms covering quadratic residues can show that residuosity alone is not enough and then call this endpoint to exhibit the actual roots for many random residues without hand-computing extension-field powers. Research notebooks that already compute Legendre or Jacobi symbols can request the root only when the symbol is one, paying $0.002 per successful item and nothing on validation failures.
Integration use cases
Contest programming and LMS auto-grading
Graders verify modular square-root answers, reject non-residues and composite moduli with invalid_input, and keep omega deterministic across runs.
Technical questions
How do I compute a modular square root with Cipolla's algorithm?
Send integers a and odd prime p. On success the API returns roots r and p−r (or 0 when a≡0 mod p) such that r² ≡ a (mod p), plus the deterministic omega witness used in the extension field.
What if a is not a quadratic residue modulo p?
The task fails with invalid_input and a message that a is a quadratic non-residue. No root is invented, and the call is not billed.
What does the Cipolla modular square root tool cost?
The browser tool is free. API requests use prepaid KIT balance at $0.002 per successful call; invalid input is not billed.