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?

Ref: Solving quadratic congruences with odd prime moduli

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:

For more information, please refer to wiki .

 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

$p=193$ and $a = 67$
$p=569$ and $a = 367$
$p=34369$ and $a = 19170$
$p=50753$ and $a = 12957$
$p=97241$ and $a = 47861$
$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

From Solving quadratic congruences with odd prime moduli :

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.