“read o¬” the bits of logγ ± one at a time.

13.3.2 Prime-power modulus

Let p be an odd prime, let a be an integer relatively prime to p, and let e > 1

be an integer. We know that a is a quadratic residue modulo pe if and only

if a is a quadratic residue modulo p. Suppose that a is a quadratic residue

modulo p, and that we have found an integer z such that z 2 ≡ a (mod p),

using, say, one of the procedures described in §13.3.1. From this, we can

easily compute a square root of a modulo pe using the following technique,

which is known as Hensel lifting.

13.3 Computing modular square roots 295

More generally, suppose we have computed an integer z such that z 2 ≡

a (mod pf ), for some f ≥ 1, and we want to ¬nd an integer z such that

ˆ

z 2 ≡ a (mod pf +1 ). Clearly, if z 2 ≡ a (mod pf +1 ), then z 2 ≡ a (mod pf ),

ˆ ˆ ˆ

and so z ≡ ±z (mod pf ). So let us set z = z + pf u, and solve for u. We

ˆ ˆ

have

z 2 ≡ (z + pf u)2 ≡ z 2 + 2zpf u + p2f u2 ≡ z 2 + 2zpf u (mod pf +1 ).

ˆ

So we want to ¬nd integer u such that

2zpf u ≡ a ’ z 2 (mod pf +1 ).

Since pf | (z 2 ’ a), by Theorem 2.5, the above congruence holds if and only

if

a ’ z2

2zu ≡ (mod p).

pf

From this, we can easily compute the desired value u, since gcd(2z, p) = 1.

By iterating the above procedure, starting with a square root of a modulo

p, we can quickly ¬nd a square root of a modulo pe . We leave a detailed

analysis of the running time of this procedure to the reader.

Exercise 13.10. Suppose you are given a polynomial f ∈ Z[X], along with

a prime p and a root z of f modulo p, that is, an integer z such that

f (z) ≡ 0 (mod p). Further, assume that z is simple root of f modulo p,

meaning that D(f )(z) ≡ 0 (mod p), where D(f ) is the formal derivative of

f . Show that for any integer e ≥ 1, f has a root modulo pe , and give an

e¬cient procedure to ¬nd it. Also, show that the root modulo pe is uniquely

determined, in the following sense: if two such roots are congruent modulo

p, then they are congruent modulo pe .

13.3.3 Composite modulus

To ¬nd square roots modulo n, where n is an odd composite modulus, if we

know the prime factorization of n, then we can use the above procedures

for ¬nding square roots modulo primes and prime powers, and then use the

algorithm of the Chinese remainder theorem to get a square root modulo n.

However, if the factorization of n is not known, then there is no e¬cient

algorithm known for computing square roots modulo n. In fact, one can show

that the problem of ¬nding square roots modulo n is at least as hard as the

problem of factoring n, in the sense that if there is an e¬cient algorithm for

296 Computational problems related to quadratic residues

computing square roots modulo n, then there is an e¬cient (probabilistic)

algorithm for factoring n.

Here is an algorithm to factor n, using a modular square-root algorithm

as a subroutine. For simplicity, we assume that n is of the form n = pq,

where p and q are distinct, odd primes. Choose β to be a random, non-

zero element of Zn . If d := gcd(rep(β), n) > 1, then output d (recall that

rep(β) denotes the canonical representative of β). Otherwise, set ± := β 2 ,

and feed n and ± to the modular square-root algorithm, obtaining a square

root β ∈ Z— of ±. If the square-root algorithm returns β ∈ Z— such that

n n

β = ±β, then output “failure”; otherwise, output gcd(rep(β ’ β ), n), which

is a non-trivial divisor of n.

Let us analyze this algorithm. If d > 1, we split n, so assume that d = 1,

which means that β ∈ Z— . In this case, β is uniformly distributed over

n

— , and ± is uniformly distributed over (Z— )2 . Let us condition on an a

Zn n

¬xed value of ±, and on ¬xed random choices made by the modular square-

root algorithm (in general, this algorithm may be probabilistic). In this

conditional probability distribution, the value β returned by the algorithm

