El Teorema Fundamental de los Grupos Cíclicos proporciona garantías sobre la existencia de subgrupos cíclicos dentro de un grupo cíclico.

En el contexto de la Number Theoretic Transform (NTT) de polinomios sobre un campo finito, y también la operación FRI en ZK-STARKs, necesitamos subgrupos multiplicativos cuyo orden (número de elementos) sea una potencia de dos. El Teorema Fundamental de los Grupos Cíclicos nos permite determinar rápidamente si un campo finito particular tiene un subgrupo multiplicativo con ese orden o no.

Cubriremos lo siguiente como preliminares, para luego pasar al Teorema Fundamental de los Grupos Cíclicos:

1. Definición de un Subgrupo
2. Orden de un Grupo o Subgrupo
3. Potencias de un Elemento en un Grupo Multiplicativo
4. Subgrupos Cíclicos, Grupos Cíclicos y sus Generadores

1. Definición de un Subgrupo

Dado un grupo $G$, un subconjunto $H$ de $G$ es un subgrupo de $G$ si $H$ forma un grupo con respecto a la operación de grupo en $G$. En otras palabras, si nos restringimos a los elementos de $H$ pero seguimos usando la operación de grupo de $G$, todos los criterios para un grupo se siguen cumpliendo. Lo más importante es que la operación debe ser cerrada en $H$, por lo que siempre que apliquemos la operación en dos elementos de $H$, debemos obtener otro elemento de $H$.

Ejemplo de Subgrupos

El conjunto de enteros módulo 8 bajo la suma forma un grupo $\mathbb{Z}_8 = (\{0, 1, 2, 3, 4, 5, 6, 7\}, +)$. $H_1=(\{0, 2, 4, 6\}, +)$ y $H_2=(\{0, 4\}, +)$ son ambos subgrupos de $\mathbb{Z}_8$. Por otro lado, $H_3=(\{0, 2\}, +)$ no lo es, porque $(2+2) \not \in H_3$

2. Orden de un Grupo o Subgrupo

El orden de un grupo $G$, denotado por $|G|$, es su número de elementos. Si un grupo no es finito, se dice que su orden es infinito.

Ejemplo para el orden de un grupo y subgrupo

Considera el grupo $\mathbb{Z}_8$ del ejemplo anterior. El orden de $\mathbb{Z}_8$ es 8, lo que significa que $|\mathbb{Z}_8| = 8$ (ya que hay exactamente 8 elementos en el grupo). Además, el orden del subgrupo $H = (\{0, 2, 4, 6\}, +)$ es 4 (es decir, $|H| = 4$).

3. Potencias de un elemento en un grupo multiplicativo

Si $g \in G$, las potencias del elemento $g$, denotadas por $\langle g\rangle$, forman el conjunto $\{g^i: i\in\mathbb{Z}\}$. Por ejemplo, considera el grupo de enteros distintos de cero bajo la multiplicación módulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. Las potencias del elemento $3$ en $G$ son las siguientes:

Dado que:

¿Qué hay de $3^7$?

Por lo tanto, $\langle 3\rangle = \{1, 2, 3, 4, 5, 6\}$. Para cada potencia $3^i$ con $i>6$, el resultado será uno de los elementos que ya están en esta lista.

Ejercicio: Encuentra el conjunto generado por el elemento $4$.

Las potencias de un elemento arbitrario forman un Subgrupo

Sea $g$ un elemento arbitrario en $G$. El conjunto de potencias del elemento $g$ forma un subgrupo. En otras palabras,

es un subgrupo de $G$.

Demostración. Ver el apéndice

4. Subgrupos Cíclicos, Grupos Cíclicos y sus Generadores

Sea $g$ un elemento arbitrario en $G$, entonces el subgrupo $\langle g\rangle = \{g^i: i\in\mathbb{Z}\}$ se denomina subgrupo cíclico de $G$ generado por $g$. Por ejemplo, considera el grupo de enteros distintos de cero bajo la multiplicación módulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. El subgrupo cíclico generado por el elemento $2$ es:

Ejercicio: Encuentra el subgrupo generado por el elemento $6$.

Definición de un Grupo Cíclico

Sea $g$ un elemento arbitrario en $G$. Si $G = \langle g\rangle$, entonces decimos que $G$ es un grupo cíclico y que $g$ es un generador de $G$. En otras palabras, un grupo es cíclico si contiene al menos un elemento que genera todos los elementos del grupo.

Ejemplo de Grupo Cíclico y Generadores

Considera el grupo de enteros distintos de cero bajo la multiplicación módulo 7, $G =\{1, 2, 3, 4, 5, 6\}$. Dado que $\langle 3 \rangle = G$, como se mostró anteriormente, entonces $G$ es un grupo cíclico y $3$ es un generador de $G$.

