Clase del 30 de septiembre (1 hora)
En la clase de hoy hemos probado el Teorema de Lagrange, que afirma que, dado un grupo finito $G$ y un subgrupo $H$ de $G$, el orden de $G$ es igual al producto del orden de $H$ por su índice. Como consecuencia directa de este resultado se infiere que el orden de cualquier subgrupo de un grupo finito $G$ tiene que ser un divisor de $|G|$. También, dado un elemento $g\in G$, como $o(g)$ coincide con el orden del subgrupo generado por $g$, $\langle g \rangle$, se tiene como consecuencia que $o(g)$ es un divisor de $|G|$.
Hemos demostrado, como corolario del Teorema de Lagrange, la propiedad de “transitividad de índices” y también la fórmula que permite calcular el “cardinal” de $HK$, cuando $H$ y $K$ son sobgrupos de un grupo finito $G$.
Hay que tener en cuenta aquí que $HK$ no es necesariamente un subgrupo de $G$ (hemos visto un ejemplo de ello). Más adelante veremos un resultado que caracterizará aquellas situaciones en las que el producto de dos subgrupos es un subgrupo.
En la siguiente clase probaremos otras consecuencias del Teorema de Lagrange y, posteriormente, nos plantearemos la siguiente cuestión: dado un grupo $G$ y un subgrupo $H$ de $G$, ¿cuándo el conjunto de sus clases a derecha, $\{Hx\mid x\in G\}$, tiene estructura de grupo? Veremos que esto ocurre cuando $H$ pertenece a una clase muy importante de subgrupos: los subgrupos normales.
Clase del 26 de septiembre (2 horas)
Hemos comenzado la clase recordando un importante teorema que nos indica cuál es la estructura de los grupos cíclicos finitos. En particular, un grupo cíclico finito tiene un único subgrupo de orden $k$ para cada divisor $k$ del orden del grupo (y estos son exactamente sus subgrupos). Hemos visto, como ejemplo, todos los subgrupos de $\mathbb{Z}_6$; aquí lo “engorroso” es pasar de notación multiplicativa a notación aditiva, pero resulta muy fácil si se va con un poco de cuidado.
Hemos comenzado la sección sobre el Teorema de Lagrange. Hemos comenzado con un lema técnico, de demostración muy sencilla, pero que nos va a facilitar bastante la escritura de las demostraciones.
Después hemos definido el concepto de clases a derecha y a izquierda de un elemento módulo un subgrupo $H$ de un grupo $G$. Hemos visto que el conjunto de las clases a derecha forman una partición del grupo (análogamente con las clases a izquierda). También hemos visto que el cardinal del conjunto de las clases a izquierda coincide con el de las clases a derecha estableciendo una biyección entre ambos conjuntos. Esta biyección asigna, a cada clase a izquierda $xH$, la clase a derecha $Hx^{-1}$.
Si el conjunto de clases a izquierda (o a derecha) de un grupo $G$ módulo un subgrupo $H$ es finito, hemos definido el “índice de $H$ en $G$”, o “índice según $G$ de $H$”, como el número de tales clases. Se denota por $|G:H|$.
El objetivo del próximo lunes será enunciar y probar el Teorema de Lagrange, así como algunas consecuencias importantes. El Teorema de Lagrange afirma que, si $G$ es un grupo finito y $H$ es un subgrupo suyo entonces $$|G|=|H||G:H|.$$ En particular, el orden de todo subgrupo de $G$ debe ser necesariamente un divisor del orden de $G$. Por ejemplo, un grupo de orden $15$ puede tener subgrupos de ordenes $1$, $3$, $5$ y $15$, pero no puede tener subgrupos de orden $4$.
Con el objetivo de clarificar el concepto de clase a izquierda y a derecha módulo un subgrupo, vamos a incluir aquí un ejemplo (no mencionado en clase). Supongamos que $G$ es el grupo cuaternio de orden 8, $Q_8$, es decir, $$G=\{1, -1, i, -i-, j, -j, k, -k\}.$$
Vamos a considerar el subgrupo de $G$ generado por $i$, es decir, el subgrupo cíclico $$H:=\langle i \rangle.$$ Recordad que $i^2=-1$, $i^3=-i$ y $i^4=1$. Por tanto, $i$ es un elemento de orden 4. Así pues, por el teorema de estructura de los grupos cíclicos, se tiene que $$H=\{1,i,-1,-i\}.$$
Se trata, por tanto, de un subgrupo de orden 4. Aunque no lo hemos probado todavía, vamos a aplicar aquí el Teorema de Lagrange para conocer su índice en $G$. Por este teorema: $$|G|=|H||G:H|,$$
es decir: $8=4\cdot |G:H|$. Así pues, el índice de $H$ en $G$, $|G:H|$, es igual a 2. Esto significa que existen 2 clases a izquierda de $G$ módulo $H$ (y dos clases a derecha también). Veamos cuáles son las clases a izquierda. Sabemos que forman una PARTICIÓN de $G$. Una de las clases es, por supuesto, la clase del neutro (del $1$), que es $1H=H$. Por tanto, ya tenemos una clase: $$H=\{1, i, -1, -i\}.$$
Escojamos ahora un elemento que no esté en esta clase, como por ejemplo $j$, y calculemos la clase de $j$: $$jH=\{jh\mid h\in H\}=\{j\cdot 1, j \cdot i, j\cdot (-1), j\cdot (-i)\}=\{j, -k, -j,k\}.$$
Como, tal y como hemos visto, solo hay dos clases a izquierda (pues el índice era 2), ya las tenemos todas. Son las siguientes: $$H=\{1, i, -1, -i\}\;\;\mbox{ y }\;\;\; jH=\{j, -k, -j,k\}.$$
Obsérvese que, tal y como hemos mencionado en clase, se trata de clases de equivalencia. Las clases de $1, i, -1$ y $-i$ coinciden y son iguales a $H$, es decir, $$1H=iH=(-1)H=(-i)H=H.$$ También, las clases de $j$, $-k$, $-j$ y $k$ coinciden, es decir, $$jH=(-k)H=(-j)H=kH.$$
Obsérvese que el conjunto de las clases a izquierda de $G=Q_8$ módulo $H$, $\{H, jH\}$, constituye una partición de $G$.
Veamos ahora otro ejemplo. Sigamos con el mismo grupo $G=Q_8$ y consideremos el subgrupo $N$ generado por $-1$, es decir, $N:=\langle -1\rangle=\{1, -1\}$ (observad que $-1$ tiene orden 2 y, por tanto, $N$ posee solo dos elementos: $(-1)^0=1$ y $(-1)^1=-1$). Vamos a calcular, igual que antes, el índice de $N$ en $G$, usando el Teorema de Lagrange: $$|G|=|N||G:N|.$$
Por tanto: $8=2\cdot |G:N|$. Luego $|G:N|=4$. Así pues, existen 4 clases a izquierda de $G$ módulo $N$. Veamos cuáles son:
- Tenemos la clase del $1$, es decir, $1N=N=\{1, -1\}$.
- Elegimos un elemento que no esté en la clase anterior; por ejemplo, $i$. Calculemos la clase de $i$: $$iN=\{in\mid n\in N\}=\{i\cdot 1, i\cdot (-1)\}=\{i, -i\}.$$
- Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $j$. Calculemos la clase de $j$: $$jN=\{jn\mid n\in N\}=\{j, -j\}.$$
- Elegimos un elemento de $G$ que no esté en ninguna de las clases anteriores; por ejemplo, $k$. Calculemos la clase de $k$: $$kN=\{kn\mid n\in N\}=\{k, -k\}.$$
Ya tenemos las 4 clases. Observamos que el conjunto de estas cuatro clases a izquierda forman una partición de $G$.
Si reproducís los cálculos anteriores para clases a derecha, observaréis que la clase a izquierda y a derecha módulo $H$ de cualquier elemento $x$ de $G$ coinciden (y lo mismo pasa con las clases módulo $N$), a pesar de que el grupo $G$ no es abeliano. ¡Ojo! Esto no pasa siempre. Cuando esto pasa (es decir, cuando las clases a izquierda y a derecha módulo un subgrupo coinciden) se dice que ese subgrupo es normal (y $Q_8$ tiene la peculiaridad de que todos sus subgrupos son normales, a pesar de no ser un grupo abeliano). Este concepto de subgrupo normal es muy importante y lo estudiaremos en la sección siguiente.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 6)
¿Dónde radica la seguridad del criptosistema RSA?
Conocer la aplicación de descifrado $D$ equivale a conocer la clave privada $d$, que sólo posee Bob. Y esta clave secreta $d$ no puede conocerse a partir de $(n, e)$ sin el conocimiento de $r=\varphi(n)=(p-1)(p-1)$ (recuérdese que $d$ es un representante del inverso de la clase de $e$ módulo $r=(p-1)(q-1))$. Puede razonarse que conocer $r$ es igual de difícil que saber factorizar $n$ como producto de los primos $p$ y $q$. Si estos primos se han elegido suficientemente grandes (y satisfaciendo ciertas condiciones buenas), $n$ tendrá un valor tan grande que será imposible factorizarlo con los recursos computacionales existentes en este momento. Aquí radica la seguridad del criptosistema RSA. Si una supuesta espía Eve interceptara el mensaje que Alice le envía a Bob, le resultaría imposible averiguar la clave secreta $d$ (y, por tanto, descifrar el mensaje) aún sabiendo la clave pública $(n,e)$.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 5)
Para probar que el proceso de descifrado anteriormente descrito es correcto, hay que demostrar que las aplicaciones de cifrado, C, y descifrado, D, son inversas una de la otra, es decir, $C\circ D=D\circ C=Id$, donde $Id: \mathbb{Z}_n\rightarrow \mathbb{Z}_n$ es la aplicación identidad. Como, para todo $\overline{x}\in \mathbb{Z}_n$, $C(D(\overline{x}))=D(C(\overline{x}))=\overline{x}^{ed}$, es suficiente demostrar que $$x^{ed}\equiv x\; ({\rm mod}\; n)\;\mbox{para todo $x\in \mathbb{Z}$}.$$
Sea $x$ un entero arbitrario. Si $x$ es divisible por $n$ entonces la congruencia anterior es obvia. Por tanto, podemos asumir que $x$ no es divisible por $n$. Como $ed\equiv 1\; ({\rm mod}\; r)$, existe un entero $\lambda$ tal que $ed=1+\lambda r$. Luego $x^{ed}=x (x^r)^{\lambda}$.
Vamos a distinguir dos casos:
Caso 1: $x$ y $n$ son coprimos. En este caso, la clase $\overline{x}\in \mathbb{Z}_n$ tiene inverso multiplicativo en $\mathbb{Z}$ (por la Proposición 1.9 de los apuntes, que veremos). Además, en la Sección 1.10 del Capítulo 1, veremos también que el conjunto $U_n$ formado por los elementos de $\mathbb{Z}_n$ que tienen inverso multiplicativo es un grupo (con el producto) cuyo orden es $\varphi(n)=r$ (la función de Euler de $n$). Como $\overline{x}\in U_n$, por un corolario del Teorema de Lagrange (que veremos, previsiblemente, en la clase del jueves) el orden de $\overline{x}$ en $U_n$ es un divisor de $r=\varphi(n)$ y, por tanto: $\overline{x}^{r}=\overline{1}$, es decir, $x^{r}\equiv 1\; ({\rm mod}\; n)$. Así pues, $$x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; n).$$
Caso 2: $x$ y $n$ no son coprimos. En este caso, como $n=p q$, $x$ ha de ser divisible por uno de los dos primos $p$ y $q$, pero no por ambos (al no ser $n$ divisor de $x$). Supongamos, sin pérdida de generalidad, que $p$ divide a $x$ (se razonaría igual si $q$ divide a $x$) y, por tanto, $q$ es coprimo con $x$. Como consecuencia de esto último, la clase de $x$ en $\mathbb{Z}_q$ (que vamos a denotar también por $\overline{x}$; ¡que el abuso notacional no te confunda, por favor!) tiene inverso multiplicativo, luego pertenece a $U_{q}$. Como el grupo $U_q$ tiene orden $\varphi(q)=q-1$, razonando igual que antes se tiene que el orden de $\overline{x}$ en $U_q$ es un divisor de $q-1$ y, por tanto, $\overline{x}^{q-1}=\overline{1}$ en $\mathbb{Z_q}$. Luego $\overline{x}^r=(\overline{x}^{q-1})^{p-1}=\overline{1}$ en $\mathbb{Z}_q$. Por tanto, $x^{ed}=x (x^r)^{\lambda}\equiv x\; ({\rm mod}\; q)$, es decir, $x^{ed}-x$ es un múltiplo de $q$.
Por otro lado (continuando dentro del Caso 2), como $p$ divide a $x$ se cumple, obviamente, que $x^{ed}\equiv 0 \equiv x\; ({\rm mod}\; p)$, es decir, $x^{ed}-x$ es un múltiplo de $p$.
Así, hemos demostrado que $x^{ed}-x$ es, a la vez, múltiplo de $p$ y de $q$. Luego es múltiplo de $n=p q$, es decir, $$x^{ed}\equiv x\; ({\rm mod}\; n).$$
Con esto, acabamos de demostrar que las aplicaciones $C$ y $D$ son inversas una de la otra.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 4)
Vamos a diseñar ahora una «función de cifrado», es decir, una función $$C:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si $\overline{m}$ es el mensaje que Alice quiere cifrar (recordad que Alice ha «preparado» el mensaje para transformarlo en una clase de congruencia módulo $n$), el resultado del cifrado será la imagen de $\overline{m}$ por esta función, es decir, $C(\overline{m})$. Este será el valor que Alice enviará a Bob.
La función de cifrado se define de la siguiente manera: $$C(\overline{x}):=\overline{x}^e$$ para todo $\overline{x}\in \mathbb{Z}_n$ (¡OJO! Aquí la «barrita» superior significa «clase módulo $n$»). Dicho de otro modo, para cifrar el mensaje $\overline{m}$, Alice calculará la clase de $\mathbb{Z}_n$ consistente en multiplicar la clase $\overline{m}$ consigo misma $e$ veces (con el producto en $\mathbb{Z}_n$, claro está).
Por ejemplo, consideremos las claves del anterior ejemplo e imaginemos que el mensaje que quiere cifrar Alice es $\overline{m}=\overline{12423}\in \mathbb{Z}_{25877}$. Entonces se tiene que $$C(\overline{m})=\overline{12423}^{e}=\overline{12423}^{1321}=\overline{14946}\in \mathbb{Z}_{25877}.$$ Este es el mensaje que Alice envía a Bob.
Vamos a diseñar ahora una «función de descifrado», es decir, una función $$D:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$$ tal que, si Bob aplica esta función al mensaje $C(\overline{m})$ que le ha enviado Alice, obtiene el mensaje original $\overline{m}$. Dicho de otro modo, tal que $D(C(\overline{m}))=\overline{m}$. Un poco de reflexión nos hará concluir que, lo que queremos es que $C$ sea una función biyectiva y $D$ sea su inversa.
Esta función de descifrado $D$ se define de la siguiente manera: $$D(\overline{x}):=\overline{x}^d$$ para todo $\overline{x}\in \mathbb{Z}_n$.
En el caso de nuestro ejemplo, si aplicáis esta función de descifrado $D$ a $C(\overline{m})=\overline{14946}$ obtendréis $$D(C(\overline{m}))=D(\overline{14946})=\overline{14946}^{d}=\overline{14946}^{17881}=\overline{m}.$$
¿Por qué esto funciona? ¿Cómo se justifica? Lo veremos en el siguiente post.
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 3)
Ya hemos visto que la clave pública del criptosistema RSA consiste en un par $(n,e)$, donde $n$ es el producto de dos primos muy grandes, $p$ y $q$, y $e$ es un entero entre $1$ y $r-1$ coprimo con $r$, donde $r=\varphi(n)=\varphi(p q)=(p-1)(q-1)$. Veamos ahora cómo Bob determina una clave privada (que sólo conocerá él).
Consideramos la clase de $e$ en el conjunto de clases de congruencia módulo $r$, $\mathbb{Z}_r$ (recuérdese que $e$ es un entero entre $1$ y $r-1$; por tanto, se trata de una clase distinta de la del cero). Como es habitual, denotemos por $\overline{e}$ a esta clase. Consderamos ahora la operación producto en $\mathbb{Z}_r$. Como ya sabéis, no todo elemento de $\mathbb{Z}_r\setminus \{\overline{0}\}$ tiene inverso multiplicativo (es decir, no para toda clase $\overline{x}\neq \overline{0}$ existe otra clase $\overline{x}^{-1}$ tal que $\overline{x}\cdot \overline{x}=\overline{1}$). Pero, ¿cuáles son las clases de $\mathbb{Z}_r\setminus \{\overline{0}\}$ que tienen inverso multiplicativo? La respuesta la tenéis en la Proposición 1.9 de los apuntes (que veremos más adelante): tienen inverso exactamente aquellas clases $\overline{k}$, con $1\leq k\leq r-1$, tales que $k$ y $r$ son coprimos. Revisad ahora las condiciones que satisface $e$: ¡son exactamente estas! Por tanto, la clase de $e$ en $\mathbb{Z}_n$, $\overline{e}$, tiene inverso multiplicativo. Luego existe un entero $d$ tal que $1<d<r-1$ y $\overline{d}=\overline{e}^{-1}$ en $\mathbb{Z}_r$. Dicho de otro modo, $$ed\equiv 1\;({\rm mod}\; r).$$
Este entero $d$ es la clave privada de Bob.
Ahora repasemos:
- Para generar una clave pública, Bob elige dos primos muy grandes $p$ y $q$ y considera su producto $n=p q$. Después calcula $r:=\varphi(n)=(p-1)(q-1)$ y elige un entero $e$ tal que $1\leq e\leq r-1$ y ${\rm mcd}(e,r)=1$. La clave pública es el par $(n,e)$.
- Para generar una clave privada, Bob calcula el entero $d$ tal que $1\leq d\leq r-1$ y tal que su clase en $\mathbb{Z}_r$ sea el inverso multiplicativo de la clase de $e$, es decir, tal que $ed\equiv 1\;({\rm mod}\;r)$. La clave privada es este entero $d$.
En nuestro ejemplo «de juguete» anterior (recordad: $n=113\cdot 229=25877$ y $e=1321$), Bob podría tomar como clave privada $d:=17881$ (podéis verificar que la clase de $d$ es el inverso multiplicativo de la clase de $e$ módulo $r$).
La siguiente pregunta es: ¿cómo usará Alice la clave pública $(n,e)$ para cifrar mensajes, y cómo usará Bob su clave privada $d$ para descifrarlos?
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 2)
Recordemos que tenemos a Alice y a Bob, y que Alice quiere enviar un mensaje encriptado a Bob (usando una clave pública) para que Bob lo descifre (usando SU clave privada). Para ello, Bob considera dos números primos muy grandes $p$ y $q$ y los multiplica, formando un entero muy grande $n:=pq$. Este valor $n$ es conocido por Alice y por cualquier persona que quiera y/o pueda conocerlo (¡Ojo! el valor $n$ es público, pero NO lo son los factores $p$ y $q$), y forma parte de la clave pública necesaria para cifrar mensajes para enviar a Bob. Como más adelante recordaremos, la seguridad del sistema radica en que es computacionalmente muy difícil averiguar los factores primos $p$ y $q$ a partir de $n$ si éstos son muy grandes.
Veamos ahora cómo calcular la segunda parte de la clave pública. Para esto Bob (que es el único conocedor de los primos $p$ y $q$) calcula el siguiente valor: $$r:=\varphi(n)=(p-1)(q-1),$$ es decir, la función de Euler de $n$. Para él es muy fácil de calcular pues, como $n$ es el producto de dos primos $p$ y $q$, y ÉL CONOCE ESTOS PRIMOS, por una propiedad de la función de Euler sabe que $\varphi(n)=(p-1)(q-1)$ (véase https://es.wikipedia.org/wiki/Función_φ_de_Euler). Puede razonarse que la dificultad de calcular $r$ a partir únicamente de $n$ (que es muy grande) es similar a la dificultad de obtener los primos $p$ y $q$ sólo a partir de $n$. Una vez calculado este valor $r$, Bob elige arbitrariamente un número entero $e$ tal que $0<e<r$ y tal que ${\rm mcd}(e,r)=1$. El par formado por $(n,e)$ constituye la clave pública completa, y es la información que Bob da a conocer a Alice (y a quien quiera saberla) para que ésta pueda encriptar el mensaje que quiere transmitir a Bob.
Vamos a ver un ejemplo nada realista (con números primos «de risa») para que se entienda bien. Bob podría elegir los primos $p=113$ y $q=229$. El valor $n$ es igual a $113\cdot 229=25877$, y el valor $r$ es igual a $\varphi(113\cdot 229)=112\cdot 228=25536$. Bob elige como $e$ el valor $1321$ (que está entre $1$ y $r-1$ y es coprimo con $r$).
La clave pública sería el par $$(n=25877, e=1321).$$
Aplicaciones del álgebra a la criptografía: el criptosistema RSA (parte 1).
El sistema criptográfico RSA debe su nombre a sus inventores, Ronald Rivest, Adi Shamir y Leonard Adleman, que publicaron por primera vez el método en 1977. Se trata uno de los criptosistemas más utilizados hoy en día, presente como método de seguridad en transacciones bancarias, firma digital, etc. Permite intercambiar información de forma segura entre varios participantes. Cada participante tiene dos claves: una clave privada, que utiliza para descifrar los mensajes que recibe, y una clave pública, que utilizan los demás participantes cuando desean cifrar un mensaje dirigido a él. Estas dos claves son inversas entre sí, pero debe ser computacionalmente imposible deducir la clave privada a partir de la pública (y en eso radica la seguridad del sistema).
Vamos a considerar dos personajes, Alice y Bob. Alice quiere enviar un mensaje encriptado a Bob. Para ello, Bob debe generar una clave pública para comunicársela a Alice (y a cualquiera que quiera conocerla, pues no es secreta). Esta clave la utilizará Alice para encriptar el mensaje que quiere enviar a Bob. Para generar una clave pública, deben considerarse dos números primos $p$ y $q$ muy grandes (y con ciertas condiciones) y multiplicarlos. Su producto, $n:=pq$, constituye una parte de la clave pública del criptosistema (que todo el mundo conoce, o puede conocer).
Para poder aplicar toda la “maquinaria algebraica” que necesitamos, Alice transforma su mensaje en un elemento del conjunto de las clases de congruencia módulo $n$, $\mathbb{Z}_n$ (o lo divide en varios “submensajes” y transforma cada uno de ellos de esta manera); hay varias maneras de hacer esto, pero no vamos a entrar aquí en semejante disquisición. Por lo que a nosotros respecta, el mensaje se “prepara” de manera que se transforma en un elemento de $\mathbb{Z}_n$ (o en varios de ellos, si se parte en varios submensajes).
¿Cómo se genera la parte que falta de la clave pública? ¿Cómo genera Bob una clave privada? ¿Cómo se encripta un mensaje? ¿Cómo se descifra? ¿Por qué el método es seguro? Aquí entran en juego conceptos algebraicos que veremos en este curso. En próximos posts revelaremos el modo :).
Clase del 23 de septiembre (1 hora)
Hoy hemos demostrado, en primer lugar, que los subgrupos de $\mathbb{Z}$ son exactamente los de la forma $n\mathbb{Z}$, con $n\in \mathbb{Z}$.
También hemos probado un importante teorema sobre la estructura de un grupo cíclico finito. Afirma lo siguiente: si $G$ es un grupo cíclico finito generado por un cierto elemento $g$ de orden $n$ entonces el orden del grupo coincide con el orden del generador ($n$) y los elementos de $G$ son exactamente las $n$ primeras potencias de $g$ de exponente no negativo: $1=g^0, g=g^1, g^2,\ldots, g^{n-1}$. Además, para cada divisor $k$ de $|G|=n$, $G$ tiene un único subgrupo de orden $k$ (que está generado por $g^{n/k}$). Como consecuencia del Teorema de Lagrange (que veremos próximamente), el orden de cualquier subgrupo de un grupo finito debe ser un divisor del orden del grupo. Por tanto, los subgrupos anteriormente considerados son todos los subgrupos de $G$.
También hemos visto, como corolario, que si $G=\langle g \rangle$ es un grupo cíclico de orden $n$ entonces los conjuntos de generadores de $G$ de cardinal $1$ son los de la forma $\{g^m\}$, siendo $m$ coprimo con $n$. Dicho de otro modo: $G=\langle g^m\rangle$ si y sólo si ${\rm mcd}(n,m)=1$. Por tanto, el número de generadores de cardinal 1 de $G$ es $\varphi(n)$, es decir, la función de Euler de $n$.
Por ejemplo, si $G=\langle g \rangle$ es un grupo cíclico de orden $10$ entonces sus elementos son $\{1, g, g^2,\ldots, g^9\}$ y, además, $G$ tiene $\varphi(10)=4$ sistemas de generadores de cardinal 1, que son $\{g\}$, $\{g^3\}$, $\{g^7\}$ y $\{g^9\}$. Dicho de otro modo: $$G=\langle g \rangle=\langle g^3 \rangle= \langle g^7 \rangle=\langle g^9\rangle.$$
Planteo la siguiente pregunta: ¿cuáles son los sistemas de generadores de cardinal 1 de $\mathbb{Z}$?
Finalmente hemos demostrado que un grupo finito $G$ es cíclico si y sólo si posee un elemento de orden $|G|$.
Sobre las prácticas de laboratorio
Estimadas/os estudiantes de Estructuras Algebraicas I, escribo esta entrada para comentaros algunas cosas:
– En primer lugar, recordaros que los próximos lunes y jueves comienzan las prácticas de laboratorio de la asignatura, de 19:15 a 21:15. El primer grupo en comenzar es el A4, y las prácticas se realizarán en el Aula de Informática VIII.
– He añadido a PoliformaT el boletín de las prácticas. Se trata de un documento general (no de un boletín por práctica), sobre el cual iremos avanzando a lo largo del curso.
– Como ya os comenté el primer día de clase, es preceptivo que forméis grupos (o más bien subsubgrupos 😊 ) de 4 personas del mismo subgrupo (A1, A2, A3 o A4). Como no todos los subgrupos tienen a un múltiplo de 4 como cardinal, se admitirán grupos EXTRAORDINARIOS de 2,3 ó 5 personas. Cada grupo tendrá un representante (que será el que suba las soluciones de los problemas, que tendréis que resolver en grupo, a la correspondiente tarea en PoliformaT). Por favor, realizad la distribución en grupos vosotros mismos y que cada uno de los representantes me envíe un email (a framonde@mat.upv.es) con el nombre de todos los integrantes del grupo (indicando el nombre del representante). Yo mismo me encargaré de reenviar la información a Víctor, el profesor que impartirá las prácticas de laboratorio a los subgrupos A1 y A2.
– Al finalizar cada práctica, os propondremos 3 ó 4 problemas de la lista de problemas complementarios (al final del boletín) para que los resolváis en grupo y subáis las soluciones en un plazo de 3.5 días (aprox.). Al comenzar la práctica siguiente, saldréis vosotros (previo sorteo) a explicar vuestras soluciones.
– Con excepción de la primera práctica (y la última, que será el examen), cada sesión constará de dos partes: una primera en la que explicaréis las soluciones de los problemas propuestos al final de la práctica anterior, y una segunda en la que iremos avanzando en los contenidos del boletín de prácticas relacionados con GAP, y en los ejercicios.
– En la primera práctica, comenzaremos explicando la Sección 6 del boletín («Algunos resultados teóricos»). Aquí mostraremos algunos aspectos MUY IMPORTANTES relacionados con el grupo simétrico (que NO se explicarán en las sesiones de teoría) como son: descomposición de una permutación en producto de ciclos disjuntos dos a dos, descomposición de una permutación en producto de transposiciones (y conservación de la paridad del número de transposiciones involucradas), signatura de una permutación y propiedades, y el CÁLCULO DEL ORDEN DE UNA PERMUTACIÓN a partir de su descomposición como producto de ciclos disjuntos dos a dos. La explicación se basará, sobre todo, en ejemplos, aunque se realizarán algunas demostraciones (pocas y sencillas). Las demostraciones omitidas (así como ejemplos y ejercicios complementarios) las tenéis en la última sección del Capítulo 1 de los apuntes (éstas, las demostraciones omitidas, no irán para examen). Después explicaremos algunos aspectos muy básicos del programa GAP (Parte 1 del boletín) y comenzaremos a ver cómo trabajar con grupos de permutaciones usando GAP (a partir de la sección 7 del boletín).
– Aunque podéis usar los ordenadores del aula de informática, si alguien prefiere usar su portátil lo puede hacer. Eso sí: el examen de prácticas (última práctica) tendrá que realizarse necesariamente usando los ordenadores del aula.
El sistema de álgebra computacional GAP es libre y os lo podéis descargar para cualquier sistema operativo a través de la web siguiente: https://www.gap-system.org/install/
IMPORTANTE: usaremos GAP únicamente a modo de calculadora (aunque se trata de un sistema con lenguaje de programación propio y muchas funcionalidades, hemos de ir necesariamente al grano). Abrir ficheros con GAP y guardarlos resulta bastante farragoso y no vamos a perder el tiempo con esto. Por tanto, para ir apuntando las soluciones de los ejercicios con GAP que haremos en clase, os recomiendo tener abierto un procesador de textos (Word o cualquier otro) e ir tecleando las correspondientes explicaciones de las soluciones (y copiando las instrucciones de GAP utilizadas con «copy and paste»); alternativamente, también podéis usar papel y boli. Creedme que esto es lo más operativo :).
Por favor, antes de la primera práctica, instalaos GAP en vuestros ordenadores, leed un poco la Parte 1 del boletín (secciones 1,2,3,4 y 5) y practicad un poco con los ejemplos. No os tomará mucho tiempo y agilizará bastante la primera sesión de prácticas.
Un cordial saludo,
Paco.