THE GARDEN

Quadratic Residue

Updated 13 Sep 2026

• •

  What it is

  • •

    An integer $a$ is a quadratic residue (QR) modulo $n$ if some $x$ satisfies $x^2 \equiv a \pmod n$. Modulo a prime, the QRs form a subgroup, which gives the set a useful multiplicative structure.

• •

  When to apply

  • •

    A challenge gives a prime modulus and asks you to identify or find the root of a QR among candidates, or — more subtly — leaks information through whether ciphertext values are QRs or not (a residuosity oracle).

• •

  Symbols and assumptions

  • •

    $p$ is an odd prime. For the multiplicative subgroup, a quadratic residue is a nonzero value $a=x^2\bmod p$ with $x\ne0$. Zero is a square too, but is excluded from that group.

• •

  Math — step by step

  • •
    1. Squaring identifies $x$ and $-x$: their squares agree. Over a field these are the only two roots of a nonzero square, because $(x-y)(x+y)=0$ implies $x=y$ or $x=-y$.
  • •
    2. The $p-1$ nonzero inputs therefore produce exactly $(p-1)/2$ nonzero squares. Their products and inverses are squares: $x^2y^2=(xy)^2$ and $(x^2)^{-1}=(x^{-1})^2$.
  • •
    3. These squares form an index-two subgroup. Multiplying by a square preserves whether a nonzero element is a square. This is the property exploited by ElGamal (Subgroup and Quadratic-Residue Leakage).
• •

  Worked example

  • •

    Modulo 11, square the representatives 1 through 5: $1^2=1$, $2^2=4$, $3^2=9$, $4^2=16\equiv5$, $5^2=25\equiv3$. Thus QR $=\{1,3,4,5,9\}$.

  • •

    The roots of 5 are 4 and $11-4=7$: $4^2\equiv7^2\equiv5$. The remaining nonzero residues $\{2,6,7,8,10\}$ are non-squares.

  • •

    Test multiplication: QR×QR gives $3\cdot4=12\equiv1$; QR×NQR gives $3\cdot2=6$; NQR×NQR gives $2\cdot6=12\equiv1$.

• •

  Getting square root of a if $p \equiv 3 \pmod 4$

  • •

    from here https://math.stackexchange.com/questions/1273690/when-p-3-pmod-4-show-that-ap1-4-pmod-p-is-a-square-root-of-a we know that when $p \equiv 3 \mod 4$, we can get square root of $a$, lets call it $x$ by calculating

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

  Python

  • •

    def is_qr(a, p):
        return pow(a, (p - 1) // 2, p) == 1
    

• •

  SageMath

  • •

    Mod(6, 29).is_square()      # True
    Mod(6, 29).sqrt()           # 8 (or 21, the other root)
    

• •

  Related

  • •

    Legendre Symbol

  • •

    Tonelli-Shanks Algorithm

• •

  Cards

  • •

    What are the three multiplicative closure rules for quadratic residues mod a prime?

    • •

      $QR \cdot QR = QR$, $QR \cdot NQR = NQR$, $NQR \cdot NQR = QR$

  • •

    How do you test if $a$ is a QR mod prime $p$ without brute force?

    • •

      Check that $a^{(p-1)/2} \equiv 1 \pmod p$.

◌ Explore connections in Graph view