Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

In general, if the prime factorization of n is p1*p2*...*pt, then the system of equations

(x mod pi) = ai, where i = 1, 2,..., t

has a unique solution, x, where x is less than n. (Note that some primes can appear more than once. For example, p1 might be equal to p2 .) In other words, a number (less than the product of some primes) is uniquely identified by its residues mod those primes.

For example, use 3 and 5 as primes, and 14 as the number. 14 mod 3 = 2, and 14 mod 5 = 4. There is only one number less than 3*5 = 15 which has those residues: 14. The two residues uniquely determine the number.

So, for an arbitrary a < p and b < q (where p and q are prime), there exists a unique x, where x is less than pq, such that

x ≡ a (mod p), and x ≡ b (mod q)

To find this x, first use Euclid’s algorithm to find u, such that

u*q ≡ 1 (mod p)

Then compute:

x = (((a - b)*u) mod p)*q + b

Here is the Chinese remainder theorem in C:

```    /* r is the number of elements in arrays m and u;
m is the array of (pairwise relatively prime) moduli
u is the array of coefficients
return value is n such than n == u[k]%m[k] (k=0..r-1) and
n < m*m*...*m[r-1]
*/

/* totient() is left as an exercise to the reader. */
int chinese_remainder (size_t r, int *m, int *u)
{
size_t i;
int modulus;
int n;
modulus = 1;
for (i=0; i<r; ++i)
modulus *= m[i];

n = 0;
for (i=0; i<r; ++i) {
n += u[i] * modexp(modulus / m[i], totient(m[i]),
m[i]);
n %= modulus;
}

return n;
}
```

The converse of the Chinese remainder theorem can also be used to find the solution to the problem: if p and q are primes, and p is less than q, then there exists a unique x less than pq, such that

a ≡ x (mod p), and b ≡ x (mod q)

If ab mod p, then

x = (((a - (b mod p))*u) mod p)*q + b

If a < b mod p, then

x = (((a + p - (b mod p))*u) mod p)*q + b

If p is prime, and a is greater than 0 and less than p, then a is a quadratic residue mod p if

x2 ≡ a (mod p), for some x

Not all values of a satisfy this property. For a to be a quadratic residue modulo n, it must be a quadratic residue modulo all the prime factors of n. For example, if p = 7, the quadratic residues are 1, 2, and 4:

12 = 1 ≡ 1 (mod 7)
22 = 4 ≡ 4 (mod 7)
32 = 9 ≡ 2 (mod 7)
42 = 16 ≡ 2 (mod 7)
52 = 25 ≡ 4 (mod 7)
62 = 36 ≡ 1 (mod 7)

Note that each quadratic residue appears twice on this list.

There are no values of x which satisfy any of these equations:

x2 ≡ 3 (mod 7)
x2 ≡ 5 (mod 7)
x2 ≡ 6 (mod 7)

The quadratic nonresidues modulo 7, the numbers that are not quadratic residues, are 3, 5, and 6.

Although I will not do so here, it is easy to prove that, when p is odd, there are exactly (p- 1)/2 quadratic residues mod p and the same number of quadratic nonresidues mod p. Also, if a is a quadratic residue mod p, then a has exactly two square roots, one of them between 0 and (p- 1)/2, and the other between (p- 1)/2 and (p- 1). One of these square roots is also a quadratic residue mod p; this is called the principal square root.

If n is the product of two primes, p and q, there are exactly (p- 1)(q- 1)/4 quadratic residues mod n. A quadratic residue mod n is a perfect square modulo n. This is because to be a square mod n, the residue must be a square mod p and a square mod q. For example, there are 11 quadratic residues mod 35: 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, and 30. Each quadratic residue has exactly four square roots.

Legendre Symbol

The Legendre symbol, written L(a,p), is defined when a is any integer and p is a prime greater than 2. It is equal to 0, 1, or -1.

L(a,p) = 0 if a is divisible by p.
L(a,p) = 1 if a is a quadratic residue mod p.
L(a,p) = - 1 is a is a quadratic nonresidue mod p.

One way to calculate L(a,p) is:

L(a,p) = a(p- 1)/2 mod p

Or you can use the following algorithm:

1.  If a = 1, then L(a,p) = 1
2.  If a is even, then L(a,p) = L(a /2,p)*(- 1)(p2- 1)/8
3.  If a is odd (and ≠ 1), then L(a,p) = L(p mod a,a)*(- 1)(a- 1)*(p- 1)/4

Note that this is also an efficient way to determine whether a is a quadratic residue mod p (when p is prime).

[an error occurred while processing this directive]