Códigos Goppa

Abstract

El objetivo de este trabajo es servirnos de las herramientas impartidas en la asignatura de Álgebra Conmutativa y Geometría Algebraica para estudiar la teoría de códigos correctores de errores, presentada en la asignatura Teoría de Códigos y Criptografía. Esto servirá de pretexto para profundizar en temas importantes de la geometría algebraica como la teoría de divisores para curvas. Como principal aplicación para la teoría de códigos, definiremos los códigos Goppa, una familia de códigos de gran importancia histórica pues es la primera familia in nita de códigos en superar la cota de Gilbert-Varshamov. En cuanto a la organización del trabajo, este se encuentra dividido en tres capítulos y un apéndice: - - El primer capítulo presenta, en sus tres primeras secciones un repaso de los conceptos básicos de la asignatura de Teoría de Códigos y Criptografía (Definición de código corrector de errores, corrección por mínima distancia, matrices de control, códigos cíclicos...). Las dos secciones siguientes están dedicadas a dos familias de códigos que fueron posteriormente generalizados por los códigos Goppa: los códigos BCH y los códigos de Goppa clásicos. - En el segundo capítulo se desarrolla la geometría algebraica necesaria para definir los códigos de Goppa. El capítulo comienza exponer técnicas para describir curvas proyectivas sin puntos singulares sobre cuerpos algebraicamente cerrados a través de estudiar los llamados anillos de valoración de su cuerpo de funciones. Tras eso, se da una pequeña introducción a la teoría de divisores en dicho caso y se de nen los espacios de Riemman-Roch, los cuales que serán la base de los códigos Goppa. En las últimas secciones del capítulo se define la noción de curva proyectiva abstracta que será de gran utilidad para extender la teoría a cuerpos arbitrarios. 6 códigos goppa - En el tercer y último capítulo se da la definición de la familia de los códigos Goppa así como la estimación de sus parámetros dimensión y distancia mínima. En la segunda sección, se motiva a través de la cota de Hasse-Weil, la elección de varias curvas como base para la construcción de códigos Goppa. Además, se dan las matrices generatrices de dichos códigos haciendo un análisis completo de dichos ejemplos. Por último, en el resto del capítulo, se dedica una pequeña sección a hablar de la cota de Gilbert-Varshamov. - Por último, el apéndice del trabajo elabora sobre asuntos que, aunque son de gran interés, no se han podido incluir en los capítulos principales del trabajo por falta de espacio. A pesar de ello, como estaban previstos en una primera planificación para ser estudiados, se añaden como complemento al texto principal siendo citados en repetidas ocasiones invitando al lector que ahonde en los temas expuestos. Se da una definición precisa de lo que se entiende por el género de una curva además de darse una prueba completa de la desigualdad de Riemman. Estas herramientas se utilizan para tratar la dualidad en códigos de Goppa. Para finalizar, hay una pequeña sección dedicada al estudio del grupo absoluto de Galois de un cuerpo finito. Un último comentario en cuanto a la organización del contenido. El trabajo es extenso y largo de leer entero. Por ello, me gustaría recomendar que, en el caso de que el lector prefiera "ir al grano" y centrarse en lo importante (el último capítulo), las últimas 3 secciones de los capítulos 1 y 2 son de menor importancia que el resto del contenido para ese propósito. En especial las últimas secciones del capítulo segundo, son dedicadas a formalidades necesarias para ver que la teoría de las dos primeras secciones se extiende bien a cuerpos cualesquiera. Sin embargo, la extensión es bastante natural y los resultados obtenidos son bastante parecidos a los obtenidos en la primera parte del capítulo. Me gustaría terminar este pequeño resumen destacando un detalle. Algunos resultados que se presentan a lo largo del trabajo son muy profundos y por ello algunas demostraciones se omiten. En general, si la demostración puede seguirse pero se omite por motivos de longitud del trabajo, suelo dar una indicación de la idea de la prueba y de las herramientas que se utilizan en la misma. Por desgracia, será inevitable que a lo largo del trabajo nos encontremos unos pocos resultados que son imposibles de probar en tan solo unas pocas páginas de un trabajo de fin de grado y nos veremos obligados a asumir algunos teoremas. A pesar de todo esto, en cuanto a los resulta- ÍNDICE GENERAL 7 dos principales presentados en los tres primeros capítulos, todos están demostrados para el caso en el que estemos trabajando con curvas planas y, debido a que todos los ejemplos con los que construimos los códigos del capítulo 3 se basan en curvas planas, los resultados importantes del texto están todos demostrados. Hay una excepción a esto último: la fórmula de Plücker. Esta fórmula tiene una demostración un poco más compleja que el resto de resultados que precisa del teorema de Riemann-Roch en su versión completa. A pesar de ello, en el apéndice se indica una idea de cómo funcionaría la prueba conociendo el teorema de Riemann-Roch para no dejar al lector insatisfecho.