Ten en cuenta que $\langle 2 \rangle = \{1, 2, 4\}\neq G$, lo que significa que el elemento $2$ no es un generador de $G$, sino que 2 genera un subgrupo de $G$.

Ejercicio: Determina si $5$ es un generador de $G$

Los Generadores de los Grupos Cíclicos No Son Necesariamente Únicos

Los grupos cíclicos tienen al menos un generador, pero el generador no tiene que ser único. En otras palabras, un grupo cíclico puede tener múltiples generadores, cualquiera de los cuales genera el grupo entero. Lo mismo ocurre con los subgrupos cíclicos.

Como viste en el ejemplo y ejercicio anteriores, los elementos $3$ y $5$ son ambos generadores del grupo $G =\{1, 2, 3, 4, 5, 6\}$.

Como otro ejemplo, considera el grupo de enteros distintos de cero bajo la multiplicación módulo 5. Es decir, $\{1, 2 ,3, 4\}$. Los elementos $2$ y $3$ generan todo el grupo.

El Teorema Fundamental de los Grupos Cíclicos Finitos

El Teorema Fundamental de los Grupos Cíclicos Finitos hace tres afirmaciones. Sea $G$ un grupo cíclico finito, y sea $H$ un subgrupo de $G$.

1. $H$ es necesariamente finito y cíclico (lo que significa que $H$ tiene un generador).
2. El orden de $H$ (el número de elementos que tiene) es un factor del orden de $G$. En otras palabras, el orden de $H$ divide el orden de $G$. Por ejemplo, supongamos que el orden de $G$ es 6. Automáticamente sabemos que un subgrupo de orden 5 no puede existir, ya que 5 no divide a 6.
3. Si $q$ es el orden de $G$ y $k$ divide a $q$, entonces un subgrupo de tamaño $k$ necesariamente existe y es único. De hecho, podemos encontrar un generador para él inmediatamente: si $g$ es un generador de $G$, entonces $g^\frac{q}{k}$ es un generador para un subgrupo de tamaño $k$. Este subgrupo de tamaño $k$ es igual a $\langle g^\frac{q}{k} \rangle$. Mostraremos ejemplos de esto en breve.

Conexión con el Teorema de Lagrange

La afirmación (2) del Teorema Fundamental de los Grupos Cíclicos Finitos se cumple para cualquier grupo finito $G$, incluso si $G$ no es cíclico. Este resultado general se conoce como el Teorema de Lagrange.

Por brevedad, llamaremos a esto el Teorema Fundamental de los Grupos Cíclicos, en el entendido de que estamos tratando con grupos finitos.

Ejemplos de Uso del Teorema Fundamental de los Grupos Cíclicos

Usemos $G = \{1,2,3,4,5,6\}$ bajo la multiplicación módulo 7 como nuestro grupo cíclico. Ya hemos demostrado que $g = 3$ genera todo el grupo.

El subgrupo de orden 1

Usando el Teorema Fundamental de los Grupos Cíclicos, sabemos que $G$ tiene un subgrupo de orden 1, ya que 1 divide a 6. Ahora encontremos un generador para este subgrupo. Dado que $k = 1$, tenemos $3^{\frac{6}{1}} \equiv 1\pmod{7}$. El elemento identidad $1$ es claramente un generador del subgrupo de tamaño uno.

El subgrupo de orden 2

Ahora encontremos el subgrupo de tamaño 2. Sabemos que existe porque 2 divide a 6. Aquí, tenemos $g = 3$, $q = 6$, y $k = 2$. Reemplazando en la fórmula, obtenemos $g^{\frac{q}{k}} = 3^{\frac{6}{2}} = 3^3 \equiv 6\mod{7}$. El elemento $6$ genera el subgrupo de orden 2 con elementos $\{1, 6\}$.

El subgrupo de orden 3

