Cipolla's Algorithm

Purpose: Compute a modular square root $x$ with $x^2\equiv a(\mathrm{mod}p)$ in $O(\log p)$ multiplications — with no dependence on the 2-adic valuation of $p-1$, unlike Tonelli-Shanks.

Algorithm

1. Verify $a$ is a quadratic residue: $a^{(p-1)/2}\equiv 1$.
2. Find $t$ such that $t^2-a$ is a non-residue. Try $t=1,2,3,\dots$; roughly half of all $t$ work, so this takes $O(1)$ attempts on average.
3. Work in the quadratic field extension ${\mathbb{F}}_{p^2}={\mathbb{F}}_p[\omega ]/({\omega }^2-(t^2-a))$ — i.e. treat numbers as pairs $u+v\omega$ with ${\omega }^2=t^2-a$.
4. The answer is
   $x=(t+\omega {)}^{\frac{p+1}{2}}\text{computed in }{\mathbb{F}}_{p^2}.$
   The result is guaranteed to have zero $\omega$-component.

Code

long long P, W;                                   // modulus and omega^2
 
struct F2 { long long a, b; };                    // a + b*omega
 
F2 mul(F2 x, F2 y) {
    return { (x.a * y.a + W % P * (x.b * y.b % P)) % P,
             (x.a * y.b + x.b * y.a) % P };
}
 
long long cipolla(long long a, long long p) {
    P = p; a %= p; if (a < 0) a += p;
    if (a == 0) return 0;
    if (powmod(a, (p - 1) / 2, p) != 1) return -1;      // not a residue
 
    long long t = 1;
    while (powmod(((t * t - a) % p + p) % p, (p - 1) / 2, p) != p - 1) t++;
    W = ((t * t - a) % p + p) % p;
 
    F2 r{1, 0}, base{t, 1};
    long long e = (p + 1) / 2;
    while (e) { if (e & 1) r = mul(r, base); base = mul(base, base); e >>= 1; }
    return r.a;                                          // r.b is provably 0
}

Paradigm

Field extension. The trick is to leave ${\mathbb{F}}_p$, do the work where the answer exists trivially, and come back.

Complexity

• Time: $O(\log p)$ multiplications in ${\mathbb{F}}_{p^2}$ (each is 3-4 multiplications in ${\mathbb{F}}_p$), plus $O(1)$ expected tries for $t$
• Space: $O(1)$

Why It Works

Since ${\omega }^2=t^2-a$ is a non-residue, $\omega \notin {\mathbb{F}}_p$ and ${\mathbb{F}}_{p^2}$ is a genuine field of order $p^2$. In ${\mathbb{F}}_{p^2}$ the Frobenius map $z\mapsto z^p$ is an automorphism fixing exactly ${\mathbb{F}}_p$, and ${\omega }^p=-\omega$. Therefore

$(t+\omega {)}^{p+1}=(t+\omega {)}^p(t+\omega )=(t-\omega )(t+\omega )=t^2-{\omega }^2=t^2-(t^2-a)=a.$

So $x=(t+\omega {)}^{(p+1)/2}$ satisfies $x^2=a$. And $x$ lies in ${\mathbb{F}}_p$ because $x^2=a\in {\mathbb{F}}_p$ implies $x$ is fixed by Frobenius. ∎

Cipolla vs Tonelli-Shanks

	Cipolla	Tonelli-Shanks
Time	$O(\log p)$ mults, no $s$ dependence	$O({\log }^{2}p)$ worst case (with $s$ large)
Arithmetic	needs ${\mathbb{F}}_{p^2}$	stays in ${\mathbb{F}}_p$
Code length	shorter once the extension struct exists	longer control flow
When $p\equiv 3(\mathrm{mod}4)$	not needed — just $a^{(p+1)/4}$	not needed either

In competitive programming the moduli are usually small enough that either works; Tonelli-Shanks is more commonly written, Cipolla is preferable when $p-1$ has a large power of 2 (as it does for NTT-friendly primes like $998244353=119\cdot 2^{23}+1$).

Variants / Use Cases

• Quadratic residues — the underlying theory
• Discrete roots — the $k$-th root generalisation
• Hensel lifting — extend a root mod $p$ to mod $p^k$
• Elliptic curve point decompression — recovering $y$ from $x$ requires a modular square root