Welcome back to another article on topics related to Cryptography.

What is Cryptography?

Cryptography is the technique for securing communication between the sender and the receiver.

In this article you’ll learn about the Chinese Remainder theorem in Cryptography.

Let’s begin!!

Chinese Remainder theorem

The Chinese remainder theorem is a technique for resolving specific congruence systems. Assume that m1,..., and mr are pairs of reasonably prime positive integers (gcd(mi, mj) = 1 if i j). Assume that a1,..., and ar are integers, and think about the following system of congruences:

x ≡ a1 (mod m1)

x ≡ a2 (mod m2)

.

.

.

x ≡ ar (mod mr).

According to the Chinese Remainder Theorem, this system has a singular solution modulo M = m1 × m2 × · · · × mr.In this part, we will demonstrate this finding and outline an effective strategy for resolving similar systems of congruences.

Studying the "projection function" is practical. χ : ZM → Zm1 × · · · × Zmr , which we define as follows:

χ(x) = (x mod m1, . . . , x mod m2).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Proving the Chinese Remainder Theorem

The function must be shown as a bijection to demonstrate the Chinese remainder theorem.

Bijection - Bijections are also referred to as invertible functions, one-to-one correspondences.

For the inverse function, we can provide an explicit generic formula χ -1.

For 1 ≤ i ≤ r, define

Mi=Mmi

We can say that

gcd(Mi , mi) = 1

Next, for 1 ≤ i ≤ r, define

yi = Mi-1 mod mi .

This inverse exists because gcd(Mi, mi) = 1. Also, note that

Miyi ≡ 1 (mod mi)

Now, defining the function ρ: Zm1 × · · · × Zmr → ZM as follows:

ρ(a1, . . . , ar) = i=1raiMiyi mod M.

We'll demonstrate how the function ρ = χ -1, i.e, it offers a clear formula for resolving the initial congruence system.

X = ρ(a1, . . . , ar), and let 1 ≤ j ≤ r. The term aiMiyi in the above summation, reduced modulo mj : If i = j, then

aiMiyi ≡ ai (mod mi)

As

Miyi ≡ 1 (mod mi).

If ij, then,

aiMiyi ≡ 0 (mod mj)

because mj | Mi in this case. Thus,

Xi=1raiMiyi (mod mj)

aj (mod mj).

Since this is true for all j, 1 ≤ j ≤ r, X is a remedy for the congruence system. We now need to demonstrate that the answer X is unique modulo M. However, counting can accomplish this. The function χ comes from a range of cardinality M to cardinality M. We have just established that χ is an ontological (or surjective) function. Since the domain and range have the same cardinality, they must likewise be injective (i.e., one-to-one).

Example

Imagine that r = 3, m1 = 7, m2 = 11, and m3 = 13. Then M = 1001M1 = 143, M2= 91, and M3= 77, are calculated then y1 = 5,y2 = 4, and y3 = 12.

Then the function χ -1 : Z7 × Z11 × Z13 → Z1011 is the following: