[Taller] Chinese Remainder Theorem

Chinese Remainder Theorem

Buenas.

Hoy os traigo uno de los pilares matemáticos más impresionantes descubierto múltiples veces en la historia. Se le atribuye al gran Sun Tzu, es por eso que lo suelen nombrar Chinese Remainder Theorem (Teorema del resto chino), aunque otras culturas lo reinventaran con otro enunciado diferente ( para los amantes de la historia revisad: http://www.math.harvard.edu/~knill/crt/lib/Kangsheng.pdf )

¿De que trata este teorema? El siguiente planteamiento del mismo no difiere del planteamiento ancestral descrito por aquellas intrigantes culturas:

¿Cómo podemos hallar el número X que al dividir por 3 nos deja resto 2, al dividir por 5 nos deja resto 3 y al dividir por 7 nos deja resto 2? Simple, ¿verdad?. Es como si hubiera repartido una serie de objetos entre varias personas y hubiera olvidado la cantidad de objetos y solo me acuerdo de a cuantas personas he repartido y el resto de dichas operaciones.

El gran Grauss formalizó los teoremas de Euler, Lagrange, Fermat y Legendre entre tantos, formalizando de esta forma la aritmética modular en su obra maestra Disquisitiones Arithmeticae (si teneís una biblioteca en la uni corred a leerlo), y cómo no, no pudo dejar pasar la ocasión de plantear este mismo teorema, en su caso con calendarios y ciclos lunares.

Explicado el planteamiento, empecemos a adentrarnos en las profundidades matemáticas (ojalá algún día pongan LateX en este foro ... )

ATENCIÓN: Tanto la explicación algebraíca general como el ejemplo posterior son fruto de mi conocimiento y práctica, pudiendo haber mínimas diferencias con el proceso estándar/general.

Primero definamos lo que es una relación de congruencia:

$3\equiv 7\pmod 4$ lo expresamos como "3 es congruente a 7 módulo 4" porque "(4*1)+3=7" y porque "4 divide a 7-3".
$3\equiv 11\pmod 4$ "4 divide a 11-3" además "4*2 + 3 = 11"

De forma general tenemos:

$b\equiv a\pmod n$ , su expresión en forma de ecuación sería "a = n*k + b", además "n | a-b" es decir "a-b es el múltiplo k de n". Si "a" es divisible entre "n" tendríamos $0\equiv a\pmod n$

Si no entendiste la parte anterior, tranquilo, revisa este tema https://en.wikipedia.org/wiki/Modular_arithmetic y vuelve cuando quieras.

Por lo tanto el CRT se basa en resolver el siguiente sistema de congruencias:

Dada una coleción de pares (a_i, n_i) tal que a_i < n_i donde a_i es el residuo y n_i el módulo de cada congruencia,

hallar x tal que:

$x\equiv a_{1}\pmod n_1$
$x\equiv a_{2}\pmod n_2$
$x\equiv a_{3}\pmod n_3$
...
$x\equiv a_i\pmod n_i$

Es decir, x dejará residuo $a_{1}$ al dividir por $n_1$ , residuo $a_2$ al dividir por $n_2$ etc.

Para que este sistema tenga solución, los módulos desde $n_1$ hasta $n_i$ deben de ser coprimos es decir gcd(n₁...n_i)=1. En cristiano, ninguno de los módulos puede estar compuesto por factores primos de otro módulo.

Si la coprimalidad se cumple, entonces expresaremos el módulo total como:

$N = n_1*n_2*n_3*...*n_i -> lcm(n_1...n_i)$

y aplicamos la siguiente fórmula:

$q = \sum_{k=0}^i a_k*N_k*[N_k^{-1}]_{n_k}$ Donde $N_k= \frac{N}{n_k}$ y $[N_k^{-1}]_{n_k}$ denota la multiplicativa modular inversa, $1\equiv N_k*t\pmod n_k$

Si lo reescribimos tenemos:

$q = \sum_{k=0}^i a_k*N_k*t_k$

Una vez calculadas y almacenadas en "q" las sucesivas iteraciones, obtenemos el residuo de nuestro nuevo sistema de la siguiente forma:

$u\equiv q\pmod N$ por lo tanto nuestra solucion al sistema final quedaría:

$x = N*k + u$

Ejemplo:
$x\equiv 2\pmod 3$
$x\equiv 3\pmod 5$
$x\equiv 2\pmod 7$

Primero probamos que los módulos son coprimos entre sí. Para ello comprobamos que gcd(3,5)=1 gcd(3,7)=1 gcd(5,7)=1.
Ahora calculamos el módulo total o variable multiplicativa del módulo:

$N = 3*5*7 = 105$

y aplicamos la fórmula arriba descrita paso por paso:

$q = \sum_{k=1}^i a_k*N_k*[N_k^{-1}]_{n_k}$

Empezamos por k=1, por lo tanto tenemos:

$a_1 = 2<br />n_1 = 3<br />N_1= \frac{N}{n_1} = \frac{105}{ 3} = 35$
$[N_1^{-1}]_{n_1}$ => para ello calculamos "t₁" mediante la multiplicativa modular inversa de N₁ en n₁, $1\equiv 35*t_k\pmod 3$ , a través de euler $t_1\equiv 35^{\phi(3)-1}\pmod 3$ por lo tanto t₁=2. Si hacemos 1=35*2 (mod 3) se satisface la relación.

Ahora multiplicamos a1*N1*t1 y lo dejamos en q:

q = 2*35*2 = 140

Sigamos

i=1

a₂ = 3
n₂ = 5
N₂ = N / n₂ = 105 / 5 = 21
[(N₂)^-1]_n₂ -> Resolvemos t₂ para hallar la mult. inv. mod. 1=21*t₂ (mod 5) de la siguiente forma: t₂ = 21^phi(5)-1 (mod 5), que equivale a t₂ = 21³ (mod 5), por lo tanto t₂=1.

y sumamos en q:

q = q + a₂*N₂*t₂ = q + 63 = 140 + 63 = 203

Última iteración

i = 2

a₃ = 2
n₃ = 7
N₃ = N / n₃ = 105 / 7 = 15
[(N₃)^-1]_n₃ -> Resolvemos t₃ para hallar la mult. inv. mod. 1=15*t₃ (mod 7) de la siguiente forma: t₃ = 15^phi(7)-1 (mod 7), que equivale a t₃ = 15⁵ (mod 7), por lo tanto t₃=1.

y sumamos en q:

q = q + a₃*N₃*t₃ = q + 30 = 203 + 30 = 233

Ahora falta el último paso para obtener la solución al sistema inicial:

Para ello computamos:

u = q (mod N)

u = 233 (mod 105)

u = 23

y la solución al sistema inicial sería:

x = u (mod N)

x = 23 (mod 105)

Para comprobar que la solución es fidedigna sustituimos x por 23 en el sistema inicial:

2 = 23 (mod 3)
3 = 23 (mod 5)
2 = 23 (mod 7)

Y como vemos se satisfacen las congruencias en su totalidad. Otras soluciones para X serían x = 105*k + 23 -> {23, 128, 233...}

Cosas a tener en cuenta:

En la vida real las multiplicativas modulares inversas se computan mediante el Extended Euclidean y no cómo yo he hecho en mi ejemplo, ya que necesitas la factorización de cada módulo mediante el procedimiento de Euler.

CONCEPTOS A TENER EN CUENTA:

https://en.wikipedia.org/wiki/Congruence_relation
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
https://en.wikipedia.org/wiki/Modulo_operation
https://en.wikipedia.org/wiki/Euler's_totient_function
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
https://en.wikipedia.org/wiki/Pairwise_coprime
https://en.wikipedia.org/wiki/Disquisitiones_Arithmeticae
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures

He implementado una función en C# la cual dadas dos listas que representan un sistema de congruencias, una de residuos y otra de módulos, devuelve una lista donde el primer elemento es X y el segundo elemento es N = n₁*n₂*..*n_i. La multiplicativa inversa modular se computa de forma iterativa sin el Extended Euclidean, ya que "a_i*t_i" dejarán un múltiplo "k_i" de "n_i" pequeño.

Código

private static BigInteger MultInv(BigInteger a, BigInteger b)
        {
            BigInteger inv = BigInteger.Zero, rem = BigInteger.Zero;
            BigInteger i = BigInteger.One;
            bool found = false;
            while (!found)
            {
                inv = BigInteger.DivRem(BigInteger.Add(BigInteger.Multiply(b, i), BigInteger.One), a, out rem);
                if (rem == BigInteger.Zero)
                    found = true;
                i++;
            }
            return inv;
        }
 
        private static List<BigInteger> ChineseRT(List<BigInteger> residues, List<BigInteger> modules)
        {
            List<BigInteger> sol = new List<BigInteger>(2);
            BigInteger N = BigInteger.One, ai = BigInteger.Zero, Ni = BigInteger.Zero, res = BigInteger.Zero;
            foreach (BigInteger m in modules)
                N = BigInteger.Multiply(N, m);
            for (int i = 0; i < modules.Count; i++)
            {
                ai = residues[i];
                Ni = BigInteger.Divide(N,modules[i]);
                res += BigInteger.Multiply(BigInteger.Multiply(ai, Ni), MultInv(Ni, modules[i]));
            }
            res = BigInteger.Remainder(res, N);
            sol.Add(res);
            sol.Add(N);
            return sol;
        }
 
        static void Main(string[] args)
        {
            List<BigInteger> residues = new List<BigInteger>();
            List<BigInteger> modules = new List<BigInteger>();
            residues.Add(2); residues.Add(3); residues.Add(2);
            modules.Add(3); modules.Add(5); modules.Add(7);
            List<BigInteger> sol = ChineseRT(residues, modules);
        }

EDIT: Seguiré adaptándolo a LateX.

Saludos!