Introduction

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

We say rr is a square root of nn mod pp if r2≡n(modp)r^2 \equiv n \pmod{p}. For example, 62=36≡2(mod17)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−1p-1 — works but takes O(p)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⁡2p)O(\log^2 p) steps by a beautiful detour: it temporarily steps outside ordinary integers mod pp 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.

Try It

Enter any prime pp and a quadratic residue nn (a number that actually has a square root mod pp). 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">Enter a prime <b>p</b> and a quadratic residue <b>n</b> (n must have a square root mod p). The demo shows brute-force scan vs Cipolla's field-extension algorithm side by side.</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">Find √n mod p</button>
</div>
<div id="error" class="error" hidden></div>
<div id="results" hidden>
  <div class="col-pair">
    <div class="col">
      <div class="col-head">Brute Force</div>
      <div id="bf-steps" class="steps"></div>
      <div id="bf-answer" class="answer"></div>
    </div>
    <div class="col">
      <div class="col-head">Cipolla's Algorithm</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Cipolla's algorithm: find r such that r^2 ≡ n (mod p)
// Uses quadratic field extension F_p^2 = F_p[ω] where ω^2 = a^2 - n (a non-residue).
// Returns { r, steps[] } or null if no square root exists.

function modpow(base, exp, mod) {
  // Fast modular exponentiation — handles BigInt
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % mod;
    exp >>= 1n;
    base = base * base % mod;
  }
  return result;
}

// Multiply two elements of F_p^2 = {a + b*ω : a,b in F_p}, ω^2 = omega2
function fp2mul(A, B, omega2, p) {
  const [a0, a1] = A, [b0, b1] = B;
  const c0 = (a0 * b0 + a1 * b1 * omega2) % p;
  const c1 = (a0 * b1 + a1 * b0) % p;
  return [(c0 + p) % p, (c1 + p) % p];
}

// Raise element of F_p^2 to a power
function fp2pow(base, exp, omega2, p) {
  let result = [1n, 0n];
  while (exp > 0n) {
    if (exp % 2n === 1n) result = fp2mul(result, base, omega2, p);
    exp >>= 1n;
    base = fp2mul(base, base, omega2, p);
  }
  return result;
}

function cipolla(n, p) {
  const steps = [];
  n = ((n % p) + p) % p;

  // Check if n is a quadratic residue
  const euler = modpow(n, (p - 1n) / 2n, p);
  if (euler !== 1n) return { r: null, steps: ['n is not a quadratic residue mod p (Euler criterion: n^((p-1)/2) ≠ 1).'] };

  steps.push(fmt('Euler criterion: %n%^((%p%-1)/2) ≡ %euler% (mod %p%) → n is a QR ✓', { n: n, p: p, euler: euler }));

  // Find a such that a^2 - n is a non-residue
  let a = 1n, omega2, tries = 0;
  while (true) {
    omega2 = ((a * a - n) % p + p) % p;
    const leg = modpow(omega2, (p - 1n) / 2n, p);
    tries++;
    if (leg === p - 1n) {
      steps.push(fmt('Tried a=%a%: a²-n = %v%-%n% ≡ %omega2% (mod %p%) → non-residue ✓ (found in %tries% try/tries)', { a: a, v: a*a, n: n, omega2: omega2, p: p, tries: tries }));
      break;
    }
    steps.push(fmt('Tried a=%a%: a²-n ≡ %omega2% is a residue, skip.', { a: a, omega2: omega2 }));
    a++;
    if (a > p) return { r: null, steps: ['Could not find non-residue (unexpected for prime p).'] };
  }

  // Compute (a + ω)^((p+1)/2) in F_p^2
  const exp = (p + 1n) / 2n;
  steps.push(fmt('Computing (%a% + ω)^((%p%+1)/2) = (%a% + ω)^%exp% in F_p²', { a: a, p: p, exp: exp }));
  steps.push(fmt('where ω² = %omega2% (mod %p%)', { omega2: omega2, p: p }));

  const [r, imag] = fp2pow([a, 1n], exp, omega2, p);
  steps.push(fmt('Result: %r% + %imag%·ω', { r: r, imag: imag }));

  if (imag !== 0n) {
    steps.push('Imaginary part non-zero — unexpected (check inputs).');
    return { r: null, steps };
  }

  // Verify
  const check = modpow(r, 2n, p);
  steps.push(fmt('Verify: %r%² ≡ %check% (mod %p%) %v%', { r: r, check: check, p: p, v: check === n ? '✓ matches n!' : '✗ mismatch!' }));
  return { r: check === n ? r : null, steps };
}

function bruteForce(n, p) {
  const steps = [];
  n = ((n % p) + p) % p;
  for (let r = 0n; r < p; r++) {
    const sq = r * r % p;
    const hit = sq === n;
    steps.push({ text: `${r}² ≡ ${sq} (mod ${p})${hit ? ' ← match!' : ''}`, hit });
    if (hit) return { r, steps, checked: Number(r) + 1 };
  }
  return { r: null, steps, checked: Number(p) };
}

function isPrime(n) {
  if (n < 2n) return false;
  if (n === 2n) return true;
  if (n % 2n === 0n) return false;
  for (let i = 3n; i * i <= n; i += 2n) if (n % i === 0n) return false;
  return true;
}

