Saulo Silva's Blog

In public-key Cryptography, especially with the RSA algorithm, the Chinese Remainder Theorem is often used. Say you have a system of simultaneous congruences as follows

x a₁ mod m₁
x a₃ mod m₂

x a_k mod m_k ,

where m₁, m₂, …, m_k are coprime, i.e. gcd(m₁, m₂, …, m_k) = 1. How can we solve for x? The solution is quite straight forward, but could involve a fair amount of calculations. I find that breaking down the method into smaller steps makes it easier to find and fix mistakes. By the Chinese Remainder Theorem, the solution to that system of equations is

x = (a₁M₁y₁ + a₂M₂y₂ + … + a_kM_ky_k) mod M ,

where M_i is the product of all m’s except for m_i

,

y_i is the multiplicative inverse of M_i modulo m_i

y_i M_i^-1 mod m_i ,

and M = m₁ * m₂ * … * m_k .

Let us try a numeric example. Here is a system of simultaneous congruences:

x 12 mod 25
x 9 mod 26
x 23 mod 27

We start by calculating M₁ and y₁:

M₁ = m₂ * m₃ = 26 * 27 = 702

y₁ = M₁^-1 mod m₁ = 702^-1 mod 25 .

We apply the Extended Euclidean Algorithm to find the multiplicative inverse of 702 relative to 25:

702 = 28 * 25 + 2 → 2 = 702 – 28 * 25
25   = 12 * 2 + 1 → 1 = 25 – 12 * 2
= 25 – 12 * (702 – 28 * 25)
= 337 * 25 – 12 * 702

Then y₁ = 702^-1 mod 25 -12 13.

The same calculations can be carried on to find M₂ = 675, y₂ = 25, M₃ = 650 and y₃ = 14. Now it is just a matter of plugging in the values into the equation:

x = (a₁M₁y₁ + a₂M₂y₂ + a₃M₃y₃) mod M
= (12*702*13 + 9*675*25 + 23*650*14) mod 17550 470687 14387

To verify our answer we can plug that number back into the system:

470687 mod 25 12
470687 mod 26 9
470687 mod 27 23