The goal of this project is to use the tools taught in the subject Commutative Algebra and Algebraic Geometry to study the theory of error-correcting codes presented in the subject Theory of Codes and Cryptography. This will serve as an excuse to delve into important topics in algebraic geometry such as the theory of divisors in curves. As the main application for the theory of codes, we will de ne the Goppa codes, a family of codes of historical value since it is the rst in nite family of codes known to go beyond the Gilbert-Varshamov bound. Regarding the memoir, it is divided into three chapters and an appendix: The rst chapter presents, in its rst three sections, a review of the basic concepts of the subject of Code Theory and Cryptography (de nition of error– correcting code, minimum distance correction, control matrices, cyclic codes ...). The next two sections are devoted to two families of codes that were later generalized by Goppa codes: the BCH codes and the classic Goppa codes. In the second chapter the algebraic geometry we need to de ne the Goppa codes is developed. The chapter begins exposing techniques to describe projective curves without singular points on algebraically closed elds through studying the so-called evaluation rings of their body of functions. After that, a brief introduction is given to the theory of divisors in this case and the Riemman-Roch spaces are de ned, which will be the basis of the Goppa codes. In the last sections of the chapter the notion of abstract projective curve is de ned, which will be very useful to extend the theory to arbitrary elds. The third and last chapter gives the de nition of the Goppa code family as well as the estimation of its dimension and minimum distance parameters. In the second section the choice of several curves as the basis for the construction of ÍNDICE GENERAL 1 Goppa codes is motivated through the Hasse-Weil bound. In addition, the generating matrices of those codes are given, making a complete analysis of the examples. Finally, in the rest of the chapter, a small section is devoted to discussing the Gilbert-Varshamov dimension. Finally, the appendix elaborates on topics that, being of great interest, have not been able to include in the main chapters of the work due to lack of space. Despite this, as they were foreseen to be studied in a rst planning, they are added as a complement to the main text. A precise de nition of what is meant by the genus of a curve is given in the appendix in addition to giving a complete proof of Riemman’s inequality. These tools are used to deal with duality in Goppa codes. Finally, there is a small section dedicated to the study of the absolute Galois group of a nite eld. One last comment regarding the organization of the content. The work might seem long to read in its entirety. For this reason, I would like to recommend that if the reader prefers to "cut to the chase" and focus on what is important (the last chapter), the last 3 sections of the 1 and 2 chapters are less essential than the rest of the content for that purpose. Especially the last sections of the second chapter are devoted to the formalities necessary to see that the theory from the rst two sections extends well to any eld. However, the extension is quite natural and the results obtained are quite similar to those obtained in the rst part of the chapter. I would like to end this short summary by highlighting one detail. Some results that are presented throughout the work are very profound and therefore some proofs are omitted. In general, if the proof can be followed but it is omitted due to its length, I usually give an indication of the idea behind it and the tools used in it. Unfortunately, it will be inevitable that throughout the work we will nd a few results that are impossible to prove in just a few pages of a dissertation and we will be forced to assume some theorems. Despite all this, as for the main results presented in the rst three chapters, they are all proven for the case in which we are working with plane curves and, because all the examples with which we build the codes of chapter 3 are based on plane curves, the important results of the text are all proved. There is an exception to the latter: Plücker’s formula. This formula has a proof a little more complex than the rest of the results required by the Riemann-Roch theorem in its complete version. Despite this, the appendix gives an idea of how the proof would work knowing the Riemann-Roch theorem so as not to leave the reader unsatis ed.