Basic Concepts from Probability, Complexity, Algebra and Number Theory - Introduction to Cryptography with Maple - page 122

we see that this algorithm computes the Legendre symbol more efficiently than
Euler's criterion and hence so do Maple's functions numtheory:-Jacobi and
numtheory:-legendre .

As we will see later, the quadratic residues modulo a product of two odd primes
are of cryptographic interest. The following result characterizes them:

∈ Z n . Then
x is a quadratic residue modulo n if and only if it is both a quadratic residue modulo
p and a quadratic residue modulo q.

Proposition 2.14 Let n = pq be a product of two distinct primes and x

Proof As we have already remarked, if x is a quadratic residue modulo n then it
is also a quadratic residue modulo p and modulo q . Conversely, suppose that x is a
quadratic residue modulo both primes, so that we have congruences x a 2

≡ ( )

mod p

b 2

≡ ( )

and x mod q . Then, the Chinese remainder theoremgives us a unique element

∈ Z n such that y

y ≡ a ( mod p )

(2.6)

y ≡ b ( mod q )

a 2 y 2 b 2 y 2 Thus x ≡ ≡ ( mod p ) and x ≡ ≡ ( mod q ) . Hence both p and q

y 2 and, since they are different primes, so does their product n . Therefore

divide x −

y 2 x ≡ ( mod n ) and x is indeed a quadratic residue modulo n .

Remark 2.11 Note that the preceding proposition can also easily be deduced from
Theorem 2.14. The proof thus obtained is essentially the same as the one above but
it looks even more straightforward.

The following corollary explains something we noticed when computing the
quadratic residues modulo 15: when n is a product of two distinct odd primes, exactly
one-fourth of the elements of

Z n are quadratic residues:

Corollary 2.7 pq is a product of two distinct odd primes then each quadratic

residue modulo n has exactly four square roots in

If n =

Z n .
Proof Let x be a quadratic residue modulo n . Then x is both a quadratic residue
modulo p and a quadratic residue modulo q , and hence it has two square roots
modulo p and two square roots modulo q . Thus we get four different pairs formed
by a square root of x modulo p and a square root of x modulo q . Each of these pairs
defines a system of congruences that, by the Chinese remainder theorem, gives rise
to a square root of x modulo n .

2.9.2 Computing Modular Square Roots

We have seen how to determine whether the equation x 2

, where p
is prime, has a solution, but now we are going to see how to find the solutions, i.e.,

≡ a ( mod p )