[Taller] Chinese Remainder Theorem

[kub0x]

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:

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

De forma general tenemos:

[latex]b\equiv a\pmod n[/latex] , 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 [latex]0\equiv a\pmod n[/latex]

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:

[latex]x\equiv a_{1}\pmod n_1[/latex]
[latex]x\equiv a_{2}\pmod n_2[/latex]
[latex]x\equiv a_{3}\pmod n_3[/latex]
...
[latex]x\equiv a_i\pmod n_i[/latex]

Es decir, x dejará residuo [latex]a_{1}[/latex] al dividir por [latex]n_1[/latex], residuo  [latex]a_2[/latex] al dividir por [latex]n_2[/latex] etc.

Para que este sistema tenga solución, los módulos desde [latex]n_1[/latex] hasta [latex]n_i[/latex] 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:

[latex]N = n_1*n_2*n_3*...*n_i -> lcm(n_1...n_i)[/latex]

y aplicamos la siguiente fórmula:

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

Si lo reescribimos tenemos:

[latex]q = \sum_{k=0}^i a_k*N_k*t_k[/latex]

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

[latex]u\equiv q\pmod N[/latex] por lo tanto nuestra solucion al sistema final quedaría:

[latex] x = N*k + u [/latex]

Ejemplo:
[latex]x\equiv 2\pmod 3[/latex]
[latex]x\equiv 3\pmod 5[/latex]
[latex]x\equiv 2\pmod 7[/latex]

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:

[latex]N = 3*5*7 = 105[/latex]

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

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

Empezamos por k=1, por lo tanto tenemos:

[latex]a_1 = 2
n_1 = 3
N_1= \frac{N}{n_1} = \frac{105}{ 3} = 35[/latex]
[latex][N_1^{-1}]_{n_1}[/latex] => para ello calculamos "t₁" mediante la multiplicativa modular inversa de N₁ en n₁, [latex]1\equiv 35*t_k\pmod 3[/latex], a través de euler [latex]t_1\equiv 35^{\phi(3)-1}\pmod 3[/latex] 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]_n2 -> 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]_n3 -> 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 (csharp) [Seleccionar] Expandir

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!

[AlbertoBSD]

Es posible que n_i sea igual a otro n_k?

Lo lei el otro dia y hoy amaneci con la idea de usarlo para buscar a un testigo correcto parael test de fermat fe numero primo ya sabes por aquello de los liars.. peto no se si sea aplicable

¿Que otros  validos usos puede tener?

[kub0x]

Es posible que n_i sea igual a otro n_k?

Realmente no, pues X es un valor común relacionado con todos los n_i por lo tanto si tenemos lo siguiente:

X = y (mod n_i)
X = z (mod n_i)

Como ves este sistema de congruencias lineales no se sostiene, ya que es imposible que un mismo número X deje dos restos 'y' 'z' distintos con el mismo módulo n_i, por eso los módulos deben de ser coprimos entre sí.

Bueno este teorema tiene varias aplicaciones en la criptografía:

- Secret Sharing con interpolación de polinomios (i.e de Lagrange) (el secreto se reconstruye con el Chinese Remainder Theorem).
- Pohlig-Hellman para computar el logaritmo discreto en grupos multiplicativos finitos, si el orden del módulo tiene factores triviales, CRT y consigues la privada.
- En RSA a la hora de computar el par de claves y firmar/cifrar mensajes, ya que el coste computacional queda reducido a dos exponenciales modulares.

Luego tiene más aplicaciones en otras ramas de la matemática, como en las Fourier transform.

Saludos!

[Gh057]

(casi off. topic XD) No pude dejar de comentar el excelente aporte que haz dejado kub0x; si bien es cierto que se dificulta por la notación, desde ya agradecido por las referencias indicadas para seguir el hilo del tema. También aprovecho el medio para agradecerte por las referencias anteriormente indicadas, las cuales sigo intentando dedicar tiempo de mis ratos libres  -y disfrutando!-  como es el caso de una edición de tapas duras de B. Scheider "Applied Cryptography". Sublime. XD

A mi corto entender, e intentando responder la consulta de AlbertoBSD, la aplicación más práctica que me viene a la mente del CRT es la de acelerar el descifrado en el intercambio de claves... al tener k y siendo primos p y q, puede utilizar números más pequeños que sean a su vez primos, y de esa forma realizar operaciones modulares en el orden de la mitad de bits... Saludos.