# How to Solve Quadratic Congruences With Prime Moduli?

## Quadratic Congruences with prime moduli

Let $a$ be a quadratic residue modulo $p$, i.e., the Legendre Symbol $(\frac{a}{p}) = 1$.

Then, the equation $$x^2 \equiv a \pmod{p} \tag{1}$$ has exactly two solutions $x_0, p - x_0$.

How to find the two solutions?

### Case 1: $p \equiv 3 \pmod{4}$

For this case, an explicit formula exists that can handle this easily: $$x_0 \equiv a^{\frac{p + 1}{4}} \pmod{p} \tag{2}$$ Proof: \begin{aligned} x_0^2 & \equiv a^{\frac{p + 1}{4}\cdot 2} \newline &\equiv a^{\frac{p + 1}{2}} \newline &\equiv a\cdot a^{\frac{p - 1}{2}} \newline &\equiv a\cdot 1 \newline &\equiv a \pmod{p} \end{aligned}

For the last second $\equiv$, Euler’s criterion says that $a^{\frac{p-1}{2}} \equiv (\frac{a}{p}) \pmod{p}$, and since here $a$ is a QR, thus $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$.

### Case 2: $p \equiv 1 \pmod{4}$

No trivial solution exists for this case, but several ad-hoc algorithms, one of which is Tonelli-Shanks Algorithm, could solve this.

Tonelli-Shanks Algorithm Implementation:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41  def TonelliShanksAlgorithm(a, p): ''' Solve the equation x^2 ≡ a (mod p) where p ≡ 1 (mod 4). returns all the two solutions to the equation. ''' # 1. Factor p - 1 into 2^S * Q where Q is odd. Q = p - 1 S = 0 while Q & 1 == 0: S += 1 Q //= 2 # 2. Find a NR(p). y = 2 while Legendre(y, p) != -1: y += 1 # 3. Calculate the four quantities. R = pow(a, (Q + 1) // 2, p) c = pow(y, Q, p) t = pow(a, Q, p) E = S # 4. Loop. while t != 1: for i in range(1, E): if pow(t, 2 ** i, p) == 1: break b = pow(c, 2 ** (E - i - 1), p) R = R * b % p c = pow(b, 2, p) t = c * t % p E = i return [R, p - R] def Legendre(a, p): ''' The Legendre Sybmol. returns 1 if a is QR(p), or -1 if NR(p), or 0 if a divides p. ''' if a % p == 0: return 0 # Euler's Criterion return 1 if pow(a, (p - 1) // 2, p) == 1 else -1 

#### Example

1. $p=193$ and $a = 67$
2. $p=569$ and $a = 367$
3. $p=34369$ and $a = 19170$
4. $p=50753$ and $a = 12957$
5. $p=97241$ and $a = 47861$
6. $p=2773676993$ and $a = 1342865413$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  # ... problems = [ (67, 193), (367, 569), (19170, 34369), (12957, 50753), (47861, 97241), (1342865413, 2773676993) ] for solutions in map(lambda xy: TonelliShanksAlgorithm(xy[0], xy[1]), problems): print(solutions) # output: # [35, 158] # [103, 466] # [19136, 15233] # [30781, 19972] # [45733, 51508] # [1056882643, 1716794350] 

#### Computational Analysis

According to Wikipedia:

The Tonelli–Shanks algorithm requires (on average over all possible input (quadratic residues and quadratic nonresidues)) $$2m + 2k + \frac{S(S-1)}{4} + \frac{1}{2^{S-1}} - 9$$ modular multiplications, where $m$ is the number of digits in the binary representation of $p$ and $k$ is the number of ones in the binary representation of $p$.

### Summary

Overall, the Tonelli-Shanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the Tonelli-Shanks algorithm or the explicit formula (2). On the other hand, the equation $$x^2 \equiv a \pmod{n} \tag{3}$$ is difficult to solve where the modulus $n$ is the product of two large primes $p$ and $q$. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of $n$ is known, equation (3) is solvable and the Tonelli-Shanks algorithm along with the Chinese remainder theorem play a crucial role.