Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

In general, if the prime factorization of *n* is *p _{1}*p_{2}*...*p_{t}*, 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, *p _{1}* might be equal to

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[0]*m[1]*...*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 *a* ≥ *b* 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*

*Quadratic Residues*

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

*x*^{2}≡ 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:

- 1
^{2}= 1 ≡ 1 (mod 7) - 2
^{2}= 4 ≡ 4 (mod 7) - 3
^{2}= 9 ≡ 2 (mod 7) - 4
^{2}= 16 ≡ 2 (mod 7) - 5
^{2}= 25 ≡ 4 (mod 7) - 6
^{2}= 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:

*x*≡ 3 (mod 7)^{2}*x*≡ 5 (mod 7)^{2}*x*≡ 6 (mod 7)^{2}

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).

Previous | Table of Contents | Next |