Ayer por la tarde, intentando resolver un problema de programación, me encontré que tenía que resolver la raíz cuadrada de un número módulo n. Recordé que eso lo había estudiado en Criptografía, pero, como me suele suceder, no me sé de memoria el algoritmo. Cuando llegué a casa revisé mis apuntes y allí lo encontré, y me pareció tan curioso que me gustaría exponerlo aquí por si a alguien puede serle de utilidad.
0. Supongamos que queremos calcular las raíces cuadradas de una cantidad c módulo n. En primer lugar, debemos encontrar dos factores positivos, p y q, tales que n = p*q. Estos dos factores deben cumplir además que deben ser primos entre sí y congruentes con 3 módulo 4 (es decir, que su resto al dividirlos entre 4 debe ser 3). Si no conseguimos hacer esto, no podremos aplicar el método que viene a continuación.
1. Seguidamente, aplicaremos el algoritmo de Euclides extendido para obtener dos números a y b tales que a*p+b*q=1. Podemos hacer esto ya que el algoritmo de Euclides extendido nos proporciona los números a y b que cumplen a*p+b*q=mcd(p,q), y al ser p y q primos entre sí por cómo los hemos elegido, su máximo común divisor es 1.
2. Recordemos que c es la cantidad cuya raíz cuadrada módulo n queremos calcular. Llamaremos: r = c^((p+1)/4) mód p; s = c^((q+1)/4) mód q.
3. Llamaremos ahora m1 = (a*p*s + b*q*r) mód n; m2 = (a*p*s - b*q*r) mód n
4. Las cuatro raíces de c módulo n son m1, -m1 mód n (es decir, n-m1), m2 y -m2 mód n (n-m2, igual que antes).
Como el algoritmo anterior igual es un poco denso voy a dar un ejemplo en el que se aplique. Supongamos que queremos calcular las raíces cuadradas de 16 módulo 21.
0. En este caso n = 21 = 3 * 7. Es fácil que comprobar que tanto 3 como 7 son congruentes con 3 módulo 4. Por tanto, p = 3 y q = 7.
1. Aplicando el algoritmo de Euclides extendido obtenemos que a = -2 y b = 1 (podemos usar, por ejemplo, el applet del link anterior).
2. r = 16^((3+1)/4) mód 3 = 16^1 mód 3 = 16 mód 3 = 1;
s = 16^((7+1)/4) mód 7 = 16^2 mód 7 = 256 mód 7 = 4
3. m1 = (-2*3*4 + 1*7*1) mód 21 = -17 mód 21 = 4;
m2 = (-2*3*4 - 1*7*1) mód 21 = -31 mód 21 = 11
4. Las cuatro raíces cuadradas de 16 módulo 21 son: 4, 17 (-4 mód 21), 11 y 10 (-11 mód 21).
Hace 9 meses
Entradas
Raiz cuadrada de un número c módulo n tiene dos significados:
ResponderEliminar(c^1/2) mod n
(c mod n)^1/2
¿Cuál es la que tú quieres buscar? Porque yo me he perdido enseguida con esas propiedades tan chungas de por medio.
Creo que la forma más fácil de definir el conjunto de las raíces cuadradas de un número c módulo n es {x | (x*x) mód n = c}.
ResponderEliminarEn el ejemplo lo puedes comprobar:
(4 *4) mód 21 = 16 mód 21 = 16
(17 * 17) mód 21 = 289 mód 21 = 16
(11 * 11) mód 21 = 121 mód 21 = 16
(10 * 10) mód 21 = 100 mód 21 = 16
También hay que decir que no todos los números tienen raíces cuadradas módulo n, es decir, que aunque este procedimiento se puede seguir para todos los números las soluciones que nos dé no siempre serán válidas; lo mejor será comprobarlas de la forma anterior.
Entonces no comprendo porqué son "raíces cuadradas de un numero c módulo n". En todo caso serían "números cuyos cuadrados módulo n dan c". El término es erróneo, a menos que sea un nombre propio para esta operación, en cuyo caso me parece inadecuado.
ResponderEliminarEllohir, creo que el término es correcto. Por ejemplo, en la entrada de la wikipedia sobre el Criptosistema Rabin se habla de él.
ResponderEliminarEn álgebra modular no se cumplen "estrictamente" algunas de las propiedades que sí se dan en, por ejemplo, los reales. Por ejemplo, y corrígeme si me equivoco, en los naturales tampoco tiene sentido hablar de raíz cuadrada como x^(1/2), porque 1/2 tampoco es un número natural y porque habría números que no tendrían raíz. En este conjunto de números la definición de raíz cuadrada de c podría ser justamente la de "número cuyo producto por sí mismo da c".
Tal vez mi razonamiento no sea del todo bueno, si es así te agradeceré que me corrijas.
No te entiendo. ¿Crees que el término es correcto y luego dices que la raiz no está bien definida en los naturales? ¿WTF?
ResponderEliminarYo no estoy hablando de en qué dominios se aplican ni nada de eso. Digo que la frase "Raiz cuadrada de un número c módulo n" tiene dos significados tomando por separado los elementos de la frase, y estos resultados son "(c^1/2) mod n" y "(c mod n)^1/2" y ninguno de ellos es "{x | (x*x) mód n = c}".
A ver, por partes:
ResponderEliminar- Sí, creo que el término es correcto, al fin y al cabo cuando tú haces la raíz de un número lo que haces es hallar otro número tal que multiplicado por sí mismo da el primero, sea o no en módulo.
- También creo que la raíz no está bien definida en los naturales. Esto lo pongo porque hay ciertos dominios en que creo que la raíz no se acoge a su definición como potencia (n^1/2), sino a la definición del párrafo de arriba; es decir, que ambas definiciones no tienen por qué ser equivalentes en todos los dominios.
Por otra parte, tienes razón, dependiendo de cómo se lea se pueden ver dos significados, y además totalmente distintos (por ejemplo, si probamos con "raíz cuadrada de 9 módulo 5"). Sin embargo, creo que ninguno de los dos se corresponde con lo que se calcula, por más que el término me sigue pareciendo el adecuado, tal vez por un abuso del término "raíz cuadrada". De todas formas, y como digo arriba, sigo pensando que las definiciones de raíz cuadrada como potencia fraccionaria y como conjunto de los números que multiplicados por sí mismos dan otro concreto no son equivalentes, y que aquí se aplica la última de esas dos.
La raíz es una función, es decir, una aplicación R->R.
ResponderEliminarSi tomamos sólo casos N->R podemos convertirla a una sucesión, sólo hay que saltarse los no-enteros en la primera parte. Es decir, aplicamos la función normalmente pero se coge un subconjunto de las parejas.
Para la aplicación N->N también podemos usar ambas, sólo hay que saltarse los no-enteros de ambas partes. Un subconjunto del subconjunto anterior.
No veo ningún problema con las definiciones. Simplemente si quieres definirnla en los naturales coge sólo las soluciones en los naturales.
----------
¿Por qué estoy discutiendo esto?
En fin, dejo ya la discusión que me cansa. Sólo quería decir eso, que esta operación tiene un nombre cuando menos ambiguo y punto. Y no, no he podido encontrar un nombre más adecuado.
Genial el blog, cada entrada es una sorpresa nueva xD Tienes de todo por aqui jeje
ResponderEliminarGracias Ainoa, ¡siempre está bien que le suban a uno la moral un poquito! Siempre será un placer verte por aquí, estás invitada a pasarte cuando quieras. :-)
ResponderEliminarHi guys, I left a link http://www.cacr.math.uwaterloo.ca/hac/
ResponderEliminarwhere square root mod is explained
Bye4now
Thanks, Anonymous, for you link. It's very interesting!
ResponderEliminarpuedes decirme pq -31mod21=11?? no entiendo
ResponderEliminarporfa explica eso.. buh
ResponderEliminarClaro, ahí va la explicación.
ResponderEliminarUna manera sencilla de saber x mod y cuando x es un número negativo es sumar y sucesivas veces hasta que obtengamos el primer número positivo. En este caso:
-31 + 21 = -10 + 21 = 11
Por eso, -31mod21 = 11 ;-)
Turn your mobile phone into an extraordinary gadget with LED Black - Berry apps.
ResponderEliminarThere health benefits outnumber their disadvantages, if any.
However, my husband had a little trouble tightening the
screw on the solar panel, so it tended to slip to less than an optimal angle.
Also visit my weblog :: Wandleuchten
No se entendió nada
ResponderEliminar