ÁLGEBRA

ARITMÉTICA MODULAR

 raíz primitiva módulo n (abreviado mod n), si a genera como grupo a ${\displaystyle \mathbb {Z} _{n}^{*}}$, es decir, si ${\displaystyle \forall b\in \mathbb {Z} _{n}^{*}}$ existe ${\displaystyle k\in \mathbb {Z} }$ tal que ${\displaystyle a^{k}\equiv b(mod\ n)}$. Aquí ${\displaystyle \mathbb {Z} _{n}^{*}}$ denota los elementos invertibles módulo n.

Dado que el orden de ${\displaystyle \mathbb {Z} _{n}^{*}}$ es ${\displaystyle \varphi (n)}$, siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.

Ejemplos[editar]

Si ${\displaystyle n=5}$ entonces 3 es raíz primitiva módulo 5:

${\displaystyle {\begin{array}{l}3^{1}=3\\3^{2}=9\equiv 4{\pmod {5}}\\3^{3}=3^{2}\times 3\equiv 4\times 3=12\equiv 2{\pmod {5}}\\3^{4}=3^{3}\times 3\equiv 2\times 3=6\equiv 1{\pmod {5}}\\\end{array}}}$

Si observamos bien, todo resto coprimo con 5 (1,2,3 y 4) es congruente con ${\displaystyle 3^{k}}$ módulo 5 para algún ${\displaystyle k\in \mathbb {Z} }$. De hecho (y esto ocurre para toda raíz primitiva) el ${\displaystyle k}$ puede elegirse entre 1 y ${\displaystyle 4=\varphi (5)}$.

Para ${\displaystyle n=14}$ tenemos que 5 es raíz primitiva:

${\displaystyle {\begin{array}{l}5^{0}=1\\5^{1}=5\\5^{2}=25\equiv 11{\pmod {14}}\\5^{3}=5^{2}\times 5\equiv 11\times 5=55\equiv 13{\pmod {14}}\\5^{4}=5^{3}\times 5\equiv 13\times 5=65\equiv 9{\pmod {14}}\\5^{5}=5^{4}\times 5\equiv 9\times 5=45\equiv 3{\pmod {14}}\\\end{array}}}$

${\displaystyle \mathbb {Z} _{14}^{*}=\{1,3,5,9,11,13\}}$, o sea que obtenemos todos los elementos de ${\displaystyle \mathbb {Z} _{14}^{*}}$ como potencias de 5.

Existencia de raíces primitivas[editar]

Se puede demostrar que si p es un número primo, entonces existe alguna raíz primitiva módulo p (para la demostración se utiliza el hecho de que ${\displaystyle \mathbb {Z} _{p}}$ es un cuerpo cuando p es primo). Fijada b una raíz primitiva módulo p, cualquier entero a que no sea divisible entre p puede escribirse como ${\displaystyle a=b^{r}{\pmod {p}}}$ para un único ${\displaystyle r\in \{1,2,...,p-1\}}$.

También puede demostrarse que si ${\displaystyle n=p^{k}}$ con p un primo impar (mayor que 2), entonces existen raíces primitivas módulo n, así como también existen raíces primitivas módulo n cuando n=1, ${\displaystyle n=2p^{k}}$, siendo p, como antes, un primo impar. Éstos, junto con el valor n=4, son los únicos números n que permiten raíces primitivas módulo n.

Aplicaciones[editar]

Al utilizar el protocolo criptográfico Diffie-Hellman suelen escogerse un primo p y g una raíz primitiva módulo p. Como dijimos, dado ${\displaystyle b\in \mathbb {Z} _{p}^{*}}$ se tiene ${\displaystyle b=g^{r}{\pmod {p}}}$ para un único ${\displaystyle r\in \{1,2,...,p-1\}}$. Encontrar ese rfijados a y b es lo que se conoce como el problema del logaritmo discreto.

