Chinese remainder theorem(CRT) | Information Security | Solving Examples with Steps | Implementation using C++
Basically, we are given k numbers which are pairwise coprime, and given remainders of these numbers when an unknown number x is divided by them. We need to find the minimum possible value of x that produces given remainders.Above given diagram-INPUT:-2 MOD 3
3 MOD 5
2 MOD 7
The Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.
For Solving any CRT problem, we have to assign the variables as shown below-
a1=2 , n1=3
a2= 3 , n2= 5
a3=2 , n3=7
After assigning values to variables, Step 1 is to find the M
M = n1 * n2 * n3
This value of M is very Important which will be required further in the Algorithm.
Step 2 —
Find m1 , m2 , m3
m1 = M/n1
m2 = M/n2
m3 = M/n3
Step 3 — is to find m inverse, Lets say m1’ m2' m3’
m1’ = m1 MOD n1
m2’ = m2 MOD n2
m3’ = m3 MOD n3
After Successful is calculation of M , m , m’ values, Final step is to calculate Y i.e Chineese Remainder
So,
Y = [(m1' * m1 * a1) + (m2' * m2 * a2) + (m3' * m3 * a3) MOD M ]
Final C++ code
#include<stdio.h> // header file
#include<iostream> // header file
using namespace std;
int main()
{
int a[10],n[10],m[10],mi[10],i,size,M=1,Y=0; // variables
cout<<"Enter the size of array :"; // accepting number cin>>size; // of values
// required to MOD
cout<<"Enter the values of a :";
for(i=0;i<size;i++)
{
cin>>a[i]; // accepting a1 ,a2,.....
}
cout<<"Enter the values of n :";
for(i=0;i<size;i++)
{
cin>>n[i]; // accepting n1, n2,......
}
for(i=0;i<size;i++)
{
M=M*n[i]; // calculating M = n1 * n2 * ....
}
cout<<"\nM = "<<M;
for(i=0;i<size;i++)
{
m[i]=M/n[i]; //calculating m1 = M/n1 ,m2=M/n2,.....
cout<<"\nm"<<i<<"= "<<m[i];
}
for(i=0;i<size;i++)
{
mi[i]=m[i]%n[i]; //calculating m1' = m1 MOD n1 ,m2'=m2 MOD n2,.....
cout<<"\nm"<<i<<" inverse = "<<mi[i];
}
for(i=0;i<size;i++)
{
Y=Y+(a[i]*m[i]*mi[i]); //calculating Final Value of Y
}
cout<<"\n\nY = "<<Y;
Y=Y%M;
cout<<"\n\nChinese Remainder(Y MOD M) :-"<<Y; //displaying OUTPUT
}