Grupos de potencias en Zn (4) - Índices modulares

Índices modulares

En la entrada anterior estudiamos las raíces primitivas, elementos del grupo multiplicativo Z*_n de las unidades en Z_n (números coprimos con n), tales que su gaussiano es máximo y coincidente con j(n). Estas raíces, mediante sus potencias, engendran todo Z*_n, luego un elemento inversible cualquiera coincidirá con una potencia de la raíz primitiva. El exponente comprendido entre 0 y j(n)-1 que logra esta coincidencia recibe el nombre de índice del elemento respecto a la raíz primitiva. También es llamado logaritmo discreto.

Es decir; si a es una raíz primitiva y b un elemento inversible, existe un exponente k en el intervalo (0, j(n)-1) tal que a^kºb, y a ese exponente le llamaremos índice de b respecto a la raiz a.

Por ejemplo, el módulo 7 posee dos raíces primitivas. La raíz 3 engendra mediante potencias todos los elementos desde 1 a 6 (por ser 7 primo son todos inversibles), 3⁰º1, 3¹º3, 3²º2, 3³º6, 3⁴º4 y 3⁵º5. Cada uno de los exponentes es el índice de ese elemento.

La función índice que asigna a cada elemento inversible el exponente de la menor potencia de la raíz primitiva que lo engendra la podemos representar por ind_a(b) o simplemente ind(b) si se conoce la raíz. También podemos representarlo como un logaritmo, que en este caso recibe el nombre de logaritmo discreto. En el ejemplo anterior ind₃(6)=3, ind₃(4), ind₃(4)=4,…Si existe una raíz primitiva, todos los elementos inversibles de Z_m tendrán definido el índice.

Al ser un exponente, las propiedades del índice o logaritmo discreto son previsibles (supongamos módulo m):

El cálculo de los índices en grupos complejos no es fácil, aunque se han creado muchos algoritmos eficientes, y por eso los índices son usados en algunos sistemas criptográficos.

Aquí nos limitaremos, como siempre, a casos sencillos con los que aprender los conceptos. Hemos creado en nuestra hoja GAUSSIANO

http://www.hojamat.es/sindecimales/congruencias/herramientas/herrcong.htm#gaussiano

un confeccionador automático de tablas de índices para un módulo dado. Sólo tienes que escribir dicho módulo, y pulsar un botón para que aparezca la tabla, si es que existen raíces primitivas. Aquí tienes la del módulo 54:

En columna aparecen los elementos inversibles de Z₅₄, que hay 18, porque  j(54)=18. En la fila superior tenemos las raíces primitivas, que por ser 54 de la forma 2p^k (2*3³), existen con seguridad, y son 6, ya que j(j(54))=6. Con ella podemos encontrar el índice de cualquier inversible. Por ejemplo, el índice de 37 respecto a 23 es 12, lo que indica que 23¹²=37.

Ecuaciones potenciales

Las tablas de índices nos pueden servir para resolver la ecuación

El comportamiento de los índices como logaritmos nos permite transformar esta ecuación en otra lineal, eligiendo cualquier raíz primitiva b y aplicando índices en ambos miembros respecto a ella.

Según la teoría de las ecuaciones lineales en Z_m, si llamamos d al MCD(n, j(m)), el índice de a ha de ser múltiplo de d para que exista solución. En ese caso basta despejar el índice de x y buscar después el valor de x en las tablas. Podíamos haber automatizado todo el proceso, pero parece que se aprende más de esta forma.

Ejemplo: Resolver x⁶º37 (mod 54

En primer lugar encontramos que j(54)=18 (ver tabla y párrafos anteriores), luego d=MCD(6,18)=6. En la tabla citada buscamos el índice de 37 respecto a la raíz primitiva 5 y encontramos que es 12. Por tanto, como 12 es múltiplo de 6, deberá existir una solución (en realidad, según las propiedades de las ecuaciones lineales, deberían aparecer 6). Tomamos índices respecto al 5:

6*ind₅(x)ºind₅(37) (mod 54 º12

ind₅(x)º12/6=2.

Buscamos en la tabla qué inversible tiene índice 2 respecto a la raíz primitiva 5, y nos resulta 25. Comprobamos:

25¹º25; 25²º25*25º31; 25³º25*31º19; 25⁴º25*19º43; 25⁵º25*43º49; 25⁶º25*49º37

Así comprobamos que 25 es una solución de la ecuación propuesta. Pero hemos asegurado que existen otras cinco soluciones, que se pueden leer en la tabla si hubiéramos usado otra raíz primitiva. Son estas: 13, 43, 31, 7 y 49. Esto completa el conjunto de seis soluciones de la ecuación propuesta.
Otras ecuaciones de ese tipo no tienen solución. Por ejemplo:

x⁷º12 (mod 49

Formamos la tabla de índices módulo 49 y vemos que ind₃(12)=11, que j(49)=42 y MCD(7,42)=7, pero 11 no es múltiplo de 7, luego no existe solución. Hemos creado una tabla con las séptimas potencias de los inversibles de Z*₄₉ y sólo nos resultan seis resultados posibles: {1, 30, 31, 18, 19, 48}, y el 12 no está entre ellos.

El ejemplo anterior nos da una pista para descubrir si un resto dado es cúbico, bicuadrado o de otro orden en un módulo dado. Por ejemplo, ¿es resto bicuadrado 15 en módulo 22? Planteamos a⁴º15 (mod 22 y analizamos:

Formamos la tabla de índices módulo 22

j(22)=10 y MCD(4,10)=2, luego ind(15) ha de ser múltiplo de 2. Según la tabla, se cumple para cualquier raíz primitiva, luego sí es un resto bicuadrado. Podemos encontrar su raíz cuarta:
4ind(a)=2, luego ind(a)=2/4 (mod 22 = 6

El 3 posee índice 6, y cumple 3⁴º15 (mod 22, luego existe la raíz bicuadrada de 15, y este valor 15 es resto bicuadrado (sólo hemos investigado una posibilidad, pero con una basta).