Exercise 2.9.4 (Modular square roots)

Question

With the aid of a pocket calculator, use RESSOL to find solutions of the following congruences:

$
\begin{array}{ll}
(a)\ x^2 \equiv 10 \pmod {13};\qquad&(b)\ x^2 \equiv 5 \pmod {19};\
(c)\ x^2 \equiv 3 \pmod {11}; \qquad & (d)\ x^2 \equiv 7 \pmod {29}.
\end{array}
$

Richard Ganaye · Accepted Answer

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof} 
\begin{enumerate}
\item[(a)] Here $p = 13$ and $a = 10$. Note that $p-1 = 12 = 2^2 \cdot 3 = 2^k m$, where $k=2, m= 3$.
Starting from $\left(a^{\frac{m+1}{2}}ight)^2 = a \cdot a^{m},$
we obtain
\begin{align}
r^2 \equiv an \pmod p,
\end{align}
where $r = a^{\frac{m+1}{2}} = 10^2 \equiv 9 \pmod {13}$, and $n = a^m = 1000 \equiv -1 \pmod {13}$.

We choose a generator quadratic non residue $z$. Since $2^6 \equiv \legendre{2}{13} = -1 \pmod {13}$, we take $z = 2$.

(Then $\overline{z}$ is a generator of $(\Z/13\Z)^*$, and $\overline{c} = \overline{z}^m = \overline{2}^3 = \overline{8}$ is a generator of the subgroup of elements whose order is a power of $2$.)

The order of $c^m = 8$ is $2^k = 2^2$. The order of $n \equiv -1 \pmod {13}$ is $2$.

(Since $n^2 = n^{2^{k-1}} \equiv a^{\frac{p-1}{2}} = 1$, we verify anew that $a$ is a quadratic residue.)

Therefore $n$ and $c^2$ have the same order $2^1$.
Multiplying (1) by $c^2$, we obtain
$$(rc)^2 \equiv a (nc^2) \pmod p,$$
that is $r_1^2 \equiv a n_1 \pmod p$, where $r_1 = rc \equiv 7 \pmod {13}$, and $n_1 = nc^2$ must have order $2^{k_1}$, with $k_1 < 1$. Indeed, $n_1 = - 8^2 \equiv 1 \pmod {13}$.

Therefore $7^2 \equiv 10 \pmod{13}$, and $7$ is a square root of $10$ modulo $13$. The other root is $-7 \equiv 6 \pmod{13}$.

Verification:  $7^2 = 49 = 3 	imes 13 + 10$.

\item[(b)] Similarly, for the equation $x^2 \equiv 5 \pmod {19}$, we obtain $z = 3, c = -1$, and $n \equiv 1, r \equiv  9 \pmod{19}$. Since $n = 1$, there is no loop, and the roots of $5$ modulo $19$ are $\pm 9$.

\item[(c)] With $z = 6, c = 10$, we obtain $ n = 1, r = 5$. No loop : $\pm 5$ are the roots of  $3$ modulo $11$.

Note: in the cases (b) and (c), we have $p \equiv 3 \pmod{4}$, thus the roots are given by $\pm a^{\frac{p+1}{4}}$.

\item[(d)] With $z = 8, c = 17$, we obtain $n = 1, r = 23$, thus $6,  23$ are the roots of $7$ modulo $29$.

\end{enumerate}
\end{proof}

A Python code to implement the RESSOL algorithm is
\begin{verbatim}
from random import randint

def legendre(a, p):
    resu = pow(a, (p - 1) // 2, p)
    if resu > p//2:
        resu -= p
    return resu
    
def ressol(a, p):
    assert legendre(a, p) == 1, "not a square (mod p)"
    
    m = p - 1
    s = 0
    while m % 2 == 0:
        m //= 2
        s += 1
        
    found = False
    while not found:
        xi = randint(2, p - 2)
        if -1 == legendre(xi, p):
            found = True
            
    c = pow(xi, m , p)                      # o(c) = 2^s
    r = pow(a, (m+1) // 2, p)
    n = pow(a, m, p)
    while n!=1:
        i = 0
        npower = n
        while npower != 1:
            npower = (npower * npower) % p
            i = i + 1
                                            # o(n) = 2^i
        b = pow(c, 2 ** (s-i-1), p)         # o(b^2) = 2^i = o(n)
        r = (r * b) % p
        n = (n * b * b) % p
    return(r)

if __name__ == '__main__':
    print(ressol(43,97))
\end{verbatim}

Exercise 2.9.4 (Modular square roots)

Answers

Comments

Exercise 2.9.4 (Modular square roots)

Answers

Comments

Add answer