Articulo 1.docx 2q4m4i

Teoría de grupos en la generación de Códigos Bodmer Richard, Murillo Isaac Departamento de Computación y Simulación de Sistemas, Universidad Tecnológica de Panamá Ciudad de Panamá, Panamá [email protected]

Resumen— Este trabajo muestra los resultados obtenido de una investigación sobre las ideas básicas de la teoría de grupos para aplicarlas a la generación de códigos.

  

Índice de Términos— Concepto de estructuras algebraicas, Concepto de las estructuras algebraicas grupos y semigrupos, Aplicación de la teoría de grupos en la solución de acertijos: cubo de Rubik, Aplicación de la teoría de grupos en la generación de códigos binarios o en criptografía: la máquina de enigma, Aplicación de los grupos y semigrupos en las Redes Sociales. I. INTRODUCCIÓN Este documento es una investigación respecto a la teoría de grupos aplicadas a la generación de códigos, podremos encontrar diferentes aplicaciones de esta teoría en acertijos como el cubo de Rubik, también en la criptografía con la maquina enigma usada en la Segunda Guerra Mundial, también podemos ver las aplicaciones de las estructuras algebraicas grupos y semigrupos en un tema actual como lo es las redes sociales. La estructura algebraica es un conjunto X dotado de una o varias operaciones, allí podemos encontrar los grupos (que la resolución de una operación interna satisface la propiedad asociativa, elemento neutro y simetría/asimetría) y semigrupos (que contiene tiene ley de composición e identidad). Encontramos una teoría de grupos que clasifica a esos en propiedades y aplicaciones dentro y fuera de matemáticas. Esta misma se puede aplicar a distintos temas ya mencionados anteriormente como códigos binarios o cubo de Rubik. II. DESARROLLO DE CONTENIDOS A. Concepto de estructuras algebraica. Una Estructura Algebraica es un objeto matemático consistente en un conjunto no vacío y una relación o ley de composición interna definida en él. B. Concepto de las estructuras algebraicas grupos y semigrupos. Grupos: un grupo es una estructura algebraica formada por un conjunto no vacío dotado de una operación interna que combina cualquier par de elementos para componer un tercero, dentro del mismo conjunto y que satisface la propiedad asociativa, existencia de elemento neutro y simétrico. Semigrupos: Un semigrupo es un sistema algebraico de la forma (A, @) en la cual A es un conjunto no vacío, @ es una operación interna definida en A.

Si la ley de composición interna también es conmutativa se llama semigrupo conmutativo. Si existe el elemento neutro se dice que es un semigrupo con unidad o semigrupo con identidad. El elemento neutro de llama identidad.

Operaciones:  Operación interna: llamamos operación interna en un conjunto A, a la operación que hace corresponder a cada par de elementos de AxA con un único elemento de A.  Operación externa: llamamos operación externa en un conjunto A sobre otro conjunto K, a la operación que hace corresponder a todo par de elementos (a,k) de AxK un único elemento de A. C. Aplicación de la teoría de grupos en la solución de acertijos: cubo de Rubik Teoría de grupos: En álgebra abstracta, la teoría de grupos estudia las estructuras algebraicas conocidas como grupos. Sus objetivos son, entre otros, la clasificación de los grupos, sus propiedades y sus aplicaciones tanto dentro como fuera de las matemáticas. El cubo de Rubik es un rompecabezas mecánico inventado por el escultor y profesor de arquitectura húngaro Erno˝ Rubik en 1974. Se trata de un cubo cuyas caras tienen cada una nueve pegatinas y que consta de un ingenioso dispositivo mecánico que permite que sus caras giren y las pegatinas cambien de posición. El problema usual de este rompecabezas consiste en, a partir de una posición en la que las caras muestran pegatinas de distintos colores, realizar una sucesión de movimientos del cubo conseguir que las seis caras del cubo mues- tren un único color.  Notación para el cubo: La disposición de los colores en las caras del cubo puede variar de cubo en cubo. Por ello, es interesante disponer de una notación que no dependa de los colores que el fabricante haya querido utilizar en su cubo ni de la orientación, sino simplemente de su posición: Derecha, Izquierda, Frontal, Trasera, Arriba, Abajo.  Simetría del cuadrado: simetrías del cuadrado, esto es, los movimientos del cuadrado como cuerpo rígido que lo devuelven a su lugar original, aunque quizás en distinta posición. Es posible que alguna simetría exija levantar el cuadrado del plano del papel y darle la vuelta fuera del plano.

luego se convertiría en la guerra más devastadora que ha conocido la humanidad. En ese momento, el matemático y genio Alan Turing ya estaba trabajando para el Government Code & Cypher School (GC&CS), el Servicio de Inteligencia británico. Un año antes había empezado con ellos su tarea a tiempo parcial, que desde el principio estuvo centrada en descifrar el código secreto que Alemania utilizaba para sus comunicaciones militares, llamado Enigma.

