Les anneaux de polynômes sont l'un des outils privilégiés pour construire et étudier des familles de codes correcteurs. Nous nous proposons, dans cette thèse, d'utiliser des anneaux de Öre, qui sont des anneaux de polynômes non-commutatifs, afin de créer des codes correcteurs. Cette approche nous permet d'obtenir des familles de codes correcteurs plus larges que si l'on se restreint au cas commutatif mais qui conservent de nombreuses propriétés communes. Nous obtenons notamment un algorithme qui permet de fabriquer des codes correcteurs dont la distance de Hamming ou la distance rang est prescrite. C'est ainsi que nous avons exhibé deux codes qui améliorent la meilleure distance minimale connue pour un code de même longueur et de même dimension. L'un est de paramètres $[42,14,21]$ sur le corps $\mathbb{F}_8$ et l'autre de paramètres $[40,23,10]$ sur $\mathbb{F}_4$. La généralisation de cette étude au cas d'anneaux polynomiaux multivariés est également présentée; l'outil principal est alors la théorie des bases de Gröbner qui s'adapte dans ce cadre non-commutatif et permet de manipuler des idéaux pour créer de nouvelles familles de codes correcteurs.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-11-06T18:45:09Z No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-11-09T14:32:38Z (GMT) No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) / Made available in DSpace on 2017-11-09T14:32:38Z (GMT). No. of bitstreams: 1 maurorodriguesrochajunior.pdf: 550118 bytes, checksum: 5b26ad1ab2bd9d4a190d742762346968 (MD5) Previous issue date: 2017-08-11 / O principal objetivo desse trabalho é estudar duas aplicações distintas das bases de Gröbner a códigos lineares. Com esse objetivo, estudamos como relacionar códigos a outras estruturas matemáticas, fazendo com que tenhamos novas ferramentas para a realização da codificação. Em especial, estudamos códigos cartesianos afins e os códigos algébrico-geométricos de Goppa. / The main objective of this work is to study two different applications of Gröbner basis to linear codes. With this purpose, we study how to relate codes to other mathematical structures, allowing us to use new tools to do the coding. In particular, we study affine cartesian codes e algebraic-geometric Goppa codes.

Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. C'est dans ce contexte que s'inscrit cette thèse dont les contributions sont doubles. D'une part, nous présentons de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Nous montrons que la résolution de systèmes avec symétries est étroitement liée à la résolution de systèmes quasi-homogènes. Nous proposons ainsi de nouveaux résultats de complexité pour la résolution de tels systèmes. Nous nous intéressons également à l'étape bloquante de la résolution de systèmes : le changement d'ordre pour bases de Gröbner. La complexité classique de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons pour la première fois des algorithmes de changement d'ordre de complexité sous-cubique en le nombre de solutions. D'autre part, nous nous intéressons à l'attaque du logarithme discret sur les courbes elliptiques par calcul d'indice proposée par Gaudry. Nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. Une des étapes principales de cette attaque nécessite le calcul de polynômes de sommation introduits par Semaev. Les symétries des courbes elliptiques binaires nous permettent d'élaborer un nouvel algorithme par évaluation-interpolation pour le calcul des polynômes de sommation. Munis de cet algorithme nous établissons un nouveau record pour le calcul de ces polynômes.

The main objective of this dissertation is to present an algebraic method capable of determining a solution, if any, of a non linear polynomial equation systems using Gröbner basis. In order to accomplish that, we first present some concepts and theorems linked to polynomial rings with several undetermined and monomial ideals where we highlight the division extended algorithm, the Hilbert Basis and the Buchberger´s algorithm. Beyond that, using basics of Elimination and Extension Theorems, we present an algebraic solution to the map coloring that use 3 colors as well as a general solution to the Sudoku puzzle. / O objetivo principal desse trabalho é, usando bases de Gröbner, apresentar um método algébrico capaz de determinar a solução, quando existir, de sistemas de equações polinomiais não necessariamente lineares. Para tanto, necessitamos inicialmente apresentar alguns conceitos e teoremas ligados a anéis de polinômios com várias indeterminadas e de ideais monomiais, dentre os quais destacamos o algoritmo extendido da divisão, o teorema da Base de Hilbert e o algoritmo de Buchberger. Além disso, usando noções básicas da Teoria de eliminação e extensão, apresentamos uma solução algébrica para o problema da coloração de mapas usando três cores, bem como um solução geral para o puzzle Sudoku.