Como 3 divide a 6, existe un subgrupo de orden 3. Además, el elemento $3^{\frac{q}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2\pmod{7}$ es un generador para este subgrupo, $\langle 2\rangle = \{2^0, 2^1, 2^2\} =\{1, 2, 4\}.$

El subgrupo de orden 4, 5

No hay subgrupos de orden 4 y 5 porque estos números no dividen a 6.

El subgrupo de orden 6

Como 6 divide a 6, existe un subgrupo de orden 6. Además, $3^{\frac{q}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3$ es un generador de este subgrupo:

Ejercicio: Considera el grupo con elementos $G = \{1,2,3,4,5,6,7,8,9,10\}$ bajo la multiplicación módulo 11.

1. Encuentra un generador para este grupo.
2. El grupo tiene un subgrupo de orden 5, ya que 5 divide el orden de $G$, que es 10. Encuentra un generador para este subgrupo y calcula el subgrupo que genera.

Subgrupo Multiplicativo de Orden $k$ en un Campo Finito

Podemos encontrar subgrupos multiplicativos de un orden específico en un campo finito. Primero, veamos la definición de los campos finitos:

Por definición, un campo $(\mathbb{F}, + , *)$ consiste de dos grupos abelianos (los operadores binarios son conmutativos):

1. Grupo aditivo: $(\mathbb{F}, +)$, el cual es abeliano y finito en un campo finito.
2. Grupo multiplicativo: $(\mathbb{F^*}, *)$ (donde $\mathbb{F}^* = \mathbb{F}\setminus\{0\}$), el cual también es abeliano y finito en un campo finito.

Ten en cuenta que $\mathbb{F}_q$ denota un campo con $q$ elementos, mientras que $\mathbb{F}^*_q$ (el grupo multiplicativo de $\mathbb{F}_q$) tiene $q-1$ elementos.

En el siguiente teorema, vemos que todo campo finito necesariamente contiene un subgrupo multiplicativo de orden $q - 1$ (omitiendo el $0$).

Teorema 1: El Grupo Multiplicativo $\mathbb{F}^*_q$ es Cíclico de Orden $q-1$.

Si $\mathbb{F}_q$ es un campo finito con orden $q$, entonces su grupo multiplicativo $\mathbb{F}^*_q$ es cíclico de orden $q-1$.

El hecho de que $\mathbb{F}^*_q$ forma un grupo de orden $q-1$ se deduce directamente de la definición de un campo finito.

Dado que probar la ciclicidad del grupo multiplicativo nos llevaría más allá del alcance de este artículo, lo tomaremos como un hecho dado.

Un grupo cíclico tiene un generador, por lo tanto sabemos que existe algún $g\in \mathbb{F}^*_q$ tal que

Elementos Primitivos en un Campo Finito (Generadores)

En la teoría de campos, un elemento primitivo de un campo finito $\mathbb{F}_q$ es un generador del grupo multiplicativo del campo. El elemento $g$ en el Teorema 1 es un elemento primitivo en $\mathbb{F}_q$.

El siguiente código en Python utiliza la biblioteca galois para identificar los elementos primitivos (generadores) en $\mathbb{F}_7$.

Copy
import galois

GF = galois.GF(7)

primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]

# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Ejercicio: Usa Python para encontrar todos los elementos primitivos del grupo multiplicativo del campo $\mathbb{F}_{11}$.

Corolario 1: Prueba de Subgrupo de Orden $k$ — Existencia a través de Divisores en un Campo Finito

Un corolario útil es que podemos verificar rápidamente si un subgrupo de un cierto tamaño existe o no, al enumerar todos los divisores de $q-1$. Por ejemplo, considera el campo $\mathbb{F}_{41}$, que tiene un grupo multiplicativo $\mathbb{F}_{41}^*$ con orden 40. Podemos verificar rápidamente que $\mathbb{F}_{41}^*$ tiene un subgrupo de tamaño 8 porque 8 divide a 40.

Como otro ejemplo, considera el campo $\mathbb{F}_{17}$, cuyo grupo multiplicativo $\mathbb{F}_{17}^*$ tiene un orden de 16. Dado que 8 divide a 16, $\mathbb{F}_{17}^*$ tiene un subgrupo de tamaño 8. De manera similar, tiene un subgrupo de tamaño 4, porque 4 divide a 16, y, como podrías adivinar, $\mathbb{F}_{17}$ también tiene un subgrupo de tamaño 2.

Para encontrar un generador para un subgrupo multiplicativo de un tamaño dado, podemos utilizar la afirmación (3) del Teorema Fundamental anterior. El tamaño de $\mathbb{F}_{q}^*$ es $q-1$, así que si tenemos un elemento primitivo $g$ y queremos un subgrupo multiplicativo de orden $k$, podemos calcular $g^\frac{q-1}{k}$ para cualquier elemento primitivo $g$.

Ejemplo Todo en Uno

Considera el campo finito $\mathbb{F}_{17} =\{0, 1, 2, \dots, 16\}$. Para un $k$ dado, queremos encontrar un subgrupo multiplicativo de orden $k$ en $\mathbb{F}_{17}$ utilizando el Teorema Fundamental de los Grupos Cíclicos Finitos.

Ya que el subgrupo multiplicativo $\mathbb{F}_{17}^*$ tiene orden $q-1=17-1=16$, sabemos por la afirmación (2) del Teorema Fundamental de los Grupos Cíclicos que tiene subgrupos de órdenes 1, 2, 4, 8 y 16, siendo el último el grupo mismo.

Estos subgrupos son cíclicos, por lo que cada uno tiene al menos un generador. Por la afirmación (3) del teorema, sabemos que un generador para cada subgrupo está dado por $g^\frac{q-1}{k}$, donde $g$ es un generador de todo el grupo multiplicativo y $k$ es el tamaño de nuestro subgrupo deseado.

Por lo tanto, para generar los subgrupos, el primer paso es encontrar un generador de $\mathbb{F}_{17}^*$, que es un elemento primitivo de $\mathbb{F}_{17}$.

El generador de $\mathbb{F}^*_{17}$

Recuerda del Teorema 1 que $\mathbb{F}^*_{17}$ es un grupo cíclico. Para demostrar que $\mathbb{F}^*_{17}$ puede ser generado por el elemento $3$, podemos calcular todas las potencias de $3$ de la siguiente manera:

¿Qué hay de $3^{17}$?

Puedes ver que para todo $i \ge 17$, el elemento $3^i$ es igual a uno de los de $3^0, 3^1, 3^2, \dots, 3^{16}$. También puedes ver que cada valor en {1,2,…,16} aparece en algún lugar de la lista de potencias de 3. Entonces, $\langle 3 \rangle = \{1, 2, \dots, 16\} = \mathbb{F}^*_{17}$.

Este generador se puede encontrar en código Python con galois.primitive_elements.

Copy
import galois

GF = galois.GF(17)

primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Encontrando el subgrupo de orden $k$ en $\mathbb{F}^*_{17}$

Supongamos que queremos determinar si existe un subgrupo multiplicativo de orden $k=4$ en el campo finito $\mathbb{F}_q = \mathbb{F}_{17}$. Ten en cuenta que el grupo multiplicativo de $\mathbb{F}_q$ tiene tamaño $q-1$. Para $\mathbb{F}_{17}$, el grupo multiplicativo $\mathbb{F}_{17}^*$ tiene $q-1 = 17-1 = 16$ elementos.

Recuerda por el Teorema Fundamental de los Grupos Cíclicos Finitos que dado que $k$ divide a $q-1$ (explícitamente, $4$ divide a 16), entonces $g^{\frac{q-1}{k}}$ es un generador y $\langle g^{\frac{q-1}{k}}\rangle$ es un subgrupo de tamaño 4.

Por lo tanto, 13 es un generador para el subgrupo de tamaño 4 en $\mathbb{F}^*_{17}$ y

Explícitamente, $\{1, 13, 16, 4\}$ es el subgrupo.

Ejercicio: Calcula los subgrupos multiplicativos de orden $2$ y $8$.

Resumen

• El objetivo es encontrar los subgrupos multiplicativos de tamaño $k$ en el campo $\mathbb{F}_q$.
• Si $G = \langle g\rangle = \{g^i: i\in\mathbb{Z}\}$, entonces $G$ es un grupo cíclico, y $g$ es un generador de $G$.
• Si $\mathbb{F}_q$ es un campo finito de orden $q$, entonces $(\mathbb{F}^*_q, .)$ es un grupo cíclico de orden $q-1$.
• El Teorema Fundamental de los Grupos Cíclicos establece que el campo finito $\mathbb{F}_q$ tiene un subgrupo de tamaño $k$ si y solo si $k$ divide a $q-1$. Además, un generador de este subgrupo es $g^{\frac{q-1}{k}}$, donde $g$ es un generador del grupo multiplicativo $\mathbb{F}^*_q$.

Apéndice

Verificaremos las tres condiciones necesarias para que $\langle g \rangle$ sea un subgrupo de $G$.

Identidad: Dado que $1 = g^0$, entonces $1 \in \langle g \rangle$.

Clausura: Supongamos que $a, b \in \langle g \rangle$. Entonces sabemos que $a = g^n$ y $b = g^m$ para algunos $n, m$. Aplicar la operación de grupo da

Dado que $n+m\in\mathbb{Z}$, por lo tanto $ab\in \langle g \rangle$.

Inverso: Supongamos que $a\in \langle g \rangle$. Entonces $a = g^m$ para algún $m$,

Dado que $-m\in\mathbb{Z}$, entonces $a^{-1} \in \langle g \rangle$.

Ejercicios

¿Cuáles son todos los órdenes de los subgrupos multiplicativos de $\mathbb{F}_{31}$ y un generador para cada subgrupo?

¿Cuáles son todos los órdenes de los subgrupos multiplicativos de $\mathbb{F}_{5}$ y un generador para cada subgrupo?

¿Cuáles son todos los órdenes de los subgrupos multiplicativos de $\mathbb{F}_{51}$ y un generador para cada subgrupo?