Cipolla's Algorithm

Ordinary arithmetic has square roots: $\sqrt{9} = 3$, $\sqrt{2} \approx 1.414$. But in modular arithmetic — the world of clocks and remainders — the question "what is the square root of $n$ modulo $p$?" is surprisingly subtle.

We say $r$ is a square root of $n$ mod $p$ if $r^2 \equiv n \pmod{p}$. For example, $6^2 = 36 \equiv 2 \pmod{17}$, so 6 is a square root of 2 mod 17. Not every number has such a root; those that do are called quadratic residues.

The naive approach — try every remainder from 0 to $p-1$ — works but takes $O(p)$ time, which is hopeless for the primes used in modern cryptography (hundreds of digits long). Cipolla's algorithm, published by Michele Cipolla in 1907, finds the square root in $O(\log^2 p)$ steps by a beautiful detour: it temporarily steps outside ordinary integers mod $p$ and into a quadratic field extension — a mathematical space with an "impossible" number whose square is not a residue.

That detour is the trick. Once you understand it, you see a pattern that reappears throughout number theory, algebra, and the algorithms that secure every HTTPS connection you make.

Enter any prime $p$ and a quadratic residue $n$ (a number that actually has a square root mod $p$). The demo runs Cipolla's algorithm step by step, showing both the brute-force scan and the field-extension shortcut side by side.

<p class="hint">{{hint}}</p>
<div class="inputs">
  <label>n <input id="inp-n" type="number" value="10" min="1"></label>
  <label>p <input id="inp-p" type="number" value="13" min="3" step="2"></label>
  <button id="btn-run" type="button">{{btn_run}}</button>
</div>
<div id="error" class="error" hidden></div>
<div id="results" hidden>
  <div class="col-pair">
    <div class="col">
      <div class="col-head">{{col_brute}}</div>
      <div id="bf-steps" class="steps"></div>
      <div id="bf-answer" class="answer"></div>
    </div>
    <div class="col">
      <div class="col-head">{{col_cipolla}}</div>
      <div id="cip-steps" class="steps"></div>
      <div id="cip-answer" class="answer"></div>
    </div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.inputs { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .7rem; }