récords en logaritmos discretos son los mejores resultados obtenidos hasta la fecha en la resolución del problema del logaritmo discreto, consistente en encontrar soluciones de x para la ecuación g^x = h, dados dos elementos g y h pertenecientes a un grupo cíclico finito G. La dificultad de resolver el problema es la base de la seguridad de numerosos sistemas criptográficos, entre ellos el protocolo Diffie-Hellman, el cifrado ElGamal, el Algoritmo de Firma Digital (DSA), o la criptografía de curvas elípticas. La elección más habitual de G utilizada en esos algoritmos incluye el grupo multiplicativo de enteros módulo p, el grupo multiplicativo de un cuerpo finito, y el conjunto de puntos de una curva elíptica sobre un cuerpo finito.

Enteros módulo p[editar]

El 18 de junio de 2005, Antoine Joux y Reynald Lercier anunciaron la computación de un logaritmo discreto módulo un número primo fuerte de 130 dígitos (431 bits) en tres semanas, utilizando para ello un ordenador HP AlphaServer GS1280 con 16 procesadores a 1.15 GHz ejecutando un algoritmo de criba general del cuerpo de números (GNFS).¹​

El 5 de febrero de 2007, fue superado con el anuncio de Thorsten Kleinjung de la computación de un logaritmo discreto módulo un número primo fuerte de 160 dígitos (530 bits), usando de nuevo la criba general del cuerpo de números. La mayor parte de la computación fue realizada utilizando tiempo muerto de CPU en varios ordenadores de un clúster de computación en paralelo.²​

Cuerpos finitos[editar]

El récord actual (a fecha de 2013) en un cuerpo finito de característica 2 fue anunciado por Antoine Joux el 21 de mayo de 2013. Su equipo fue capaz de computar logaritmos discretos en el cuerpo de 2⁶¹⁶⁸ = (2²⁵⁷)²⁴ elementos usando para ello menos de 550 horas de CPU. Esta computación fue realizada utilizando el mismo algoritmo de cálculo empleado en la computación reciente del cuerpo con 2⁴⁰⁸⁰ elementos.³​

Los récords anteriores en cuerpos finitios de característica 2 fueron anunciados por:

• Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 11 de abril 2013. La nueva computación trataba con el cuerpo de 2⁶¹²⁰ elementos y demoró 749,5 horas de CPU.

• Antoine Joux el 22 de marzo de 2013. Utilizó el mismo algoritmo⁴​ para cuerpos de característica pequeña que en la anterior computación del cuerpo de 2¹⁷⁷⁸ elementos. Se computó en el cuerpo con 2⁴⁰⁸⁰elementos, representado como una extensión de grado 255 del cuerpo con 2¹⁶ elementos, utilizando para ello menos de 14100 horas de CPU.⁵​

• Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 19 de febrero de 2013. Utilizaron una nueva variante de la criba general del cuerpo de números con un cuerpo base de tamaño medio, para cuerpos binarios, para computar un logaritmo discreto en un cuerpo de 2¹⁹⁷¹ elementos. Para poder usar un cuerpo base de tamaño medio representaron el cuerpo como una extensión de grado 73 del cuerpo de 2²⁷elementos. La computación demoró 3132 horas de CPU en un clúster SGI Altix ICE 8200EX utilizando procesadores de 6 núcleos Intel (Westmere) Xeon E5650.⁶​

• Antoine Joux el 11 de febrero de 2013. Utilizaba un nuevo algoritmo para cuerpos de característica pequeña. Se computó en un cuerpo de 2¹⁷⁷⁸ elementos, representedo como una extensión de grado 127 del cuerpo con 2¹⁴ elementos. El cómputo se realizó en menos de 220 horas de CPU.⁷​

El récord actual (a fecha de 2013) para un cuerpo finito de característica 2 de grado primo fue anunciado por el grupo CARAMEL el 6 de abril de 2013. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en una cuerpo de 2⁸⁰⁹ elementos.⁸​ El récord anterior en un cuerpo finito de característica 2 de grado primo fue anunciado por Antoine Joux y Reynald Lercier el 23 de septiembre de 2005. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en un cuerpo de 2⁶¹³ elementos. El cómputo demoró 17 días en cuatro nodos de 16 procesadores, a 1.3 GHz cada uno, del súper-ordenador Teranova, basado en el Itanium 2.⁹​