is completely determined. If θ : Zp — Zq ’ Zn is the ring isomorphism of

the Chinese remainder theorem, and β = θ(β1 , β2 ), then in this conditional

probability distribution, β is uniformly distributed over the four square roots

of ±, which we may write as θ(±β1 , ±β2 ).

With probability 1/4, we have β = θ(β1 , β2 ) = β , and with probability

1/4, we have β = θ(’β1 , ’β2 ) = ’β , and so with probability 1/2, we

have β = ±β , in which case we fail to factor n. However, with probability

1/4, we have β = θ(’β1 , β2 ), in which case β ’ β = θ(’2β1 , 0), and since

2β1 = 0, we have p rep(β ’ β ) and q | rep(β ’ β ), and so gcd(rep(β ’

β ), n) = q. Similarly, with probability 1/4, we have β = θ(β1 , ’β2 ), in

which case β ’ β = θ(0, ’2β2 ), and since 2β2 = 0, we have p | rep(β ’ β )

and q rep(β ’ β ), and so gcd(rep(β ’ β ), n) = p. Thus, with probability

1/2, we have β = ±β , and gcd(rep(β ’ β ), n) splits n.

Since we split n with probability 1/2 conditioned on any ¬xed choice ± ∈

(Z— )2 and any ¬xed random choices of the modular square-root algorithm,

n

it follows that we split n with probability 1/2 conditioned simply on the

event that β ∈ Z— . Also, conditioned on the event that β ∈ Z— , we split n

/n

n

with certainty, and so we may conclude that the above algorithm splits n

with probability at least 1/2.

Exercise 13.11. Generalize the algorithm above to e¬ciently factor arbi-

13.4 The quadratic residuosity assumption 297

trary integers, given a subroutine that computes arbitrary modular square

roots.

13.4 The quadratic residuosity assumption

Loosely speaking, the quadratic residuosity (QR) assumption is the as-

sumption that it is hard to distinguish squares from non-squares in Z— , where

n

n is of the form n = pq, and p and q are distinct primes. This assumption

plays an important role in cryptography. Of course, since the Jacobi symbol

is easy to compute, for this assumption to make sense, we have to restrict

our attention to elements of ker(Jn ), where Jn : Z— ’ {±1} is the Jacobi

n

— )2 ⊆ ker(J ) (see Exercise 12.2). Somewhat more

map. We know that (Zn n

precisely, the QR assumption is the assumption that it is hard to distinguish

a random element in ker(Jn ) \ (Z— )2 from a random element in (Z— )2 , given

n n

n (but not its factorization!).

To give a rough idea as to how this assumption may be used in cryptog-

raphy, assume that p ≡ q ≡ 3 (mod 4), so that [’1]n ∈ ker(Jn ) \ (Z— )2 , and

n

— )2 = [’1] (Z— )2 (see Exercise 12.3). The value n can

moreover, ker(Jn ) \ (Zn n n

be used as a public key in a public-key cryptosystem (see §7.8). Alice, know-

ing the public key, can encrypt a single bit b ∈ {0, 1} as β := (’1)b ±2 , where

Alice chooses ± ∈ Z— at random. The point is, if b = 0, then β is uniformly

n

— )2 , and if b = 1, then β is uniformly distributed over

distributed over (Zn

ker(Jn ) \ (Z— )2 . Now Bob, knowing the secret key, which is the factorization

n

of n, can easily determine if β ∈ (Z— )2 or not, and hence deduce the value of

n

the encrypted bit b. However, under the QR assumption, an eavesdropper,

seeing just n and β, cannot e¬ectively ¬gure out what b is.

Of course, the above scheme is much less e¬cient than the RSA cryp-

tosystem presented in §7.8, but nevertheless, has attractive properties; in

particular, its security is very closely tied to the QR assumption, whereas

the security of RSA is a bit less well understood.

Exercise 13.12. Suppose that A is a probabilistic algorithm that takes as

input n of the form n = pq, where p and q are distinct primes such that

p ≡ q ≡ 3 (mod 4). The algorithm also takes as input ± ∈ ker(Jn ), and

outputs either 0 or 1. Furthermore, assume that A runs in strict polynomial