Title: Goppa codes and their applications Author: Bc. Jaroslav Kotil Department: Department of algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc. Abstract: In this diploma paper we introduce Goppa codes, describe their para- metres and inclusion in Alternant codes, which are residual Generalized Reed- Solomon codes, and Algebraic-geometry codes. Aftewards we demonstrate deco- ding of Goppa codes and introduce Wild Goppa codes. We also describe post- quantum cryptography member: McEliece cryptosystem for which no effective attacks with quantum computers are known. We outline a usage of this crypto- system with Goppa codes and describe the security of the cryptosystem together with possible attacks of which the most effective ones are based on information- set decoding. Keywords: Goppa codes, Generalized Reed-Solomon codes, Algebraic-geometry codes, Post-quantum cryptography, McEliece cryptosystem 1

Deux défis de la théorie du codage algébrique sont traités dans cette thèse. Le premier est le décodage efficace (dur et souple) de codes de Reed--Solomon généralisés sur les corps finis en métrique de Hamming. La motivation pour résoudre ce problème vieux de plus de 50 ans a été renouvelée par la découverte par Guruswami et Sudan à la fin du 20ème siècle d'un algorithme polynomial de décodage jusqu'au rayon Johnson basé sur l'interpolation. Les premières méthodes de décodage algébrique des codes de Reed--Solomon généralisés faisaient appel à une équation clé, c'est à dire, une description polynomiale du problème de décodage. La reformulation de l'approche à base d'interpolation en termes d'équations clés est un thème central de cette thèse. Cette contribution couvre plusieurs aspects des équations clés pour le décodage dur ainsi que pour la variante décodage souple de l'algorithme de Guruswami--Sudan pour les codes de Reed--Solomon généralisés. Pour toutes ces variantes un algorithme de décodage efficace est proposé. Le deuxième sujet de cette thèse est la formulation et le décodage jusqu'à certaines bornes inférieures sur leur distance minimale de codes en blocs linéaires cycliques. La caractéristique principale est l'intégration d'un code cyclique donné dans un code cyclique produit (généralisé). Nous donnons donc une description détaillée du code produit cyclique et des codes cycliques produits généralisés. Nous prouvons plusieurs bornes inférieures sur la distance minimale de codes cycliques linéaires qui permettent d'améliorer ou de généraliser des bornes connues. De plus, nous donnons des algorithmes de décodage d'erreurs/d'effacements [jusqu'à ces bornes] en temps quadratique.