Dadas N ecuaciones modulares: A ≅ x 1 mod(m 1 ) . . A ≅ x n mod(m n ) Encuentra x en la ecuación A ≅ xmod(m 1 *m 2 *m 3 ..*m n ) donde m i es primo, o potencia de un primo, e i toma valores de 1 a n. La entrada se da como dos arrays, la primera es una array que contiene valores de cada x i y la segunda array contiene el conjunto de valores de cada número primo. m i Muestra un número entero para el valor de x en la ecuación final. Ejemplos:
Consider the two equations A ≅ 2mod(3) A ≅ 3mod(5) Input : 2 3 3 5 Output : 8 Consider the four equations, A ≅ 3mod(4) A ≅ 4mod(7) A ≅ 1mod(9) (32) A ≅ 0mod(11) Input : 3 4 1 0 4 7 9 11 Output : 1243
Explicación: nuestro objetivo es resolver estas ecuaciones de dos en dos. Tomamos las dos primeras ecuaciones, las combinamos y usamos ese resultado para combinarlas con la tercera ecuación, y así sucesivamente. El proceso de combinar dos ecuaciones se explica a continuación, tomando el ejemplo 2 como referencia:
- A ≅ 3mod(4) y A ≅ 4mod(7) son las dos ecuaciones que nos proporcionan en un principio. Sea la ecuación resultante un A 0 ≅ x 0 mod(m 1 * m 2 ).
- Un 0 viene dado por m 1 ‘ * m 1 * x 0 + m 0 ‘ * m 0 * x 1 donde m 1 ‘ = inversa modular de m 1 módulo m 0 y m 0 ‘ = inversa modular de m 0 módulo m 1
- Podemos calcular el inverso modular usando el algoritmo euclidiano extendido.
- Encontramos que x 0 es A 0 mod (m 1 * m 2 )
- Conseguimos que nuestra nueva ecuación sea A ≅ 11mod(28), donde A es 95
- Ahora tratamos de combinar esto con la ecuación 3 y, mediante un método similar, obtenemos A ≅ 235mod(252), donde A = 2503
- Y finalmente, al combinar esto con la ecuación 4, obtenemos A ≅ 1243mod(2772) donde A = 59455 y x = 1243
Observamos que 2772 es exactamente igual a 4 * 7 * 9 * 11. Así hemos encontrado el valor de x para la ecuación final. Puede consultar Algoritmo euclidiano extendido e Inverso multiplicativo modular para obtener información adicional sobre estos temas.
C++
// C++ program to combine modular equations
// using Chinese Remainder Theorem
#include<bits/stdc++.h>
using namespace std;
// function that implements Extended euclidean
// algorithm
vector<int> extended_euclidean(int a,int b){
if(a == 0){
vector<int> temp;
temp.push_back(b);
temp.push_back(0);
temp.push_back(1);
return temp;
}
else{
vector<int> temp(3);
temp= extended_euclidean(b % a, a);
int g = temp[0];
int y = temp[1];
int x = temp[2];
temp[0] = g;
temp[1] = x - ((b/a) * y);
temp[2] = y;
return temp;
}
vector<int> temp;
return temp;
}
// modular inverse driver function
int modinv(int a,int m){
vector<int> temp(3);
temp = extended_euclidean(a, m);
int g = temp[0];
int x = temp[1];
int y = temp[2];
// Since we are taking the modulo of
// negative numbers so, to have positive
// output of the modulo we use this formula.
int ans = x - (floor(x/(float)m) * m);
return ans;
}
// function implementing Chinese remainder theorem
// list m contains all the modulii
// list x contains the remainders of the equations
int crt(vector<int> &m,vector<int> & x)
{
// We run this loop while the list of
// remainders has length greater than 1
while(1)
{
// temp1 will contain the new value
// of A. which is calculated according
// to the equation m1' * m1 * x0 + m0'
// * m0 * x1
int var1 = (modinv(m[1],m[0]));
int var2 = (modinv(m[0],m[1]) );
// cout << var1 << " " << var2 << endl;
int temp1 = (modinv(m[1],m[0])) * x[0] * m[1] + (modinv(m[0],m[1]) )* x[1] * m[0];
// temp2 contains the value of the modulus
// in the new equation, which will be the
// product of the modulii of the two
// equations that we are combining
int temp2 = m[0] * m[1];
// cout << temp1<< " "<<temp2<< endl;
// we then remove the first two elements
// from the list of remainders, and replace
// it with the remainder value, which will
// be temp1 % temp2
x.erase(x.begin());
x.erase(x.begin());
x.insert(x.begin(), temp1%temp2);
//we then remove the first two values from
//the list of modulii as we no longer require
// them and simply replace them with the new
// modulii that we calculated
m.erase(m.begin());
m.erase(m.begin());
m.insert(m.begin(), temp2);
// once the list has only one element left,
// we can break as it will only contain
// the value of our final remainder
if(x.size()== 1){
break;
}
}
// returns the remainder of the final equation
return x[0];
}
// driver segment
int main(){
vector<int> m = {4, 7, 9, 11};
vector<int> x = {3, 4, 1, 0};
cout << crt(m, x) << endl;
return 0;
}
// The code is contributed by Gautam goel (gautamgoe962)
Python
# Python 2.x program to combine modular equations # using Chinese Remainder Theorem # function that implements Extended euclidean # algorithm def extended_euclidean(a, b): if a == 0: return (b, 0, 1) else: g, y, x = extended_euclidean(b % a, a) return (g, x - (b // a) * y, y) # modular inverse driver function def modinv(a, m): g, x, y = extended_euclidean(a, m) return x % m # function implementing Chinese remainder theorem # list m contains all the modulii # list x contains the remainders of the equations def crt(m, x): # We run this loop while the list of # remainders has length greater than 1 while True: # temp1 will contain the new value # of A. which is calculated according # to the equation m1' * m1 * x0 + m0' # * m0 * x1 temp1 = modinv(m[1],m[0]) * x[0] * m[1] + \ modinv(m[0],m[1]) * x[1] * m[0] # temp2 contains the value of the modulus # in the new equation, which will be the # product of the modulii of the two # equations that we are combining temp2 = m[0] * m[1] # we then remove the first two elements # from the list of remainders, and replace # it with the remainder value, which will # be temp1 % temp2 x.remove(x[0]) x.remove(x[0]) x = [temp1 % temp2] + x # we then remove the first two values from # the list of modulii as we no longer require # them and simply replace them with the new # modulii that we calculated m.remove(m[0]) m.remove(m[0]) m = [temp2] + m # once the list has only one element left, # we can break as it will only contain # the value of our final remainder if len(x) == 1: break # returns the remainder of the final equation return x[0] # driver segment m = [4, 7, 9, 11] x = [3, 4, 1, 0] print crt(m, x)
Javascript
// JavaScript program to combine modular equations
// using Chinese Remainder Theorem
// function that implements Extended euclidean
// algorithm
function extended_euclidean(a, b){
if(a == 0){
let temp = [b, 0, 1];
return temp;
}
else{
let temp= extended_euclidean(b % a, a);
let g = temp[0];
let y = temp[1];
let x = temp[2];
temp[0] = g;
temp[1] = x - (Math.floor(b/a) * y);
temp[2] = y;
return temp;
}
let temp;
return temp;
}
// modular inverse driver function
function modinv(a, m){
let temp = extended_euclidean(a, m);
let g = temp[0];
let x = temp[1];
let y = temp[2];
// Since we are taking the modulo of
// negative numbers so, to have positive
// output of the modulo we use this formula.
let ans = x - (Math.floor(x/m) * m);
return ans;
}
// function implementing Chinese remainder theorem
// list m contains all the modulii
// list x contains the remainders of the equations
function crt(m, x)
{
// We run this loop while the list of
// remainders has length greater than 1
while(1)
{
// temp1 will contain the new value
// of A. which is calculated according
// to the equation m1' * m1 * x0 + m0'
// * m0 * x1
let var1 = (modinv(m[1],m[0]));
let var2 = (modinv(m[0],m[1]) );
// cout << var1 << " " << var2 << endl;
let temp1 = (modinv(m[1],m[0])) * x[0] * m[1] + (modinv(m[0],m[1]) )* x[1] * m[0];
// temp2 contains the value of the modulus
// in the new equation, which will be the
// product of the modulii of the two
// equations that we are combining
let temp2 = m[0] * m[1];
// cout << temp1<< " "<<temp2<< endl;
// we then remove the first two elements
// from the list of remainders, and replace
// it with the remainder value, which will
// be temp1 % temp2
x.shift();
x.shift();
x.unshift(temp1 % temp2);
//we then remove the first two values from
//the list of modulii as we no longer require
// them and simply replace them with the new
// modulii that we calculated
m.shift();
m.shift();
m.unshift(temp2);
// once the list has only one element left,
// we can break as it will only contain
// the value of our final remainder
if(x.length== 1){
break;
}
}
// returns the remainder of the final equation
return x[0];
}
// driver segment
let m = [4, 7, 9, 11];
let x = [3, 4, 1, 0];
console.log(crt(m, x));
// The code is contributed by phasing17
Output 1243
Complejidad de tiempo: O(l), donde l es el tamaño de la lista restante.
Complejidad espacial: O (1), ya que no estamos utilizando ningún espacio adicional.
Este teorema y algoritmo tiene excelentes aplicaciones. Una aplicación muy útil es calcular n C r % m donde m no es un número primo y el teorema de Lucas no se puede aplicar directamente. En tal caso, podemos calcular los factores primos de m, y usar los factores primos uno por uno como módulo en nuestra ecuación n C r % m que podemos calcular usando el Teorema de Lucas, y luego combinar las ecuaciones resultantes usando el arriba se muestra el Teorema del Resto Chino. Este artículo es una contribución de Deepak Srivatsav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA