THE GARDEN

Legendre Symbol

Updated 13 Sep 2026

• •

  What it is

  • •

    $\left(\frac{a}{p}\right)$, computed as $a^{(p-1)/2} \bmod p$, tells you whether $a$ is a quadratic residue (1), a non-residue (-1, shown as $p−1$), or $\equiv 0 \pmod p$ (0). Python/Sage's kronecker() generalizes it to composite moduli.

• •

  When to apply

  • •

    You need fast QR/non-QR classification on a large prime without brute-forcing the field — including as a side-channel, when a ciphertext scheme leaks a bit per value depending on its residuosity.

• •

  Symbols and assumptions

  • •

    For odd prime $p$, the Legendre symbol $\chi_p(a)$ is 0 if $a\equiv0$, +1 for a nonzero square, and −1 for a non-square. The fraction-like notation $(a/p)$ is a symbol, not division.

• •

  Math — step by step

  • •
    1. Euler’s criterion computes it: $a^{(p-1)/2}\equiv\chi_p(a)\pmod p$. In code, −1 appears as the nonnegative residue $p-1$.
  • •
    2. For nonzero $a=g^k$ with a primitive root $g$, even $k$ means $a$ is a square. Since $g^{(p-1)/2}=-1$, raising $a$ to $(p-1)/2$ gives $(-1)^k$, revealing that parity.
  • •
    3. Exponentiation distributes over multiplication, so $\chi_p(ab)=\chi_p(a)\chi_p(b)$. A square mask has symbol +1 and cannot hide the symbol of the value it multiplies.
  • •
    4. Testing for a square and finding a square root are different tasks. Euler’s criterion classifies; Tonelli-Shanks Algorithm finds a root. A Jacobi symbol +1 for composite modulus does not prove the input is a square.
• •

  Worked example

  • •

    Let $p=11$, so the exponent is 5. For 2: $2^5=32\equiv10=-1\pmod{11}$, hence 2 is a non-square.

  • •

    For 4: $4^2\equiv5$, $4^4\equiv3$, and $4^5\equiv12\equiv1$, hence 4 is a square.

  • •

    Mask both with the square 4. The results are $4\cdot2=8$ and $4\cdot4=5\pmod{11}$. Their fifth powers are 10 and 1, respectively: the class survives the mask.

  • •

    For the special input 2, $\chi_p(2)=(-1)^{(p^2-1)/8}$: primes congruent to 1 or 7 modulo 8 give +1; primes congruent to 3 or 5 give −1.

• •

  Python

  • •

    def legendre(a, p):
        ls = pow(a, (p - 1) // 2, p)
        return -1 if ls == p - 1 else ls
    

• •

  SageMath

  • •

    legendre_symbol(6, 29)   # 1
    kronecker(6, 29)         # 1, generalizes to composite moduli too
    

• •

  Related

  • •

    Quadratic Residue

  • •

    Tonelli-Shanks Algorithm

• •

  Cards

  • •

    What three values can the legendre symbol take, and what does each mean?

    • •

      1 = quadratic residue, -1 = non-residue, 0 = a ≡ 0 mod p.

  • •

    What's a real-world CTF use of the Legendre symbol beyond just finding QRs?

    • •

      As an oracle: testing residuosity of each ciphertext value can leak a bit of hidden information per value.

◌ Explore connections in Graph view