Inicio » 2024 (Página 4)
Archivos anuales: 2024
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.
Algunas indicaciones para resolver el problema B-2
Os escribo a continuación algunas indicaciones para resolver el problema B-2 (del 10 de septiembre):
Para probar que la operación es asociativa, sugiero considerar los siguientes casos (que cubren todas las posibilidades), calcular, para cada uno de ellos, (x*y)*z y (x*y)*z, y comparar los resultados (deberían salir iguales):
- $x+y\geq 1$, $y+z\geq 1$ y $x+y+z-1\geq 1$.
- $x+y<1$, $y+z<1$, $x+y+z<1$.
- $x+y<1$, $y+z<1$, $x+y+z\geq 1$.
- $x+y<1$, $y+z\geq 1$ (obsérvese que esto obliga a que $x+y+z\geq 1$).
- $x+y\geq 1$, $y+z<1$ (obsérvese que esto obliga a que $x+y+z\geq 1$).
- $x+y\geq 1$, $y+z\geq 1$ y $x+y+z-1<1$.
El elmento neutro es $0$. Probadlo.
El elemento inverso de un elemento $x\in G$ es $1-x$. Probadlo.
Clase del 18 de septiembre (1 hora)
Hoy hemos corregido el problema número 10 de la hoja de problemas del Tema 1. También hemos definido el concepto de grupo cíclico. Lo recordamos: un grupo $G$ se dice que es cíclico si puede ser generado por un solo elemento, es decir, si existe un elemento $g\in G$ tal que $G=\langle g \rangle$. Dicho de otro modo, si $G$ es el conjunto de todas las potencias de $g$: $G=\{g^k\mid k\in \mathbb{Z}\}$. Hemos visto varios ejemplos de grupos cíclicos. Recordemos algunos:
- $(\mathbb{Z},+)$ es cíclico, ya que $\mathbb{Z}=\langle 1 \rangle$. En efecto, todo número entero puede expresarse como un producto de $1$’s y su “inverso” (que es $-1$, en este caso, y suele llamarse “opuesto” al usarse notación aditiva). Veamos porqué es así:
- Si $n=0$ entonces $0=0\cdot 1\in \langle 1 \rangle$ (sería el análogo a “1” elevado a “cero”, pero usando notación aditiva).
- Si $n>0$ entonces $n=1+1+\cdots 1$ ($n$ veces), es decir $n=n\; 1\in \langle 1 \rangle$ (sería el análogo a “1” elevado a “$n$”, pero usando notación aditiva).
- Si $n<0$ entonces $n=(-1)+(-1)+\cdots+(-1)$ ($-n$ veces), es decir, $n=(-n)(-1)\in \langle 1 \rangle$ (sería el análogo a tomar el “inverso de 1” elevado a “$-n$”, pero usando notación aditiva).
- $(\mathbb{Z}_n,+)$ también es cíclico, ya que está generado por la clase del $1$, es decir, $\mathbb{Z}_n=\langle \overline{1}\rangle$. En efecto, cualquier elemento de $\mathbb{Z}_n$ es de la forma $\overline{m}$, con $0\leq m\leq n-1$. Y está claro que $\overline{m}=\overline{1}+\cdots+\overline{1}$ ($m$ veces), o expresado de otro modo, $\overline{m}=m\overline{1}\in \langle \overline{1}\rangle$.
De hecho, veremos más adelante que los ejemplos anteriores son, esencialmente, TODOS los grupos cíclicos que hay. Dicho de manera más precisa: si $G$ es un grupo cíclico se cumple lo siguiente:
- Si $G$ es infinito entonces $G$ es isomorfo a $\mathbb{Z}$ (con la suma).
- Si $G$ es finito entonces $G$ es isomorfo a $\mathbb{Z}_n$ (con la suma), donde $n$ es el orden de $G$.
La pregunta natural que surge ahora (y que estoy seguro que todas/os os habéis hecho después de ver la definición de grupo cíclico 🙂 ) es la siguiente: los subgrupos de un grupo cíclico, ¿son también cíclicos? Hemos demostrado que es así. El enunciado preciso del teorema es el siguiente:
Teorema. Todo subgrupo de un grupo cíclico también es cíclico.
Recordemos la demostración. En clase he tratado de hacerla algo más detallada que la que hay en los apuntes, pero trataré todavía de estructurarla y detallarla más aquí (para ayudaros a entenderla mejor).
Sea $G$ un grupo cíclico y sea $H$ un subgrupo de $G$. Como $G$ es cíclico, podrá ser generado por un solo elemento, es decir, existe un elemento $g\in G$ tal que $G=\langle g \rangle$. El objetivo es probar que $H$ también es cíclico, es decir, que puede ser generado por un solo elemento.
Si $H=\{1_G\}$ entonces $H$ es obviamente cíclico, pues $H=\langle 1_G\rangle$.
Supongamos ahora que $H\neq \{1_G\}$. Para demostrar que $H$ es cíclico procederemos de la siguiente manera:
(1) Primero probaremos que el conjunto $A:=\{s\in \mathbb{N}\mid g^s\in H\}$ es no vacío.
(2) Como $A$ es un subconjunto no vacío del conjunto de los números naturales, tiene mínimo (por el buen orden de $\mathbb{N}$). Denotemos por $n$ a dicho mínimo.
(3) Probaremos que $H$ está generado por $g^n$, es decir, que $H=\langle g^n\rangle$.
Vamos a ello.
Empecemos por el paso (1): Como $H\neq \{1_G\}$, existe un elemento $x\in H$ tal que $x\neq 1_G$. Como $x\in H\leq G=\langle g \rangle$, $x$ se podrá expresar en forma de potencia de $g$, es decir, existe $s\in \mathbb{Z}\setminus \{0\}$ tal que $x=g^s$ (nótese que $s\neq 0$ porque $x\neq 1$). Ahora distinguimos dos casos:
- Caso 1: $s$ es positivo. En este caso, $s\in A$ y, por tanto, $A\neq \emptyset$.
- Caso 2: $s$ es negativo. En este caso, $g^{-s}=(g^{s})^{-1}=x^{-1}\in H$ porque $x\in H$ y $H$ es un subgrupo. Luego $-s\in A$.
En cualquiera de los dos casos, hemos encontrado un elemento en $A$. Por tanto, concluimos que $A$ es no vacío. Ya tenemos el paso (1).
En el paso (2), simplemente hay que tomar $n:=\min(A)$.
Veamos ahora el paso (3). La inclusión $\langle g^n\rangle \subseteq H$ es obvia, puesto que $g^n$ pertenece a $H$ y, así, todas sus potencias también pertenecerán a $H$. Veamos la inclusión contraria. Para ello, escojamos un elemento arbitrario $h$ de $H$ y probemos que $h$ puede expresarse como una potencia de $g^n$:
Como $h\in H\leq G=\langle g \rangle$, $h$ podrá expresarse como una potencia de $g$, es decir, existe un entero $m$ tal que $x=g^m$.
Aplicando el Algoritmo de la División a $m$ y a $n$, existen dos enteros $q$ y $r$ tales que $0\leq r<n$ y $m=nq+r$. Por tanto: $$h=g^m=g^{nq+r}=(g^n)^q g^r.$$ Multiplicando a ambos lados por el inverso de $(g^n)^q$ (es decir, por $(g^n)^{-q}$) se obtiene que $$g^r=(g^n)^{-q} h.$$
Y aquí está el punto clave: como $g^n$ pertenece a $H$ (recuérdese que $n$ es el mínimo de $A$), cualquier potencia suya también pertenecerá a $H$ (en particular, $(g^n)^{-q}$). Por tanto, en el miembro de la derecha de la igualdad anterior tenemos un producto de dos elementos de $H$. Como $H$ es subgrupo, dicho producto debe pertenecer a $H$. Concluimos, por tanto que $g^r$ (el miembro de la izquierda) pertenece a $H$. Pero esto implica que $r$ ha de ser igual a $0$ porque, si fuera estrictamente positivo, ¡$r$ pertenecería a $A$, y esto es contradictorio con el hecho de que $r<n$ y $n=\min(A)$!
Y esto permite finalizar la prueba puesto que, como $r=0$, se tiene que $h=(g^n)^q\in \langle g^n\rangle$ (pues $h$ es una potencia de $g^n$).
Clase del 13 de septiembre (2 horas)
En la clase de hoy hemos probado el Teorema de Caracterización de Subgrupos. Afirma lo siguiente: un subconjunto $H$ de un grupo $G$ es un subgrupo de $G$ si y sólo si
- El neutro de $G$ pertenece a $H$.
- $H$ es cerrado para la operación de $G$, es decir, $xy\in H$ para todo $x,y\in H$.
- $H$ es cerrado para la “toma de inversos”, es decir, $x^{-1}\in H$ para todo $x\in H$.
Además hemos probado otro criterio que consiste en UNA SOLA CONDICIÓN (previa constatación de que el subconjunto es no vacío). Dice lo siguiente: un subconjunto NO VACÍO $H$ de un grupo $G$ es un subgrupo de $G$ si y sólo si $xy^{-1}\in H$ para todo $x,y\in H$.
Hemos visto varios ejemplos de subgrupos. Uno de ellos es el “grupo especial lineal” de dimensión $n$ sobre un cuerpo $K$. Consiste en el conjunto de las matrices cuadradas con entradas en $K$ y con determinante igual a $1$ (con el producto matricial como operación). Se trata de un subgrupo de $GL(n,K)$ (el grupo general lineal).
Hemos demostrado que la intersección de una familia arbitraria de subgrupos es un subgrupo y, dado un subconjunto $X$ (no vacío) de un grupo $G$, hemos definido el “subgrupo generado por $X$” (denotado por $\langle X \rangle$) como la intersección de todos los subgrupos de $G$ que contienen a $X$ (o, dicho de otro modo, como el menor subgrupo de $G$ que contiene a $X$). Hemos demostrado que $\langle X \rangle$ está formado exactamente por los productos de la forma $x_1 x_2\cdots x_n$, donde $n$ es un número natural y, para todo $i$, $x_i$ es, o bien un elemento de $X$ o bien el inverso de un elemento de $X$.
Decimos que un grupo $G$ “está generado” por un subconjunto $X\subseteq G$ (no vacío) si $$G=\langle X \rangle$$ o, dicho de otro modo, si todo elemento de $G$ se puede expresar como producto de elementos de $X$ e inversos de elementos de $X$. Si un grupo admite un sistema finito de generadores se dice que “es finitamente generado”.
Hemos visto varios ejemplos de sistemas generadores de grupos. En particular, hemos visto que el grupo cuaternio de orden 8, $Q_8$, está generado por $i$ y $j$, es decir, $Q_8=\langle i,j\rangle$. También hemos visto que el grupo diédrico de orden $2n$, $D_{2n}$ (que es el grupo de simetrías de un $n$-ágono regular), está formado por $n$ rotaciones ($1, \rho, \rho^2,\ldots, \rho^{n-1}$) y $n$ reflexiones ($\tau, \tau\rho, \ldots, \tau \rho^{n-1}$), donde $\rho$ es la rotación con centro el polígono regular y ángulo $2\pi/n$, y $\tau$ es una de las reflexiones. La rotación $\rho$ tiene orden $n$ y TODAS las reflexiones tienen orden 2. Además, se satisface la condición $\rho\tau=\tau \rho^{-1}$ (y obsérvese que $\rho^{-1}=\rho^{n-1}$, pues $o(\rho)=n$).
PODÉIS RESOLVER YA el Problema 10 de la hoja de problemas del Capítulo 1:
Para los restantes problemas necesitamos avanzar un poco más en la materia.
También he comentado en clase que el enunciado del Ejercicio 1.10 es mejor cambiarlo por el siguiente:
Si $G$ es un grupo y $a,b\in G$ entonces:
- Si $a$ tiene orden finito entonces $a^{-1}$ también tiene orden finito y $o(a^{-1})=o(a)$.
- Si $ab$ tiene orden finito entonces $ba$ también tiene orden finito y $o(ab)=o(ba)$.
La solución que hay escrita es válida. El motivo del cambio es que es posible que $a$ y $b$ tengan orden finito y, sin embargo, $ab$ tenga orden infinito. El enunciado anterior, interpretado correctamente, estaba bien; sin embargo, creo que está todo más claro si lo cambiamos por éste.