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 = 2sf, 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^t+1^2 mod p (Algorithm 2.143).
  • 6. For i from 1 to s - 1 do the following:
  • 6.1 Compute d = (r2 • a-1)2 mod p.
  • 6.2 If d = —1 (mod p) then set r<— r ■ c mod p.
  • 6.3 Set c<—c2 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 Qp. OUTPUT: the two square roots of a modulo p.

  • 1. Compute r = rdp+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 Qp. OUTPUT: the two square roots of a modulo p.

  • 1. Compute cl = a.(p-1U4 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 = 2st with s large.

3.39 Algorithm Finding square roots modulo a prime p

INPUT: an odd prune p and a square a e Qp.

OUTPUT: the two square roots of a modulo p.

  • 1. Choose random b e Zp until b2 - 4a is a quadratic non-residue modulo p, i.e.,
  • (6^4a) = _L
  • 2. Let / be the polynomial x2 - bx + a in Zp[x],
  • 3. Compute r = x(p+1^2 mod 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 F4 of odd order q = pm,p prime, 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 a2’" 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 Qn), 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 aQn.

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).
 
Source
< Prev   CONTENTS   Source   Next >