Chinese Reminder Theorem
The Chinese Remainder Theorem (CRT) is a mathematical theorem that provides a way to solve a system of linear congruences.
Specifically, it states that given a set of integers that are pairwise coprime and a set of remainders modulo those integers, there exists a unique solution, modulo the product of the integers, to the system of congruences.
The theorem has applications in number theory, cryptography, and computer science.
m = m1·m2·...·mk, with
(mi,mj) = 1 for all
i ≠ j.
And a system of
x ≡ a1 (mod m1) ... x ≡ ak (mod mk)
The system has a unique solution
x ∈ Zm.
Existence Proof (by construction)
ci = m/mi · [(m/mi)^-1 mod mi], for i in 1..k
mi | m and
(m/mi,mi) = 1 →
m/mi has multiplicative inverse modulo
x = ∑ ai·ci, for i in 1...k
i = j then
ci mod mj = 1 else
ci mod mj = 0. Follows that:
x mod m1 = a1·1 + a2·0 + ... + ak·0 = a1 x mod m2 = a1·0 + a2·1 + ... + ak·0 = a2 ... x mod mk = a1·0 + a2·0 + ... + ak·1 = ak
Assume there are two solutions
∀ i in 1..k:
x1 mod mi = ai → x = mi·w + ai x2 mod mi = ai → x' = mi·k + ai → x1 - x2 = mi·(w - k) → mi|(x1 - x2)
(mi,mj) = 1 and both
mi|(x1 - x2) and
mj|(x1 - x2) then
(mi·mj)|(x1 - x2).
(m = m1·m2⋅...·mk)|(x1 - x2) and thus that
x1 ≡ x2 (mod m)
Note: is important when computing the solution
x to don’t reduce
mi, just the inverse.
Given that there is a unique solution, the transformation to vectored form is a bijection, and thus we are allowed to perform computations in the vectored form and then go back to the normalized form.
a ∈ Zm is first uniquely mapped into the smaller components:
a ↔ (a1, ... , ak) = (a mod m1, ... , a mod mk)
Then we can operate over the smaller components.
For example, if we want to multiply two values
a ↔ (a1, ..., ak) = (a mod m1, ..., a mod mk) b ↔ (b1, ..., bk) = (b mod m1, ..., b mod mk)
We operate on the single components, and finally we map back to obtain
a+b ↔ (a1+b1, ..., ak+bk) = (a+b mod m1, ..., a+b mod mk) a·b ↔ (a1·b1, ..., ak·bk) = (a·b mod m1, ..., a·b mod mk)
Note that the result holds because:
(a mod mi · b mod mi) mod mi = (a·b mod m) mod mi
And the uniqueness of the solution.
Doesn’t matter if we first reduce the result modulo
m and then modulo
mi, give that:
z = mq + r = m1·..·mk·q + r → (z mod m) mod mi = r mod mi and also → z mod mi = r mod mi
In the end, via CRT we found the unique solution
x = a+b ∈ Zn such that:
x mod mi = (a mod mi + b mod mi) mod mi
m1 = 9, m2 = 10, m = 90
To vectored form:
a = 73 → (73 mod 9, 73 mod 10) = (1, 3) b = 84 → (84 mod 9, 84 mod 10) = (3, 4) a·b = x → (1⋅3 mod 9, 3⋅4 mod 10) = (3, 2)
Resolve the system:
x = 3 (mod 9) x = 2 (mod 10)
Using the existence proof formula:
x = 3 · 90/9 · [(90/9)^-1 mod 9] + 2 · 90/10 · [(90/10)^-1 mod 10] = 3·10·1 + 2·9·9 = 192 = 12 (mod 90)
We found that
a·b = 12 (mod 90)
RSA CRT Speed-up
The technique is applicable to RSA when we know the modulus prime factors
q, thus it is generally applicable to the decryption and signing
If we have a number
a ∈ Zn then we map it to
(a mod p, a mod q).
We end up working with numbers having approximately half the digits of the original number.
Instead of performing one single exponentiation modulo
n, we perform two
q. For example, for digital signature if
the secret exponent:
Sp = m^d mod p Sq = m^d mod q
We then write the following system of two equations:
S ≡ Sp (mod p) S ≡ Sq (mod q)
According to CRT the solution
S to the system is unique and turns out to be
the value we want to compute (i.e.
m^d mod n).
The cost of multiplying two numbers with
k bits is
Because the exponent has
k bits, the cost to perform
m^d is approximately
the cost of performing
k iterations where each iteration has the cost of
(let’s assume that we do a multiplication on each iteration). Thus, the total
With CRT we execute two modular exponentiation
m^d mod p and
m^d moq q.
q have approximately
k/2 bits the cost of each
≈ (k/2)^2. The iterations for performing one exponentiation
will thus cost
≈ (k/2)^3 = (k^3)/8. We are performing two exponentiation thus
the total cost is
Using the CRT speedup can thus result in a significant reduction in the cost of
performing modular exponentiation. Specifically, the cost is approximately
of the traditional method, resulting in a speed-up of around 75%.
Euler’s Totient Proof
Given two numbers
m2 such that
(m1,m2) = 1 and
m = m1·m2, we want
to prove that
φ(m) = φ(m1)·φ(m2).
This is equivalent proving that there exist a bijection from
Zm1* × Zm2*.
f: Zm* → Zm1* × Zm2*
We define such function as:
f(x) = (x mod m1, x mod m2)
Starting from a number
x ∈ Zm* then
x mod mi is clearly in
But we require that
x ∈ Zmi*.
x ∈ Zn*, by hypothesis we know that
(x,m) = (x, m1·m2) = 1 and thus
x doesn’t have any common factor with both
For Euclidean algorithm
1 = (x,mi) = (mi, x mod mi) and thus
x mod mi ∈ Zmi*.
x2 be two elements of
f(x1) = f(x2) = (a1, a2) then
x2 are both solutions for the system:
x ≡ a1 (mod m1) x ≡ a2 (mod m2)
For the CRT the solution
x ∈ Zm* is unique, thus
x1 = x2.
ai ∈ Zmi* for CRT there exist a unique solution
x ∈ Zm.
(mi, ai = x mod mi) = 1 then for Euclidean algorithm
(x, mi) = 1.
x doesn’t have any common factor with any
mi and thus doesn’t have any
common factor with
m = m1⋅m2. Follows that
x ∈ Zm*.
Iterating the procedure this also proves that
φ(∏ mi) = ∏ φ(mi) when the
are pairwise coprime.