El récord actual (a fecha de 2012) para un cuerpo de característica 3 fue anunciado por una asociación entre Fujitsu, NICT y el equipo de la Universidad de Kyushu, que computaron un logaritmo discreto en el cuerpo de 3^6 · 97 elementos, de 923 bits de tamaño,¹⁰​ empleando una variante de la criba general del cuerpo de números, superando así el récord anterior en el cuerpo de 3^6 · 71 elementos de 676 bits ¹¹​ por un amplio margen.

Respecto a cuerpos de característica de tamaño "moderado", computaciones notables realizadas en 2005 incluyen aquélla sobre el cuerpo de 65537²⁵ elementos (401 bits), anunciada el 24 de octubre de 2005, y la del cuerpo de 370801³⁰ elementos (556 bits), anunciada el 9 de noviembre de 2005.¹²​ El récord actual (a fecha de 2013) para un cuerpo finito de característica "moderada" fue anunciada el 6 de enero de 2013. El equipo empleo una nueva variante de la criba general del cuerpo de números para el caso de primos medios para computar un logaritmo discreto en un cuerpo de 33341353⁵⁷ elementos (un cuerpo finito de 1425 bits).¹³​¹⁴​ Se había empleado la misma técnica unas semanas antes para computar un logaritmo discreto en un cuerpo de 33553771⁴⁷ elementos (un cuerpo finito de 1175 bits).¹⁵​¹⁴​

Curvas elípticas[editar]

La corporación Certicom ha propuesto una serie de desafíos relacionados con la Criptografía de curva elíptica. El nivel I involucra cuerpos de 109 y 131 bits. El nivel II incluye los de 163, 191, 239 y 359 bits. Se cree que todos los desafíos de nivel II son computacionalmente inviables.¹⁶​

Los desafíos de nivel I que han sido superados son:¹⁷​

• ECC2K-108, consistente en tomar un logaritmo discreto en una curva de Koblitz sobre un cuerpo de 2¹⁰⁸elementos. El premio fue otorgado el 4 de abril de 2000 a un grupo de unas 1300 personas, representado por Robert Harley. Utilizaron una paralelización del algoritmo rho de Pollard para logaritmos.

• ECC2-109, que consistía en tomar un logaritmo discreto en una curva sobre un cuerpo de 2¹⁰⁹ elementos. El 8 de abril de 2004 se otorgó el premio a un grupo de unas 2600 peronas representado por Chris Monico. También emplearon una versión paralelizada del algoritmo rho de Pollard para logaritmos, durando el cáculo 17 meses de tiempo real.

• ECCp-109, consistente en tomar un logaritmo discreto en una curva modulo un primo de 109 bits. El premio se otorgó el 15 de abril de 2002 a un grupo de 10308 personas, representado por Chris Monico. De nuevo se empleó una variante paralelizada del algoritmo rho de Pollard para logaritmos, demorando 549 días de tiempo real.

Ninguno de los desafíos de 131 bits (o superiores) han sido superados a fecha de 2010.

En julio de 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra y Peter L. Montgomery anunciaron que habían conseguido computar un logaritmo discreto en una curva elíptica módulo un primo de 112 bits. La computación fue realizada mediante un clúster de 200 PlayStation 3 durante 6 meses, empleando la versión paralelizada más común del algoritmo rho de Pollard para logaritmos.

 residuo cuadrático módulo ${\displaystyle m}$ a cualquier entero ${\displaystyle r}$ coprimo con ${\displaystyle m}$ para el que tenga solución la congruencia:

${\displaystyle x^{2}\equiv r{\pmod {m}},}$

o lo que es lo mismo cuando ${\displaystyle r}$ es un cuadrado no nulo módulo ${\displaystyle m}$, y que por lo tanto tiene una raíz cuadrada en la aritmética de módulo ${\displaystyle m}$.¹​²​ A los enteros que no son congruentes con cuadrados perfectos módulo ${\displaystyle m}$ se les denomina no-residuos cuadráticos. En adelante nos referimos a menudo a ellos como residuos y no-residuos.

En el estudio de los residuos cuadráticos es conveniente limitarse al caso en el que el módulo es un primo ${\displaystyle p}$, ya que entonces tenemos un comportamiento mucho más sencillo, y muchas propiedades de los residuos para módulos generales pueden derivarse de este caso usando el teorema chino del resto, y otros resultados de la resolución de congruencias. Para estudiar este caso es muy conveniente el uso del símbolo de Legendre, y de su extensión el símbolo de Jacobi.

