10 Chinese Remainder Theorem

Dr Kulothungan

Learning Objectives

Ø  To introduce prime numbers and their applications in cryptography.

Ø   To discuss about Euler’s and Fermat’s Theorem.

Ø   To discuss various examples Euler’s and Fermat’s Theorem.

Ø   To describe the Chinese remainder theorem and its application.

10.1. Chinese Remainder Theorem

This theorem has this name because it is a theorem about remainders and was first discovered in the 3rd century AD by the Chinese mathematician Sunzi in Sunzi Suanjing.

The Chinese remainder theorem is a theorem of number theory, which states that, if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.

10.2. Theorem Statement

Let n1, …, nk be integers greater than 1, which are often called moduli or divisors. Let us denote by N the product of the ni.

The Chinese remainder theorem asserts that if the ni are pairwise coprime, and if a1, …, ak are integers such that 0 ≤ ai < nifor every i, then there is one and only one integer x, such that 0 ≤  x < N and the remainder of the Euclidean division of x by niis ai for every i.

This may be restated as follows in term of congruences: If the ni are pairwise coprime, and if a1, …, ak are any integers, then there exists an integer x such that

and any two such x are congruent modulo N.

In abstract algebra, the theorem is often restated as: if the ni are pairwise coprime, the map

defines a ring isomorphism[12]

between the ring of integers modulo N and the direct product of the rings of integers modulo the ni. This means that for doing a sequence of arithmetic operations in z/nz one may do the same computation independently in each  z/n_iz and then get the result by applying the isomorphism (from the right to the left). This may be much faster than the direct computation if Nand the number of operations are large. This is widely used, under the name multi-modular computation, for linear algebraover the integers or the rational numbers.

The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family.

10.3. CRT – Problem

An old woman goes to market and a horse steps on her basket and crushes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

This problem can be expressed as a system of congruences

x≡2(mod3)

x≡3(mod5)

x≡2(mod7)

What does (mod n) mean?

x ≡ a1 ( mod m1 )

The Chinese remainder theorem states the above equations have a unique solution if the moduli are relatively prime.

   Example:

The following is an example of a set of equations with different moduli:

X≡ 2 (mod 3)

X≡ 3 (mod 5)

X≡ 2 (mod 7)

The solution to this set of equations is given in the next section; for the moment, note that the answer to this set of equations is x = 23. This value satisfies all equations: 23 ≡ 2 (mod 3), 23 ≡ 3 (mod 5), and 23 ≡ 2 (mod 7).

Solution To Chinese Remainder Theorem

1.  Find M = m1 × m2 × … × mk. This is the common modulus.

2.  Find M1 = M/m1, M2 = M/m2, …, Mk = M/mk.

3.  Find the multiplicative inverse of M1, M2, …, Mk using the corresponding moduli (m1, m2, …, mk). Call the inverses M1⁻¹, M2⁻¹, …, Mk ⁻¹.

4.  The solution to the simultaneous equations is

Note that the set of equations can have a solution even if the moduli are not relatively prime but meet other condition. However , in cryptography only interested in solving equations with coprime moduli.

Example

Find the solution to the simultaneous equations:

solution

We follow the four steps.

X≡ 2 (mod 3)

X≡ 3 (mod 5)

X≡ 2 (mod 7)

1. M = 3 × 5 × 7 = 105

2. M1 = 105 / 3 = 35, M2 = 105 / 5 = 21, M3 = 105 / 7 = 15

3. The inverses are M1−1 = 2, M2−1 = 1, M3 −1 = 1

4. x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = 23 mod 105

Solution for Egg Problem

To solve for x, let M=3⋅5⋅7=105

M1=35

M2=21

M3=15

Here we see that 2 is an inverse of M1=35 modulo 3 because 35⋅2≡2⋅2≡1(mod3);

1 is an inverse of M2=21 modulo 5, because 21≡1(mod5);

and 1 is an inverse of M3=15(mod7), because 15≡1(mod7)

The solution to this system are those x such that

x =2⋅35⋅2+3⋅21⋅1+2⋅15⋅1

=233≡23(mod105)

The answer is 23 eggs.

10.4. The Proof

Let s and t be positive integers with gcd(s, t) = 1 S and t are therefore coprime Prove that there exists an integer w such that sw == 1 (mod t)

For each k, let Mi = m/mk where m = m1m2m3…mk (product of mods) Prove that the greatest common denominator of Mi & mi = 1 Or, that Mi and mi are coprime

Prove that there is an integer xi such that mi xi == 1(mod mi) and ai mi xi == ai (mod mi ) Let x == a₁m₁x₁ + a₂m₂x₂ + … + a_nm_nx_n Prove that x == ai (mod mi)

10.5. Application

In coding theory, detection and correction of errors is done by adding redundancy to data that is sent via a noisy channel or in a computer.

The CRT remainder techniques are useful in developing code that detects errors.

In cryptography, the CRT is used in secret sharing through error-correcting code.

The CRT is itself a secret-sharing scheme without any need for modification

Summary

Ø Outlined the CRT and their applications in cryptography

Ø Discussed about the Chinese Remainder Theorem and algorithms

Ø Worked with various examples related with Chinese Remainder Theorem