label { display: flex; align-items: center; gap: .35rem; font-weight: 600; font-size: .9rem; }
input[type=number] { width: 72px; padding: .3rem .4rem; border: 1px solid #adb1b8;
                     border-radius: 6px; font: inherit; font-size: .9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.error { color: #c92f3c; font-weight: 600; margin-bottom: .5rem; }
.col-pair { display: grid; grid-template-columns: 1fr 1fr; gap: 1rem; margin-top: .3rem; }
@media (max-width: 480px) { .col-pair { grid-template-columns: 1fr; } }
.col-head { font-weight: 700; font-size: .85rem; text-transform: uppercase;
            letter-spacing: .04em; color: #1d3557; margin-bottom: .4rem; }
.steps { font-size: .8rem; color: #555; line-height: 1.7; max-height: 200px;
         overflow-y: auto; border: 1px solid #dde3e9; border-radius: 6px;
         padding: .4rem .55rem; background: #f7f9fb; }
.steps .hit { color: #0a7d33; font-weight: 700; }
.answer { margin-top: .45rem; font-weight: 700; font-size: 1rem; min-height: 1.4em; }
.answer.ok { color: #0a7d33; }
.answer.bad { color: #c92f3c; }

// Code not found

Watch what happens as $p$ grows. The brute-force column must check every remainder — its work grows linearly with $p$. Cipolla's algorithm, by contrast, does a handful of multiplications in the field extension and terminates in logarithmic time regardless of how large $p$ is. That is the asymptotic gap that makes the algorithm practical in real cryptographic settings.

How hard is it to find a square root mod $p$, and why does Cipolla's trick work?

• Existence check (free). By Euler's criterion, $n$ is a quadratic residue mod $p$ iff $n^{(p-1)/2} \equiv 1 \pmod{p}$, computable in $O(\log p)$ multiplications by fast exponentiation.
• Brute force is $O(p)$. Trying $r = 0, 1, \ldots, p-1$ checks $r^2 \bmod p$ and terminates when it finds $n$. For a 256-bit prime that means up to $\approx 10^{77}$ operations — completely infeasible.
• The field extension. Cipolla picks a random $a$ with $a^2 - n$ a non-residue mod $p$ (roughly half of all $a$ qualify, so a few random tries suffice). He then works in $\mathbb{F}_{p^2} = \mathbb{Z}/p\mathbb{Z}[x]/(x^2 - (a^2 - n))$, where $\omega = x$ satisfies $\omega^2 = a^2 - n$. In this two-dimensional ring, the element $(a + \omega)^{(p+1)/2}$ lands in the base field $\mathbb{F}_p$ and equals $\sqrt{n}$.
• Why it lands back. The Frobenius endomorphism — the map $z \mapsto z^p$ — fixes every element of $\mathbb{F}_p$ and sends $\omega \mapsto -\omega$ (since $\omega^p = \omega \cdot \omega^{p-1} = \omega \cdot (a^2-n)^{(p-1)/2} = -\omega$ for a non-residue). A short calculation then shows $(a+\omega)^{p+1} = n$, so $(a+\omega)^{(p+1)/2}$ is the square root. Proven correct by Michele Cipolla in 1907.
• Total cost: $O(\log p)$ multiplications in $\mathbb{F}_{p^2}$, each taking $O(\log p)$ bit operations — giving $O(\log^2 p)$ overall. Faster algorithms (Tonelli-Shanks, Sarkar-Singh) exist for special prime shapes but Cipolla's is the cleanest general method.

Cipolla's algorithm also connects to discrete logarithms: both live in the world of group exponentiation over finite fields, and both show how abstract algebra converts hard-seeming arithmetic into efficient computation.

Modular square roots are not an abstraction — they appear in the core of many algorithms that run billions of times per day:

• Elliptic-curve point decompression: a compressed EC point stores only the $x$-coordinate and one bit. To recover $y$ you solve $y^2 \equiv x^3 + ax + b \pmod{p}$ — a modular square root. Every TLS 1.3 handshake using ECDHE does this.
• Quadratic sieve factoring: the fastest known general factoring algorithm repeatedly solves $t^2 \equiv n \pmod{q}$ over small primes $q$ to build a factor base. Cipolla (or Tonelli-Shanks) is the subroutine called in the sieving phase.
• Tonelli-Shanks and why it sometimes stalls: the Tonelli-Shanks algorithm is faster for primes where $p - 1$ is divisible by a high power of 2, but it requires computing a non-residue first and can hit a slow path. Cipolla's randomized approach avoids that bottleneck.
• Quadratic reciprocity and number theory: understanding which numbers are residues mod $p$ is central to P vs NP-adjacent questions about the hardness of arithmetic problems.

Learn Cipolla's algorithm and you have a concrete taste of the algebraic machinery — field extensions, Frobenius maps, group exponentiation — that underlies both classical and post-quantum cryptography.

Cipolla's algorithm is a masterclass in mathematical detour. The direct road — try every remainder — takes $O(p)$ steps and is useless for large primes. The clever road — invent a number $\omega$ whose square is a non-residue, work in $\mathbb{F}_{p^2}$ for a moment, then come back — takes $O(\log^2 p)$ steps and is practical for any prime your computer can represent.

The lesson generalizes far beyond square roots: in mathematics and computer science alike, the fastest path through a problem often goes through a richer space. Step into a field extension, a complex plane, a Fourier domain — do your computation there — and step back out with the answer.

The next time your browser negotiates a TLS connection, a modular square root is being computed somewhere in that handshake. Cipolla's 1907 insight — or a close cousin of it — is running on your behalf, invisibly, at logarithmic speed.