Autour des codes de Reed-Muller généralisés
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Reed-Muller codes and almost perfect nonlinear functions have been studied mostly for the field with two elements because of their utilization in cryptography. This thesis generalize some results to odd characteristic. In a first time, we recall the definition and properties of generalized Reed-Muller codes. Particularly, we give a new proof of Delsarte, Goethals and Mac Williams' theorem which gives the minimal weight codewords of these codes. Then we study the covering radius of the first order generalized Reed-Muller codes. We find upper and lower bounds which give the value of the covering radius for an even number of variables. Furthermore, with Magma, we manage to get more precise results for the field with three elements. Finally, we give a decoding method for generalized Reed-Muller codes. In a second time, we are interested in almost perfectly nonlinear functions and perfectly nonlinear functions. We recall definitions and already known results. Then, we prove two conjectures of Dobbertin, Mills, Müller, Pott and Willems about familles of almost perfectly nonlinear power mappings in characteristic three and we give a new family of almost perfectly nonlinear power mappings in characteristic five. Finally, we study exceptional numbers in odd characteristic that is to say power mappings which are perfectly nonlinear on an infinity of extensions of a finite field. Using methods from Jedlicka, Hernando and McGuire, we prove that the only exceptional numbers congruent to 1 modulo a prime number p are of the form 1+p^l.
Abstract FR:
Les codes de Reed-Muller et les fonctions presque parfaitement non linéaires ont particulièrement été étudiés sur le corps fini à deux éléments pour leur utilisation en cryptographie. Dans cette thèse, on généralise un certain nombre des résultats obtenus à la caractéristique impaire. Dans un premier temps, on rappelle la définition et les propriétés des codes de Reed-Muller généralisés. En particulier, on donne une nouvelle preuve du théorème de Delsarte, Goethals et Mac Williams qui donnent les mots de poids minimal de ces codes. On s'intéresse ensuite au rayon de recouvrement des codes de Reed-Muller généralisés d'ordre 1. On en donne un encadrement, ce qui nous permet d'en déduire la valeur exacte pour un nombre pair de variables. De plus, à l'aide du logiciel Magma, on obtient des résultats plus précis sur le corps fini à trois éléments. Enfin, on donne une méthode de décodage des codes de Reed-Muller généralisés. Dans un deuxième temps, on étudie les fonctions presque parfaitement non linéaires et parfaitement non linéaires. Après avoir rappelé les définitions et les résultats connus, on démontre des conjectures de Dobbertin, Mills, Müller, Pott et Willems sur des familles de fonctions presque parfaitement non linéaires en caractéristique 3 et on donne une nouvelle famille de fonctions presque parfaitement non linéaires en caractéristique cinq. Par la suite, on s'intéresse aux fonctions puissances parfaitement non linéaires sur une infinité d'extensions d'un corps fini. En utilisant des méthodes de Jedlicka, Hernando et McGuire, on démontra que les seuls entiers congrus à 1 modulo un nombre premier p qui sont des nombres exceptionnels sont de la forme 1+^Il.