Quadratic Residues
1. The Concept: Quadratic Residues
In modular arithmetic, an integer $a$ is considered a Quadratic Residue (QR) modulo $n$ if it has a perfect square root under that modulus. Mathematically, there exists some integer $x$ such that:
$$x^2 \equiv a \pmod n$$
If no such integer $x$ exists, then $a$ is a Quadratic Non-Residue (QNR).
Brute Force Implementation
For small numbers, we can iterate through all possible values in the modulus to see if their square matches our target number.
Python
number = int(input("Enter the number: "))
mod = int(input("Enter the mod: "))
for i in range(mod):
if pow(i, 2, mod) == number:
print(f"The QR is {i}")
break
else:
print(f"{number} is a Quadratic non-residue")2. The Legendre Symbol & Euler’s Criterion
To handle massive primes instantly, we use the Legendre Symbol $\left(\frac{a}{p}\right)$, which acts as a mathematical boolean:
- $\left(\frac{a}{p}\right) = 1 \implies a$ is a Quadratic Residue.
- $\left(\frac{a}{p}\right) = -1 \implies a$ is a Quadratic Non-Residue.
- $\left(\frac{a}{p}\right) = 0 \implies a \equiv 0 \pmod p$.
We calculate this using Euler’s Criterion:
$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$$
Proof of Euler’s Criterion
Case 1: $a$ is a Quadratic Residue $\left(\frac{a}{p}\right) = 1$
Assume $a$ is a QR. Therefore, $x_0^2 \equiv a \pmod p$. Substitute this into Euler’s formula:
$$a^{\frac{p-1}{2}} \equiv (x_0^2)^{\frac{p-1}{2}} \equiv x_0^{p-1} \pmod p$$
By Fermat’s Little Theorem, $x_0^{p-1} \equiv 1 \pmod p$. Thus, the criterion yields $1$.
Case 2: $a$ is a Quadratic Non-Residue $\left(\frac{a}{p}\right) = -1$
If $a$ is a QNR, for any integer $k$ in ${1, 2, \dots, p-1}$, the equation $kx \equiv a \pmod p$ has a unique solution where $x \neq k$.
This means we can perfectly pair up all integers from $1$ to $p-1$. Since there are $p-1$ total integers, we get exactly $\frac{p-1}{2}$ pairs.
Each pair multiplies to $a$. If we multiply all the pairs together, we get $a$ multiplied by itself $\frac{p-1}{2}$ times, which is $a^{\frac{p-1}{2}}$.
Simultaneously, multiplying all numbers from $1$ to $p-1$ gives $(p-1)!$.
$$(p-1)! \equiv a^{\frac{p-1}{2}} \pmod p$$
By Wilson’s Theorem, $(p-1)! \equiv -1 \pmod p$. Thus, the criterion yields $-1$.
3. The Anatomy of Primes
By the Division Algorithm ($n = 4k + r$), every integer falls into one of four buckets modulo 4:
- $0 \pmod 4$: Even (Not prime)
- $2 \pmod 4$: Even (Not prime, except 2)
- $1 \pmod 4$: Odd (Can be prime)
- $3 \pmod 4$: Odd (Can be prime)
Therefore, every odd prime strictly falls into either the $1 \pmod 4$ or $3 \pmod 4$ category. This dictates how we find square roots.
Why the number 4?
The number 4 dictates our math because finding a root requires dividing an exponent by $2$ twice:
-
Euler’s Criterion divides the exponent by $2$: $\frac{p-1}{2}$
-
To find a square root, the final exponent must be halved again to leave a perfect square.
$2 \times 2 = 4$.
4. Finding Square Roots: The $p \equiv 3 \pmod 4$ Shortcut
If a prime is $3 \pmod 4$, we can algebraically prove that $p+1$ is perfectly divisible by $4$. Let $p = 4k + 3$.
$$p + 1 = (4k + 3) + 1 = 4k + 4 = 4(k + 1)$$
Because of this clean divisibility, we can manipulate Euler’s Criterion to find the square root $x$ instantly:
$$a^{\frac{p-1}{2}} \equiv 1 \implies a^{\frac{p+1}{2}} \equiv a \implies \left(a^{\frac{p+1}{4}}\right)^2 \equiv a \pmod p$$
The square root is simply: $x \equiv a^{\frac{p+1}{4}} \pmod p$.
Optimized CTF Script
Python
# legendre_symbol.py
def is_QR(number: int, mod: int):
"""Uses Euler's Criterion to check for Residuosity."""
if pow(number, ((mod - 1) // 2), mod) == 1:
return True
elif pow(number, ((mod - 1) // 2), mod) == mod - 1:
return False
def find_sqrt_blum(number: int, mod: int):
"""Finds the square root IF mod == 3 mod 4."""
if is_QR(number, mod):
return pow(number, ((mod + 1) // 4), mod)
else:
print("Root does not exist.")
# Example 1024-bit prime (p = 3 mod 4)
p = 1015240351745398904854085756710852617887589651890601644843856908014661673566670366779329988897254765824217387885007387385031343561581972474738502735653492495738672512802535646989397687004894019607670077164139328518389376418801572639369859548816578894975834855355276135784576283991739718105416708385433091591395. Finding Square Roots: The $p \equiv 1 \pmod 4$
If $p = 4k + 1$, the exponent $\frac{p+1}{2}$ becomes $\frac{4k+2}{2} = 2k + 1$ (an odd number). We cannot divide an odd number by 2 in modular arithmetic. The shortcut fails.
The Tonelli-Shanks Algorithm
To fix this, we factor all the powers of 2 out of $p-1$ until we are left with an odd number $Q$:
$$p - 1 = Q \cdot 2^S$$
We rely on a Golden Rule state equation: $R^2 \equiv a \cdot t \pmod p$.
- $R$ (Guess): Starts as $a^{(Q+1)/2} \pmod p$.
- $t$ (Error): Starts as $a^Q \pmod p$. If $t=1$, $R$ is our root.
- $c$ (Wrench): A “fudge factor” generated from a random QNR.
- $M$ (Timer): A depth gauge starting at $S$.
The loop repeatedly squares $t$ to measure the error depth ($i$). It then bit-shifts the wrench $c$ to craft a specific fix $b$, and applies it to $R$ and $t$, driving $t$ to $1$.
Python
def tonelli_shanks(a, p):
"""Finds the square root of 'a' mod 'p' for ANY prime."""
if pow(a, (p - 1) // 2, p) != 1:
return "Not a QR!"
if a == 0: return 0
# 1. Factor p - 1 into Q * 2^S
Q = p - 1
S = 0
while Q % 2 == 0:
Q //= 2
S += 1
if S == 1:
return pow(a, (p + 1) // 4, p)
# 2. Find a QNR
z = 2
while pow(z, (p - 1) // 2, p) != p - 1:
z += 1
# 3. Initialize Variables
M = S
c = pow(z, Q, p)
t = pow(a, Q, p)
R = pow(a, (Q + 1) // 2, p)
# 4. The Loop
while t != 0 and t != 1:
t2i = t
i = 0
for i in range(1, M):
t2i = (t2i * t2i) % p
if t2i == 1: break
# Craft the fix
b = pow(c, 1 << (M - i - 1), p)
# Apply the fix
M = i
c = (b * b) % p
t = (t * c) % p
R = (R * b) % p
return R