Cipolla's Algorithm

Introduction

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.

Try It

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">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

<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 $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.

The Real Complexity

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.

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 $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.

Conclusion

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.

Comments

Loading comments...

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

Cookies & privacy

How to take a square root when arithmetic wraps around