Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Chinese Remainder theorem
3.
Proving the Chinese Remainder Theorem
4.
Example
5.
Frequently Asked Questions
5.1.
Is the Chinese remainder theorem unique?
5.2.
How is the Chinese remainder theorem used in cryptography?
5.3.
Why is the Chinese remainder theorem useful?
5.4.
What does the Chinese remainder theorem tell us?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is the Chinese Remainder theorem?

Author Muskan Sharma
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hey Readers!!

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!!
 

What is the Chinese Remainder theorem

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: 

χ -1(a1, a2, a3) = (715a1 + 364a2 + 924a3) mod 1001.

For the above example, if x ≡ 5 (mod 7), x ≡ 3 (mod 11), and x ≡ 10 (mod 13), 

So using the Chinese remainder theorem, we can formulate the following:

 x = (715 × 5 + 364 × 3 + 924 × 10) mod 1001 

= 13907 mod 1001

 = 894.

It can be said that by reducing 894 modulo are 7,11, and 13.

Frequently Asked Questions

Is the Chinese remainder theorem unique?

Up to a particular modulus, the Chinese Remainder Theorem asserts that there is always a unique answer and explains how to do so quickly.

How is the Chinese remainder theorem used in cryptography?

The approach offers assistance with random number generation and modular computation.

Why is the Chinese remainder theorem useful?

It enables the replacement of a computation for which a bound on the size of the result is known by several related computations on small integers.

What does the Chinese remainder theorem tell us?

According to the Chinese Remainder Theorem, every pair of congruences with reasonably prime moduli can be uniquely solved.

Conclusion

You understand the Chinese Remainder Theorem, proving it and knowing it in more depth with the help of an example.

Below are the mentioned kike that will help you gain more knowledge in  Cryptography.

What is Square Roots Modulo?The Station-to-station Key Agreement Scheme , Introduction to The RSA Cryptosystem

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. For placement preparations, you must look at the problemsinterview experiences, and interview bundles.

Nevertheless, consider our paid courses to give your career an edge over others!

Thank you

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
What is the Euclidean Algorithm?
Next article
Introduction to The RSA Cryptosystem
Live masterclass