Ejemplo[editar]

Si tomamos el primo p=13, se tiene que 1² = 12² = 1 (mod 13), 2² = 11² = 4 (mod 13), 3² = 10² = 9 (mod 13), 4²= 9² = 3 (mod 13), 5² = 8² = 12 (mod 13), 6² = 7² = 10 (mod 13).

Por lo tanto, los residuos cuadráticos módulo 13 son: 1, 3, 4, 9, 10 y 12; los no residuos: 2, 5, 6, 7, 8, y 11.

Notación[editar]

Gauss³​ usó R y N para denotar residuos y no residuos, respectivamente;

por ejemplo, 2 R 7 y 5 N 7, o 1 R 8 y 3 N 8.

A pesar de que esta notación es compacta y conveniente para algunos propósitos,⁴​⁵​ una mejor notación es el símbolo de Legendre, que también se conoce como carácter cuadrático, que se define para todos los números enteros a y números primos impares p como

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ si }}p{\text{ divide a }}a\\+1&{\text{ si }}a\operatorname {R} p\\-1&{\text{ si }}a\operatorname {N} p\end{cases}}}$

Una ventaja de esta notación sobre la de Gauss es que el símbolo de Legendre es una función que puede usarse en fórmulas. Otra es que el símbolo se puede generalizar fácilmente a residuos cúbicos, residuos bicuadráticos y en general de residuos potenciales.⁶​

Propiedades básicas²​[editar]

• El producto de dos residuos o de dos no-residuos es un residuo y el producto de un residuo y de un no-residuo es un no-residuo.
• Si ${\displaystyle p}$ es primo, la mitad de las ${\displaystyle p-1}$ clases residuales módulo ${\displaystyle p}$ son residuos y la otra mitad no-residuos.
• El criterio de Euler afirma que ${\displaystyle \textstyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}}$. Esto significa que a es un residuo cuadrático módulo p si y solo si ${\displaystyle \textstyle a^{\frac {p-1}{2}}\equiv 1{\pmod {p}}}$.
• -1 es un residuo de todos los primos de la sucesión ${\displaystyle 4k+1}$ y es un no-residuo de todos los primos de la sucesión ${\displaystyle 4k+3}$
• 2 es un residuo de todos los primos de las sucesiones ${\displaystyle 8k+1}$ y ${\displaystyle 8k+7}$ y es un no-residuo de todos los demás primos impares.
• Si ${\displaystyle p}$ y ${\displaystyle q}$ son primos impares, y ninguno de ellos pertenece a la sucesión ${\displaystyle 4k+1}$ entonces ${\displaystyle p}$ es un residuo módulo ${\displaystyle q}$ si y sólo si ${\displaystyle q}$ es un no-residuo módulo ${\displaystyle p}$. Si por otro lado cualquiera de los dos, o ambos, pertenecen a la sucesión ${\displaystyle 4k+1}$ entonces ${\displaystyle p}$ es un residuo módulo ${\displaystyle q}$ si y solo si ${\displaystyle q}$ es un residuo módulo ${\displaystyle p}$.

A esta última propiedad se le conoce como la ley de reciprocidad cuadrática, y es uno de los teoremas más importantes de la teoría elemental de números.

Algunas aplicaciones[editar]

Los residuos cuadráticos son útiles para varios test de primalidad, así como para algoritmos que permiten factorizar enteros. Se destaca entre ellos el test de primalidad de Solovay-Strassen, que utiliza el criterio de Eulerjunto a las propiedades del símbolo de Jacobi. Es un test probabilístico.⁷​

Problemas abiertos y conjeturas[editar]

Uno de los problemas abiertos más importantes sobre residuos cuadráticos es determinar el orden de magnituddel mínimo no-residuo cuadrático positivo ${\displaystyle n(p)}$. El mejor resultado conocido, debido a Burguess, asegura que la expresión

${\displaystyle {\frac {n(p)}{p^{1/4{\sqrt {e}}}}}}$

está acotada para todos los primos, y se conjetura que el resultado podría seguir siendo cierto si sustituimos el denominador por ${\displaystyle (\log p)^{2}}$.