THE GARDEN

Tonelli-Shanks Algorithm

Updated 13 Sep 2026

• •

  What it is

  • •

    An algorithm for computing modular square roots of a quadratic residue mod a prime. When $p \equiv 3 \pmod 4$, a closed-form shortcut applies instead of the full algorithm.

• •

  When to apply

  • •

    Given a QR $a$ and a prime modulus $p$, you're asked to find $x$ with $x^2 \equiv a \pmod p$. Check $p \bmod 4$ first — if it's 3, skip straight to the shortcut.

• •

  Symbols and assumptions

  • •

    We seek $R^2\equiv a\pmod p$ for odd prime $p$ and nonzero square $a$. Write $p-1=Q2^S$ with $Q$ odd; choose a non-square $z$. All multiplications below are modulo $p$.

• •

  Math — step by step

  • •
    1. Check $a=0$ separately; otherwise Euler’s criterion must return 1. If $p\equiv3\pmod4$, $R=a^{(p+1)/4}$ works because $R^2=a\,a^{(p-1)/2}=a$.
  • •
    2. For general $p$, initialize $c=z^Q$, $R=a^{(Q+1)/2}$, $t=a^Q$, $M=S$. The invariant is $R^2\equiv at$; the goal is to reduce $t$ to 1.
  • •
    3. While $t\ne1$, find the smallest $i$ with $t^{2^i}=1$. Set $b=c^{2^{M-i-1}}$, then replace $R$ by $Rb$, $t$ by $tb^2$, $c$ by $b^2$, and $M$ by $i$.
  • •
    4. The correction preserves $R^2=at$ and reduces the remaining power-of-two order. At $t=1$, return $R$ and $p-R$, checking that both square to $a$.
• •

  Worked example

  • •

    Find $\sqrt{10}\bmod13$. We have $12=3\cdot2^2$, so $Q=3,S=2$. Choose $z=2$, a non-square.

  • •

    Initialize: $c=2^3=8$, $R=10^2\bmod13=9$, $t=10^3\bmod13=12$, and $M=2$.

  • •

    Since $12\ne1$ but $12^2\equiv1$, take $i=1$. Then $b=8^{2^{2-1-1}}=8$, and $b^2\equiv12$.

  • •

    Update $R=9\cdot8\bmod13=7$, $t=12\cdot12\bmod13=1$. The roots are 7 and 6; $49\bmod13=36\bmod13=10$.

• •

  Python

  • •

    def modular_sqrt(a, p):
        if p % 4 == 3:
            return pow(a, (p + 1) // 4, p)
        raise NotImplementedError("full Tonelli-Shanks needed")
    

• •

  SageMath

  • •

    Mod(5, 11).sqrt()   # 4 (Sage runs full Tonelli-Shanks internally, works for any prime)
    

• •

  Related

  • •

    Quadratic Residue

  • •

    Legendre Symbol

• •

  Cards

  • •

    What shortcut exists for modular square roots when $p \equiv 3 \pmod 4$?

    • •

      $x \equiv a^{(p+1)/4} \pmod p$

  • •

    What does Tonelli-Shanks compute?

    • •

      A square root of a quadratic residue modulo a prime.

◌ Explore connections in Graph view