TAOCP 4.6.2 Exercise 15
Given a prime $p$ and an integer $u$ for which a square root modulo $p$ is known to exist, we seek an efficient algorithm for finding an integer $v$ satisfying v^2 \equiv u \pmod p.
Section 4.6.2: Factorization of Polynomials
Exercise 15. ▶ [M27] (Square roots modulo a prime.) Design an algorithm to calculate the square root of a given integer $u$ modulo a given prime $p$, that is, to find an integer $v$ such that $v^2 \equiv u \pmod{p}$, assuming that such a $v$ exists. Your algorithm should be efficient even for very large primes $p$. [For $p \ne 2$, a solution to this problem leads to a procedure for solving any given quadratic equation modulo $p$, using the quadratic formula in the usual
way.) Hint: Consider what happens when the factorization methods of this section are applied to the polynomial $x^2 - a$.
Verified: no
Solve time: 2m38s
Setup
Given a prime $p$ and an integer $u$ for which a square root modulo $p$ is known to exist, we seek an efficient algorithm for finding an integer $v$ satisfying
$$ v^2 \equiv u \pmod p. $$
The hint suggests applying the factorization methods of this section to
$$ f(x)=x^2-u. $$
Since a square root of $u$ exists modulo $p$, the polynomial $f(x)$ has two roots in the field of $p$ elements when $p\ne2$, and therefore factors as
$$ x^2-u=(x-v)(x+v). $$
The problem is to recover one of these linear factors efficiently by means of Berlekamp's method.
Solution
First consider the case $p=2$. Then every element is its own square, so the unique solution is
$$ v\equiv u \pmod2. $$
Assume henceforth that $p$ is odd.
Let
$$ f(x)=x^2-u. $$
Because a square root exists, $f(x)$ is squarefree and has exactly two distinct linear factors. In the notation of Algorithm B, we therefore have $r=2$.
Since $\deg(f)=2$, the matrix $Q$ is $2\times2$. By (12),
$$ x^{pk}\equiv q_{k,1}x+q_{k,0}\pmod{f(x)}. $$
The first row is $(1,0)$ because $x^0=1$.
Since $x^2\equiv u\pmod{f(x)}$,
$$ x^p=x(x^2)^{(p-1)/2} \equiv x,u^{(p-1)/2} \pmod{f(x)}. $$
Because $u$ is assumed to be a quadratic residue, Euler's criterion gives
$$ u^{(p-1)/2}\equiv1\pmod p. $$
Hence
$$ x^p\equiv x\pmod{f(x)}. $$
Therefore
$$ Q= \begin{pmatrix} 1&0\ 0&1 \end{pmatrix}, $$
so the null space of $Q-I$ has dimension $2$, in agreement with the fact that $f(x)$ has two irreducible factors.
A basis for the solution space of (8) is represented by the polynomials
$$ 1,\qquad x. $$
The nontrivial solution is therefore
$$ v(x)=x. $$
Step B4 instructs us to compute
$$ \gcd(f(x),x-s), \qquad 0\le s<p. $$
Since
$$ \gcd(x^2-u,x-s)\ne1 $$
precisely when $s^2\equiv u\pmod p$, the problem reduces to finding an $s$ for which the greatest common divisor is nontrivial.
Instead of trying all $p$ values of $s$, choose a random polynomial
$$ g(x)=x+a, \qquad a\in{0,1,\ldots,p-1}. $$
Modulo either factor $(x-v)$ or $(x+v)$, the value of $g$ is respectively
$$ a+v,\qquad a-v. $$
By equation (10),
$$ g(x)^{(p-1)/2} $$
takes the value
$$ \left(\frac{a+v}{p}\right) $$
on one factor and
$$ \left(\frac{a-v}{p}\right) $$
on the other, where $\left(\frac{\cdot}{p}\right)$ denotes the Legendre symbol.
If these two symbols are different, then
$$ g(x)^{(p-1)/2}-1 $$
vanishes modulo one linear factor and not the other. Consequently
$$ d(x)= \gcd!\left( f(x), g(x)^{(p-1)/2}-1 \right) $$
is a nontrivial factor of $f(x)$.
The symbols are equal only when $a+v$ and $a-v$ are simultaneously quadratic residues or simultaneously quadratic nonresidues. As $a$ ranges over the field, exactly half of the choices produce opposite symbols. Therefore a random choice of $a$ succeeds with probability $1/2$.
Whenever a nontrivial factor is obtained, it has degree $1$ and must be of the form
$$ x-v \quad\text{or}\quad x+v. $$
If
$$ d(x)=x-c, $$
then
$$ c^2\equiv u\pmod p, $$
and $c$ is a desired square root.
The resulting algorithm is therefore:
Choose random $a$ modulo $p$.
Compute
$$ h(x)\equiv(x+a)^{(p-1)/2}\pmod{x^2-u}. $$
Compute
$$ d(x)=\gcd!\left(x^2-u,;h(x)-1\right). $$
If $d(x)=1$ or $d(x)=x^2-u$, choose another $a$.
If $d(x)=x-c$, output $c$.
The expected number of trials is $2$, and each trial requires $O(\log p)$ polynomial multiplications modulo a quadratic polynomial, hence the method remains efficient even when $p$ is very large.
Verification
Let
$$ d(x)=x-c $$
be the factor returned by the algorithm. Since $d(x)$ divides $x^2-u$,
$$ x^2-u=(x-c)(x+c) $$
in the field of $p$ elements. Substituting $x=c$ gives
$$ c^2-u\equiv0\pmod p, $$
hence
$$ c^2\equiv u\pmod p. $$
Therefore every output is a correct square root.
Conversely, if $v^2\equiv u\pmod p$, then
$$ x^2-u=(x-v)(x+v). $$
For any choice of $a$ for which
$$ \left(\frac{a+v}{p}\right) \ne \left(\frac{a-v}{p}\right), $$
the polynomial
$$ \gcd!\left(x^2-u,,(x+a)^{(p-1)/2}-1\right) $$
equals one of the two linear factors. Such choices occur with probability $1/2$, so repeated random selections eventually produce a factor and hence a square root.
Notes
This procedure is essentially the specialization of Berlekamp's factorization method to the polynomial $x^2-u$. In modern terminology it is the probabilistic algorithm of Berlekamp and Rabin for extracting square roots modulo a prime. For solving a quadratic congruence
$$ ax^2+bx+c\equiv0\pmod p, $$
with $a\not\equiv0\pmod p$, the usual quadratic formula reduces the problem to finding a square root of the discriminant
$$ b^2-4ac, $$
after which the solutions are
$$ x\equiv \frac{-b\pm\sqrt{,b^2-4ac,}}{2a} \pmod p. $$
The desired square root of $u$ is therefore obtained by factoring $x^2-u$ modulo $p$.
$$ \boxed{\text{Factor }x^2-u\text{ by Berlekamp's method; a resulting linear factor }x-c\text{ yields }c^2\equiv u\pmod p.} $$