Quadratic Congruences - Introduction to Cryptography with Java Applets - page 171

Now let z be the least nonnegative residue of y modulo p , and let w be the least nonneg-

2

ative residue of y modulo q . So x = z are solutions to x a (mod p ), and x = w are solu-

2

tions to ). We can combine these solutions in four different ways to get four

sets of simultaneous congruences:
1. x z (mod p ) and x w (mod q )
2. x p z (mod p ) and x q w (mod q )
3. x p z (mod p ) and x w (mod q )
4. x z (mod p ) and x q w (mod q ).
Using the Chinese Remainder Theorem (CRT) on each of sets 1 through 4, we can find
the value for

x a (mod q

which solves the two congruences simultaneously, and these four values are
thus solutions to (*). For congruences 1 and 2, we use CRT to construct the two solutions
x ( zqq p + wpp q ) (mod n )

x

where q p is an inverse of q modulo p , and p q is an inverse of p modulo q . Similarly, using

CRT on congruences 2 and 3 we arrive at the other pair of solutions
x ( zqq p wpp q ) (mod n ).
We then can write the four solutions quickly as
x ( zqq p wpp q ) (mod n ).

and the proof is complete.

E XAMPLE .

Suppose we wish to solve

2

23 (mod 77).
Note that the prime factorization of 77 is 7 11, and both of these primes are congruent
to 3 modulo 4. We first obtain the solutions to

x

2

a. x

23 2 (mod 7), and

2

b. x

23 1 (mod 11).
The solutions to (a) are x 3 (mod 7), and the solutions to (b) are x 1 (mod 11).
Using the Chinese Remainder Theorem, we then separately solve the four sets of congru-
ences

1. x 3 (mod 7) and x 1 mod 11)
2. x 3 (mod 7) and x 1 mod 11)
3. x 3 (mod 7) and x 1 mod 11)
4. x 3 (mod 7) and x 1 mod 11).
Each yields a solution to x

2

23 (mod 77). We can do all of these at once, as denoted in

the formula of proposition 31:

x = (3 11 2 1 7 8) (mod 77)