Finding Square Roots

We return in this section to the question of computing square roots. If $K$ is a field in which $2\neq 0$ , and $a,b,c\in K$ , with $a\neq 0$ , then the solutions to the quadratic equation $ax^2+bx+c=0$ are

$$x = \frac{-b\pm \sqrt{b^2-4ac}}{2a}.$$

Now assume $K=\mathbb{Z}/p\mathbb{Z}{}$ , with $p$ an odd prime. Using Theorem 4.1.7, we can decide whether or not $b^2-4ac$ is a perfect square in $\mathbb{Z}/p\mathbb{Z}{}$ , and hence whether or not $ax^2+bx+c=0$ has a solution in $\mathbb{Z}/p\mathbb{Z}{}$ . However Theorem 4.1.7 says nothing about how to actually find a solution when there is one. Also, note that for this problem we do not need the full quadratic reciprocity law; in practice to decide whether an element of $\mathbb{Z}/p\mathbb{Z}{}$ is a perfect square Proposition 4.2.1 is quite fast, in view of Section 2.3.

Suppose $a\in\mathbb{Z}/p\mathbb{Z}{}$ is a nonzero quadratic residue. If $p\equiv 3 \pmod{4}$ then $b=a^{\frac{p+1}{4}}$ is a square root of $a$ because

$$b^2 = a^{\frac{p+1}{2}} = a^{\frac{p-1}{2} + 1} = a^{\frac{p-1}{2}} \cdot a = \left(\frac{a}{p}\right) \cdot a = a.$$

We can compute $b$ in time polynomial in the number of digits of $p$ using the powering algorithm of Section 2.3.

Suppose next that $p\equiv 1\pmod{4}$ . Unfortunately, we do not know a deterministic algorithm that takes as input $a$ and $p$ , outputs a square root of $a$ modulo $p$ when one exists, and is polynomial-time in $\log(p)$ .

Remark 4.5   There is an algorithm due to Schoof [#!schoof:sqrt!#] that computes the square root of $a$ in time $O((\sqrt(\vert a\vert)^{1/2 + \varepsilon } \cdot \log(p))^9)$ . This beautiful algorithm (which makes use of elliptic curves) is not polynomial time in the sense described above since for large $a$ it takes exponentially longer than for small $a$ .

We next describe a probabilistic algorithm to compute a square root of $a$ modulo $p$ , which is very quick in practice. Recall the definition of ring from Definition 2.1.3. We will also need the notion of ring homomorphism and isomorphism.

Definition 4.5 (Homomorphism of Rings)   Let $R$ and $S$ be rings. A homomorphism of rings $\varphi :R\to S$ is a map such that for all $a,b\in R$ we have

• $\varphi (ab) = \varphi (a) \varphi (b)$ ,
• $\varphi (a+b) = \varphi (a) + \varphi (b)$ , and
• $\varphi (1) = 1$ .

An isomorphism $\varphi :R\to S$ of rings is a ring homomorphism that is bijective.

Consider the (quotient) ring

$$R = (\mathbb{Z}/p\mathbb{Z}{})[x]/(x^2 - a)$$

defined as follows. We have

$$R = \{ u + v \alpha : u, v \in \mathbb{Z}/p\mathbb{Z}{}\}$$

with multiplication defined by

$$(u+v\alpha)(z+w\alpha) = (uz + awv) + (uw+vz)\alpha.$$

Here $\alpha$ corresponds to the class of $x$ in the quotient ring.

SAGE Example 4.5   We define and work with the quotient ring $R$ above in SAGE as follows (for $p=13$ ):

sage: S.<x> = PolynomialRing(GF(13)) 
sage: R.<alpha> = S.quotient(x^2 - 3) 
sage: (2+3*alpha)*(1+2*alpha)
7*alpha + 7

Let $b$ and $c$ be the square roots of $a$ in $\mathbb{Z}/p\mathbb{Z}{}$ (though we cannot easily compute $b$ and $c$ yet, we can consider them in order to deduce an algorithm to find them). We have ring homomorphisms $f:R\to \mathbb{Z}/p\mathbb{Z}{}$ and $g:R\to \mathbb{Z}/p\mathbb{Z}{}$ given by $f(u+v\alpha) = u+vb$ and $g(u+v\alpha) = u + vc$ . Together these define a ring isomorphism

$$\varphi : R \longrightarrow \mathbb{Z}/p\mathbb{Z}{} \times \mathbb{Z}/p\mathbb{Z}{}$$

given by $\varphi (u+v\alpha) = (u+vb,u+vc)$ . Choose in some way a random element $z$ of $(\mathbb{Z}/p\mathbb{Z}{})^*$ , and define $u,v\in\mathbb{Z}/p\mathbb{Z}{}$ by

$$u+v\alpha = (1+z\alpha)^{\frac{p-1}{2}},$$

where we compute $(1+z\alpha)^{\frac{p-1}{2}}$ quickly using an analogue of the binary powering algorithm of Section 2.3.2. If $v=0$ we try again with another random $z$ . If $v\neq 0$ we can quickly find the desired square roots $b$ and $c$ as follows. The quantity $u+vb$ is a $(p-1)/2$ power in $\mathbb{Z}/p\mathbb{Z}{}$ , so it equals either 0 , $1$ , or $-1$ , so $b = -u/v$ , $(1-u)/v$ , or $(-1-u)/v$ , respectively. Since we know $u$ and $v$ we can try each of $-u/v$ , $(1-u)/v$ , and $(-1-u)/v$ and see which is a square root of $a$ .

Example 4.5   Continuing Example 4.1.8, we find a square root of $69$ modulo $389$ . We apply the algorithm described above in the case $p\equiv 1\pmod{4}$ . We first choose the random $z=24$ and find that $(1+24\alpha)^{194} = -1.$ The coefficient of $\alpha$ in the power is 0 , and we try again with $z=51$ . This time we have $(1+51\alpha)^{194} = 239\alpha = u +v\alpha$ . The inverse of $239$ in $\mathbb{Z}/389\mathbb{Z}{}$ is $153$ , so we consider the following three possibilities for a square root of $69$ :

$$-\frac{u}{v} = 0 \qquad \frac{1-u}{v} = 153\qquad -\frac{1-u}{v} = -153.$$

Thus $153$ and $-153$ are the square roots of $69$ in $\mathbb{Z}/389\mathbb{Z}{}$ .

SAGE Example 4.5   We implement the above algorithm in SAGE and illustrate it with some examples.

sage: def find_sqrt(a, p):
...    assert (p-1)%4 == 0
...    assert legendre_symbol(a,p) == 1
...    S.<x> = PolynomialRing(GF(p))
...    R.<alpha> = S.quotient(x^2 - a)
...    while True:
...        z = GF(p).random_element()
...        w = (1 + z*alpha)^((p-1)//2)
...        (u, v) = (w[0], w[1])
...        if v != 0: break
...    if (-u/v)^2 == a: return -u/v
...    if ((1-u)/v)^2 == a: return (1-u)/v
...    if ((-1-u)/v)^2 == a: return (-1-u)/v
...        
sage: b = find_sqrt(3,13)
sage: b                        # random: either 9 or 3
9
sage: b^2   
3
sage: b = find_sqrt(3,13)
sage: b                        # see, it's random
4
sage: find_sqrt(5,389)         # random: either 303 or 86
303
sage: find_sqrt(5,389)         # see, it's random
86