Le sujet porte sur une classe de codes correcteurs d erreurs dits codes cycliques tordus, et ses applications a l'Informatique quantique et aux codes quasi-cycliques. Les codes cycliques classiques ont une structure d'idéaux dans un anneau de polynômes. Ulmer a introduit en 2008 une généralisation aux anneaux dits de polynômes tordus, une classe d'anneaux non commutatifs introduits par Ore en 1933. Dans cette thèse on explore le cas du corps a quatre éléments et de l'anneau produit de deux copies du corps a deux éléments. / The topic of the thesis is the study of skew cyclic codes, with application to Quantum Computing and quasi-cyclic codes. Classical cyclic codes have a natural structure of ideals in a polynomial ring. This was generalized by Ulmer in 2008 to skew polynomial rings, a class of non commutative rings introduced by Ore in 1933. The latter codes are not classically cyclic if the alphabet ring admits a non trivial automorphism. In this work is explored the cases of the finite field of order four and of a product ring of two copies of the finite field of order two.

One of the fundamental problems in commutative algebra and algebraic geometry is to understand the nature of the solution space of a system of multivariate polynomial equations over a field k, such as real or complex numbers. An important algorithmic tool in this study is the notion of Groebner bases (Buchberger (1965)). Given a system of polynomial equations, f1= 0,..., fm = 0, Groebner basis is a “canonical" generating set of the ideal generated by f1,...., fm, that can answer, constructively, many questions in computational ideal theory. It generalizes several concepts of univariate polynomials like resultants to the multivariate case, and answers decisively the ideal membership problem. The dimension of the solution set of an ideal I called the affine variety, an important concept in algebraic geometry, is equal to the Krull dimension of the corresponding coordinate ring, k[x1,...,xn]/I. Groebner bases were first introduced to compute k-vector space bases of k[x1,....,xn]/I and use that to characterize zero-dimensional solution sets. Since then, Groebner basis techniques have provided a generic algorithmic framework for computations in control theory, cryptography, formal verification, robotics, etc, that involve multivariate polynomials over fields. The main aim of this thesis is to study problems related to computational ideal theory over Noetherian commutative rings (e.g: the ring of integers, Z, the polynomial ring over a field, k[y1,…., ym], etc) using the theory of Groebner bases. These problems surface in many domains including lattice based cryptography, control systems, system-on-chip design, etc. Although, formal and standard techniques are available for polynomial rings over fields, the presence of zero divisors and non units make developing similar techniques for polynomial rings over rings challenging. Given a polynomial ring over a Noetherian commutative ring, A and an ideal I in A[x1,..., xn], the first fundamental problem that we study is whether the residue class polynomial ring, A[x1,..., xn]/I is a free A-module or not. Note that when A=k, the answer is always ‘yes’ and the k-vector space basis of k[x1,..., xn]/I plays an important role in computational ideal theory over fields. In our work, we give a Groebner basis characterization for A[x1,...,xn]/I to have a free A-module representation w.r.t. a monomial ordering. For such A-algebras, we give an algorithm to compute its A-module basis. This extends the Macaulay-Buchberger basis theorem to polynomial rings over Noetherian commutative rings. These results help us develop a theory of border bases in A[x1,...,xn] when the residue class polynomial ring is finitely generated. The theory of border bases is handled as two separate cases: (i) A[x1,...,xn]/I is free and (ii) A[x1,...,xn]/I has torsion submodules. For the special case of A = Z, we show how short reduced Groebner bases and the characterization for a free A-module representation help identify the cases when Z[x1,...,xn]/I is isomorphic to ZN for some positive integer N. Ideals in such Z-algebras are called ideal lattices. These structures are interesting since this means we can use the algebraic structure, Z[x1,...,xn]/I as a representation for point lattices and extend all the computationally hard problems in point lattice theory to Z[x1,...,xn]/I . Univariate ideal lattices are widely used in lattice based cryptography for they are a more compact representation for lattices than matrices. In this thesis, we give a characterization for multivariate ideal lattices and construct collision resistant hash functions based on them using Groebner basis techniques. For the construction of hash functions, we define a worst case problem, shortest substitution problem w.r.t. an ideal in Z[x1,...,xn], and establish hardness results for this problem. Finally, we develop an approach to compute the Krull dimension of A[x1,...,xn]/I using Groebner bases, when A is a Noetherian integral domain. When A is a field, the Krull dimension of A[x1,...,xn]/I has several equivalent algorithmic definitions by which it can be computed. But this is not true in the case of arbitrary Noetherian rings. We introduce the notion of combinatorial dimension of A[x1,...,xn]/I and give a Groebner basis method to compute it for residue class polynomial rings that have a free A-module representation w.r.t. a lexicographic ordering. For such A-algebras, we derive a relation between Krull dimension and combinatorial dimension of A[x1,...,xn]/I. For A-algebras that have a free A-module representation w.r.t. degree compatible monomial orderings, we introduce the concepts of Hilbert function, Hilbert series and Hilbert polynomials and show that Groebner basis methods can be used to compute these quantities. We then proceed to show that the combinatorial dimension of such A-algebras is equal to the degree of the Hilbert polynomial. This enables us to extend the relation between Krull dimension and combinatorial dimension to A-algebras with a free A-module representation w.r.t. a degree compatible ordering as well.