# Computing square roots in Zn

The operations of squaring modulo an integer *n* and extracting square roots modulo an integer *n* are frequently used in cryptographic functions. The operation of computing square roots modulo *n* can be performed efficiently when *n* is a prime, but is difficult when *n* is a composite integer whose prime factors are unknown.

## Case (i): n prime

Recall from Remark 3.32 that if *p* is a prime, then it is easy to decide if *a* e Z* is a quadratic residue modulo *p.* If *a* is, in fact, a quadratic residue modulo *p,* then the two square roots of *a* can be efficiently computed, as demonstrated by Algorithm 3.34.

3.34 Algorithm Finding square roots modulo a prime *p*

INPUT: an odd prime *p* and an integer *a,* 1 < *a < p* — 1.

OUTPUT: the two square roots of *a* modulo *p,* provided *a* is a quadratic residue modulo *p.*

- 1. Compute the Legendre symbol (^) using Algorithm 2.149. If (^) = -1 then retum(a does not have a square root modulo
*p)*and terminate. - 2. Select integers
*b,*l<6p.)

- 3. By repeated division by 2, write
*p*— 1 = 2^{s}f, where*t*is odd. - 4. Compute a
^{-1}mod*p*by the extended Euclidean algorithm (Algorithm 2.142). - 5. Set
*c<— b**mod*p*and*r<— a**^*mod^{t+1}^^{2}*p*(Algorithm 2.143). - 6. For
*i*from 1 to s - 1 do the following: - 6.1 Compute
*d =*(r^{2}• a^{-1})^{2}mod*p.* - 6.2 If
*d**=*—1 (mod*p)*then set*r<— r ■ c*mod*p.* - 6.3 Set c<—c
^{2}mod*p.* - 7. Retum(? -r).

Algorithm 3.34 is a randomized algorithm because of the manner in which the quadratic non-residue *b* is selected in step 2. No deterministic polynomial-time algorithm for finding a quadratic non-residue modulo a prime *p* is known (see Remark 2.151).

3.35 Fact Algorithm 3.34 has an expected running time of 0((lgp)^{4}) bit operations.

This running time is obtained by observing that the dominant step (step 6) is executed *s*—1 times, each iteration involving a modular exponentiation and thus taking 0((lg p)^{3}) bit operations (Table 2.5). Since in the worst case s = O(lgp), the running time of 0((lgp)^{4}) follows. When s is small, the loop in step 6 is executed only a small number of tunes, and the running time of Algorithm 3.34 is 0((lgp)^{3}) bit operations. This point is demonstrated next for the special cases *s =* 1 and *s =* 2.

Specializing Algorithm 3.34 to the case *s =* 1 yields the following simple deterministic algorithm for finding square roots when *p =* 3 (mod 4).

3.36 Algorithm Finding square roots modulo a prime *p* where *p* = 3 (mod 4)

INPUT: an odd prime *p* where *p =* 3 (mod 4), and a square *a* e *Q _{p}. *OUTPUT: the two square roots of

*a*modulo

*p.*

- 1. Compute
*r*= rd^{p+1}^^{4}mod*p*(Algorithm 2.143). - 2. Retum(? -r).

Specializing Algorithm 3.34 to the case .s = 2, and using the fact that 2 is a quadratic non-residue modulo *p* when *p =* 5 (mod 8), yields the following simple deterministic algorithm for finding square roots when *p =* 5 (mod 8).

3.37 Algorithm Finding square roots modulo a prime *p* where *p =* 5 (mod 8)

INPUT: an odd prime *p* where *p =* 5 (mod 8), and a square *а* e *Q _{p}. *OUTPUT: the two square roots of

*a*modulo

*p.*

- 1. Compute
*cl =*a.(^{p-1}U^{4}mod*p*(Algorithm 2.143). - 2. If
*d*= 1 then compute*r =*_{a}(P+^{3})/^{8}mod*p.* - 3. If
*d = p*- 1 then compute*r =*2a(4a)^^{p_5}^^{8}mod*p.* - 4. Retum(r,
*—r).* - 3.38 Fact Algorithms 3.36 and 3.37 have running tunes of 0((lgp)
^{3}) bit operations.

Algorithm 3.39 for finding square roots modulo *p* is preferable to Algorithm 3.34 when *p* - 1 = *2** ^{s}t* with

*s*large.

3.39 Algorithm Finding square roots modulo a prime *p*

INPUT: an odd prune *p* and a square *a e Q _{p}.*

OUTPUT: the two square roots of *a* modulo *p.*

- 1. Choose random
*b e Z*until_{p}*b*- 4a is a quadratic non-residue modulo^{2}*p,*i.e., - (6^4a)
_{=}__{L} - 2. Let / be the polynomial
*x*^{2}*- bx +**a*in*Z*_{p}[x], - 3. Compute
*r = x**(*mod^{p+1}^^{2}*f*using Algorithm 2.227. (Note: r will be an integer.) - 4. Retum(r, -r).
- 3.40 Fact Algorithm 3.39 has an expected running time of 0((lgp)
^{3}) bit operations. - 3.41 Note (
*computing square wots in a finite field)*Algorithms 3.34,3.36,3.37, and 3.39 can be extended in a straightforward manner to find square roots in any finite field F_{4}of odd order*q*=*p*prime,^{m},p*m*> 1. Square roots in finite fields of even order can also be computed efficiently via Fact 3.42. - 3.42 Fact Each element
*a*e F2»' has exactly one square root, namely*a*^{2}’"^{1}.

## Case (ii): n composite

The discussion in this subsection is restricted to the case of computing square roots modulo n, where *n* is a product of two distinct odd prunes *p* and *q.* However, all facts presented here generalize to the case where *n* is an arbitrary composite integer.

Unlike the case where *n* is a prime, the problem of deciding whether a given *a* € Z* is a quadratic residue modulo a composite integer *n,* is believed to be a difficult problem. Certainly, if the Jacobi symbol (^) = -1, then *a* is a quadratic non-residue. On the other hand, if (|) = 1, then deciding whether or not a is a quadratic residue is precisely the quadratic residuosity problem, considered in §3.4.

3.43 Definition The *square root modulo nproblem* (SQROOT) is the following: given a composite integer *n* and a quadratic residue *a* modulo *n* (i.e. *a e Q _{n}),* find a square root of

*a*modulo 7i.

If the factors *p* and *q* of *n* are known, then the SQROOT problem can be solved efficiently by first finding square roots of *a* modulo *p* and modulo *q,* and then combining them using the Chinese remainder theorem (Fact 2.120) to obtain the square roots of *a* modulo n. The steps are summarized in Algorithm 3.44, which, in fact, finds all of the four square roots of *a* modulo *n.*

3.44 Algorithm Finding square roots modulo *n* given its prime factors *p* and *q*

INPUT: an integer n, its prime factors *p* and *q,* and *a* € *Q _{n}.*

OUTPUT: the four square roots of *a* modulo *n.*

- 1. Use Algorithm 3.39 (or Algorithm 3.36 or 3.37, if applicable) to find the two square roots
*r*and*—r*of*a*modulo*p.* - 2. Use Algorithm 3.39 (or Algorithm 3.36 or 3.37, if applicable) to find the two square roots
*s*and —*s*of*a*modulo*q.* - 3. Use the extended Euclidean algorithm (Algorithm 2.107) to find integers
*c*and*d*such that*cp + dq*= 1. - 4. Set
*x<—(rdq*+*sap)*mod*n*and*y<—(rdq — scp)*mod*n.* - 5. Return(±x mod
*n, ±y*mod n).