Cryptology 2
Spring 2003
Modular Arithmetic and Quadratic Equations

[Home][Up]

How does one determine the solvability and the solutions of an equation such as

a*x² + b*x + c mod R = 0

in N_R?

The problem boils down to the question: Which nonzero residues mod R have square roots mod R? That is, for which a in N_R are there x in N_R such that

x² mod R = a?

The following two definitions apply only to nonzero elements of N_R: If a is a nonzero residue mod R which has a square root mod R, then a is said to be a quadratic residue mod R; otherwise, a is said to be a non-quadratic residue mod R (textbooks often say quadratic non-residue instead of non-quadratic residue).

It is always the case that 1 is a quadratic residue mod R; the main interest is in determining if there are any others.

Examples: 

The following theorems provide us with computational tools to determine if for odd prime number P, a given number in N_P has a square root mod P.

Theorem (Euler) Let P be an odd prime number and let a be a nonzero number in N_P. Then

a^(p-1)/2 mod P =  1, or a^(p-1)/2 mod P = P-1. (Recall that in N_P, -1 is the same thing as P-1.)

 Theorem (Euler's Criterion): Let P be an odd prime number and let a be a nonzero number in N_P. Then the following are equivalent:

1. a is a quadratic residue modulo P.
2. a^(p-1)/2 mod P = 1.

Hence we can also conclude that a is a nonquadratic residue if, and only if, a^(p-1)/2 mod P = P-1.

The quantity a^(p-1)/2 mod P is denoted by a special symbol, called the Legendre symbol, which is

(a/P) := a^(p-1)/2 mod P.

 The Legendre symbol has the following properties which are quite useful in computing whether one number is a quadratic residue modulo another, which is an odd prime:

Theorem: Let P be an odd prime number and let a and b be nonzero elements of N_P. Then:

1. (a*b/P) = (a/P)*(b/P).
2. (1/P)=1.
3. (-1/P) = (-1)^(p-1)/2.

From item 3 in the last theorem one gleans:

Corollary: Let P be an odd prime number. Then

1. (-1/P) = 1 if p mod 4 = 1.
2. (-1/P) = -1 if p mod 4 = 3.

Moreover, there are for a given odd prime number P as many quadratic residues mod P as there are non-quadratic residues mod P:

Theorem: For an odd prime number P, there are (P-1)/2 quadratic residues mod P, and there are (P-1)/2 non-quadratic residues mod P.

The following important theorem is due to Gauss:

Theorem (Gauss): If P is an odd prime number, then (2/P) is equal to (-1) raised to the power (P²-1)/8.

The deepest of the results regarding quadratic residues was first proven rigorously by Gauss, and is known as the Quadratic Reciprocity Law. It states:

Theorem (Quadratic Reciprocity Law): Let P and Q be odd prime numbers. Then

(P/Q)*(Q/P) = (-1)^{[(P-1)/2][(Q-1)/2]} .

How do you compute a square root mod P?

We now have a computational method for determining for an odd prime number P whether a given a in N_P is a quadratic residue mod P, or not. Once it is known that such a square root exists, one can proceed to try and find such a square root. How is this done?

A second, equally important question, is: suppose we know that a is a quadratic residue modulo the prime number P: Can we find a quadratic residue b modulo P such that b² = a mod P? And what about the case when P is a composite number?

In the case when P = 3 mod 4, or where the modulus is a product of two distinct prime numbers, each equal to 3 mod 4, there is a simple algorithm for this:

First, one solves the quadratic equation x² = a mod P for the case when P is an odd prime equal to 3 mod 4 and a is a quadratic residue mod P. The method is given in the following theorem.

Theorem: Let P be a prime number such that P mod 4 = 3. Let a be a quadratic residue mod P. Define k by (P-1)/2 = 2*k + 1. Then

x = a^k+1 mod P

is a solution for x² = a mod P. Moreover, x is a quadratic residue mod P, and is the only such solution to this equation.

Then, using the method for doing this, one solves the equation x² mod R = a where R = P*Q and P and Q are two prime numbers, each equal to 3 mod 4. This is done by first solving each of the equations x² = a mod P and x² mod Q = a, and then using the Chinese remainder theorem to find the final result.

Thus, say we have found p in N_P and q in N_Q such that

 p² mod P = a and

q² mod Q = a.

Then we use the technique of the Chinese Remainder Theorem to compute from p and q an element x of N_R such that

x² mod R = a.