Self-dual skew codes and factorization of skew polynomials

International audienceThe construction of cyclic codes can be generalized to so called module $\theta$-cyclic codes using noncommutative polynomials. The product of the generator polynomial $g$ of a self-dual module $\theta$-cyclic code and its "skew reciprocal polynomial" is known to be a noncommutative polynomial of the form $X^n-a$, reducing the problem of the computation of all such codes to a Gröbner basis problem where the unknowns are the coefficients of $g$. In previous work, with the exception of the length $2^s$, over $\FF_4$ a large number of self-dual codes were found. In this paper we show that $a$ must be $\pm 1$ and that for $n=2^s$ the decomposition of $X^n\pm 1$ into a product of $g$ and its "skew reciprocal polynomial" has some rigidity properties which explains the small number of codes found for those particular lengths over $\FF_4$. In order to overcome the complexity limitation resulting from the Gröbner basis computation we present, in the case $\theta$ of order two, an iterative construction of self-dual codes based on least common multiples and factorization of noncommutative polynomials. We use this approach to construct a $[78,39,19]_4$ self-dual code and a $[52,26,17]_9$ self-dual code which improve the best previously known minimal distances for these lengths