Hay dos maneras distintas de entender la permutación de las letras A, B, C y D del cuadrado. Podemos considerar que la acción es «se desplaza a» o «se sustituye por». También podemos considerar que la permutación actúa sobre las siglas o símbolos, independientemente de su posición, o que actúa sobre el contenido de las posiciones, independientemente del símbolo que ocupe actualmente esta posición. Estas distinciones serán importantes cuando multipliquemos permutaciones. D. Aplicación de la teoría de grupos en la generación de códigos binarios o en criptografía: la máquina de enigma Criptografía: La criptografía es el estudio de las técnicas matemáticas relacionadas con los aspectos de seguridad de la información tal como: la confidencialidad, la integridad de datos, la autenticidad y el no rechazo. Hay dos tipos de criptografía: criptografía simétrica o de clave privada y criptografía asimétrica o de clave pública. La criptografía de clave pública se desarrolló en los años setenta y utiliza complicados algoritmos matemáticos relacionados con teoría de números, curvas elípticas, grupos infinitos no conmutativos, teoría de gráficas, teoría del caos. La criptografía asimétrica surge para solucionar el problema que tiene la criptografía simétrica de distribución de claves. Ejemplo: Algoritmo rsa1 Este algoritmo es de clave pública y debe su nombre a sus tres inventores: Rivest Ron, Shamir Adi y Adleman Leonard. La descripción del esquema es la siguiente: a) Elegimos dos números primos p y q suficientemente grandes, y tomamos n = pq. b) Buscamos e tal que sea primo de φ(n)=(p − 1)(q − 1). c) Como e y φ(n) son primos entre sí, entonces existe un d tal que: e • d ≡ 1(mod φ(n) = n + 1 − p − q), donde d se puede calcular mediante el algoritmo de Euclides. d) Definimos Ee(x) = xe mod n función de cifrado Dd(y) = yd mod n función de descifrado x, y ∈ Zn. • Clave pública: (e, n) • Clave privada: (d, p, q). Cualquiera que conozca p, q y d podrá descifrar los mensajes del propietario de la clave (de hecho en este caso basta conocer p y q para romper el sistema). Cabe mencionar que la justificación de este esquema depende sólo del hecho de que xed+1 ≡ x mod n La máquina Enigma: El 1 de septiembre de 1939 Alemania invadió Polonia, dando comienzo a lo que

Aplicación en códigos binarios: El Álgebra de Boole, fue presentada originalmente por el inglés George Boole, en el año de 1854 en su artículo "An Investigation of the Laws of Thoght... ", Sin embargo, las primeras aplicaciones a circuitos de conmutación fueron desarrolladas por Claude Shannon en su tesis doctoral "Análisis simbólico de los circuitos de conmutación y relés" hasta 1938. A continuación se presentan los postulados fundamentales del álgebra de Boole: Su álgebra consiste en un método para resolver problemas de lógica que recurre solamente a los valores binarios 1 y 0 y a tres operadores fundamentales: AND (y), OR (o) y NOT (no). De esta forma se finca la lógica algebraica Booleana la cual ahora encuentra aplicación en la construcción de computadores, circuitos eléctricos, etc. E. Aplicación de los grupos y semigrupos en las Redes Sociales. Para hacer una descripción clara de una red social es necesario un concepto matemático, el de “relación”, y eso nos lleva directamente a los semigrupos. Brevemente, un semigrupo es un conjunto en el que se ha definido una operación binaria que cumple la propiedad asociativa. Es decir, si S es un conjunto no vacío, que llamamos conjunto origen, una operación binaria definida sobre S es una función por la cual a cada par ordenado de elementos de S, como r y s, le corresponde otro elemento de S que tiene como expresión r⋅ s y se llama producto de r y s. Esta operación binaria cumple la propiedad asociativa si para cualesquiera que sean r, s, t de S (r ⋅ s) ⋅ t = r ⋅ (s ⋅ t) Semigrupos de Relaciones: En la mayoría de las aplicaciones comunes de los semigrupos al campo de las redes sociales, el conjunto origen es normalmente algún conjunto de relaciones sociales, como “amigo”, “madre”, “enemigo” etc., mientras que la operación binaria es normalmente la composición de relaciones, como en “la madre de un amigo”. Dependiendo de la situación, estas relaciones pueden hacerse operativas de diferentes maneras. Un “amigo” puede ser, en un estudio determinado, un conjunto de pares ordenados de personas (x, y) donde y muestra un comportamiento “amistoso” objetivo hacia x. En otro estudio, sin embargo, podría determinarse que x es “amigo” de y si así lo confirma y. Vínculos diádicos y Estructura Global: El elemento básico de una relación social es el vínculo diádico entre dos individuos. Hay muchas clases diferentes de vínculos de ese tipo, como “gustar”, “amar”, “desear” u “odiar”. Para reflejar completamente la realidad debe especificarse cuál es la dirección de esos vínculos.

III. CONCLUSIONES De acuerdo a lo que leímos en el anterior artículo podemos destacar las diferentes aplicaciones de la teoría de grupos en la generación de códigos y con ayuda de las matemáticas discretas pudimos comprobar las distintas cantidades que manejamos en ejemplos como el Cubo de Rubrik o como lo hicieron en la utilización de la Maquina Enigma. La teoría de grupos también nos sirvió para reconocer su uso en Redes Sociales y las relaciones que se dan gracias a ellas. También vimos ejemplos detallados de las combinaciones y/o permutaciones usados para descifrar un código binario. RECONOCIMIENTOS Sin duda alguna este trabajo investigativo nos sirvió para darnos cuenta del diferente uso de las teorías de grupos y gracias al internet y libros encontrados dimos respuestas a dudas que se cruzaron en la realización del mismo. REFERENCIAS [1] [2] [3] [4]

Rosen Kenneth H., Matemática discreta y sus aplicaciones, 2da ed., McGraw-Hill., Ed. Washington, Estados Unidos: 2004 Wright, Charles R. B y Ross, Kenneth A. Matemáticas discretas. 1ra ed., Prentice Hall, México DF, México, 1999. Zaldívar, Felipe, Introducción a la teoría de grupos, 1ra ed., Prentice Hall, México DF, México, 2006. Boyd, John P., Weakly Nonlocal Solitary Waves and Beyond‑All‑Orders, Estados Unidos, 1998.