Chinese Remainder Theorem

The CRT is a method for solving certain systems of congruencies. The CRT reconstructs integers from their residue values modulo a set of relatively prime moduli. The CRT is a mechanism for manipulating very large numbers in terms of tuples of smaller integers. The CRT can be calculated in 5 steps. Given a set of congruencies such as:

x ≡ a₁ mod m₁
x ≡ a₂ mod m₂
x ≡ a₃ mod m₃
...
x ≡ a_i mod m_i

1. Calculate M = m₁ * m₂ * m₃ *, ..., m_i

2. Calculate M₁ = M/m₁, M₂ = M/m₂ and M₃ = M/m₃, ..., M_i = M/m_i

3. Calculate your a's (if necessary)

4. Find the multiplicative inverse for each M₁, M₂, M₃, ..., M_i, mod m₁, m₂, m₃, ..., m_i respectively

5. Σ(A_i * M_i * M_i^-1) mod M = Result

Example

Let's say that you want to find the answer to 3203 mod 5005.

(Step 1) We know that M = 5005 can be broken down into its prime factors:

        m1 = 5, m2 = 7, m3 = 11, m4 = 13

(Step 2) In getting the M's we have:

        M1 = 1001 = 5005/5

        M2 = 715 = 5005/7

        M3 = 455 = 5005/11

        M4 = 385 = 5005/13

(Step 3) While using Fermat's theorem we can get the following:

        a1 = 3302 mod 5 ≡ 4 mod 5

        a2 = 3302 mod 7 ≡ 2 mod 7

        a3 = 3302 mod 11 ≡ 9 mod 11

        a4 = 3302 mod 13 ≡ 9 mod 13

(Step 4) Now we have to solve for multiplicative inverses using Euclid's Extended Algorithm for each one:

        1001 * M1-1 ≡ 1 mod 5 → 1 * M1-1 ≡ 1 mod 5 → M1-1 = 1

        715 * M2-1 ≡ 1 mod 7  → 1 * M2-1 ≡ 1 mod 7   → M2-1 = 1

        455 * M3-1 ≡ 1 mod 11 → 4 * M3-1 ≡ 1 mod 11  → M3-1 = 3

        385 * M4-1 ≡ 1 mod 13 → 8 * M4-1 ≡ 1 mod 13  → M4-1 = 5

(Step 5) Finally summing everything taken modulo 5005 we have:

        [(4 * 1001 * 1) + (2 * 715 * 1) + (9 * 435 * 3) + (9 * 385 * 5)] mod 5005 

        = 35044 mod 5005 

        = 9

Thus, 3³⁰² mod 5005 = 9. Notice also that 9 is the answer to each of the congruent equations in step 3.

Links

http://www.swox.com/gmp/
http://www.cacr.math.uwaterloo.ca/hac/
http://www.claymath.org/prizeproblems/p_vs_np.pdf
http://www.utm.edu/research/primes/ftp/all.txt
http://documents.wolfram.com/v4/AddOns/NumT_NumberTheoryFunctions-.html
http://www.utm.edu/research/primes/prove/
http://directory.google.com/Top/Science/Math/Applications/Communication_Theory/Cryptographyhttp://directory.google.com/Top/Science/Math/Number_Theory/Computational/
http://sigact.acm.org/