function run() {
  const errEl = document.getElementById('error');
  const resEl = document.getElementById('results');
  errEl.hidden = true; resEl.hidden = true;

  let nVal, pVal;
  try {
    nVal = BigInt(document.getElementById('inp-n').value);
    pVal = BigInt(document.getElementById('inp-p').value);
  } catch(e) { errEl.textContent = 'Please enter valid integers.'; errEl.hidden = false; return; }

  if (!isPrime(pVal)) { errEl.textContent = fmt('%pVal% is not prime. Try 13, 17, 41, 97, 257.%pVal%', { pVal: pVal }); errEl.hidden = false; return; }
  if (pVal === 2n) { errEl.textContent = 'p must be an odd prime.'; errEl.hidden = false; return; }

  const n = ((nVal % pVal) + pVal) % pVal;

  // Brute force
  const bf = bruteForce(n, pVal);
  const bfStepsEl = document.getElementById('bf-steps');
  bfStepsEl.innerHTML = bf.steps.slice(0, 60).map(s =>
    `<div class="${s.hit ? 'hit' : ''}">${s.text}</div>`
  ).join('') + (bf.steps.length > 60 ? fmt('<div>… (%v% more checked)</div>', { v: bf.steps.length - 60 }) : '');
  const bfAns = document.getElementById('bf-answer');
  if (bf.r !== null) {
    bfAns.textContent = fmt('√%n% ≡ %r% (mod %pVal%) — checked %checked% values', { n: n, r: bf.r, pVal: pVal, checked: bf.checked });
    bfAns.className = 'answer ok';
  } else {
    bfAns.textContent = fmt('No square root exists for n=%n% mod p=%pVal%', { n: n, pVal: pVal });
    bfAns.className = 'answer bad';
  }

  // Cipolla
  const cip = cipolla(n, pVal);
  const cipStepsEl = document.getElementById('cip-steps');
  cipStepsEl.innerHTML = cip.steps.map(s => `<div>${s}</div>`).join('');
  const cipAns = document.getElementById('cip-answer');
  if (cip.r !== null) {
    cipAns.textContent = fmt('√%n% ≡ %r% (mod %pVal%) — O(log² p) steps', { n: n, r: cip.r, pVal: pVal });
    cipAns.className = 'answer ok';
  } else {
    cipAns.textContent = `No square root — n is not a quadratic residue mod p.`;
    cipAns.className = 'answer bad';
  }

  resEl.hidden = false;
}

document.getElementById('btn-run').addEventListener('click', run);
run(); // run with defaults on load
Result
Console

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

The Real Complexity

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

  • Existence check (free). By Euler's criterion, nn is a quadratic residue mod pp iff n(p−1)/2≡1(modp)n^{(p-1)/2} \equiv 1 \pmod{p}, computable in O(log⁡p)O(\log p) multiplications by fast exponentiation.
  • Brute force is O(p)O(p). Trying r=0,1,…,p−1r = 0, 1, \ldots, p-1 checks r2 mod pr^2 \bmod p and terminates when it finds nn. For a 256-bit prime that means up to ≈1077\approx 10^{77} operations — completely infeasible.
  • The field extension. Cipolla picks a random aa with a2−na^2 - n a non-residue mod pp (roughly half of all aa qualify, so a few random tries suffice). He then works in Fp2=Z/pZ[x]/(x2−(a2−n))\mathbb{F}_{p^2} = \mathbb{Z}/p\mathbb{Z}[x]/(x^2 - (a^2 - n)), where ω=x\omega = x satisfies ω2=a2−n\omega^2 = a^2 - n. In this two-dimensional ring, the element (a+ω)(p+1)/2(a + \omega)^{(p+1)/2} lands in the base field Fp\mathbb{F}_p and equals n\sqrt{n}.
  • Why it lands back. The Frobenius endomorphism — the map z↦zpz \mapsto z^p — fixes every element of Fp\mathbb{F}_p and sends ω↦−ω\omega \mapsto -\omega (since ωp=ω⋅ωp−1=ω⋅(a2−n)(p−1)/2=−ω\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+ω)p+1=n(a+\omega)^{p+1} = n, so (a+ω)(p+1)/2(a+\omega)^{(p+1)/2} is the square root. Proven correct by Michele Cipolla in 1907.
  • Total cost: O(log⁡p)O(\log p) multiplications in Fp2\mathbb{F}_{p^2}, each taking O(log⁡p)O(\log p) bit operations — giving O(log⁡2p)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.

Where It Matters

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 xx-coordinate and one bit. To recover yy you solve y2≡x3+ax+b(modp)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 t2≡n(modq)t^2 \equiv n \pmod{q} over small primes qq 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−1p - 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 pp 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.

Conclusion

Cipolla's algorithm is a masterclass in mathematical detour. The direct road — try every remainder — takes O(p)O(p) steps and is useless for large primes. The clever road — invent a number ω\omega whose square is a non-residue, work in Fp2\mathbb{F}_{p^2} for a moment, then come back — takes O(log⁡2p)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cipolla-algorithm/Content licensed under CC BY-NC 4.0.