How easy is code equivalence over Fq?

Abstract : The linear code equivalence problem is to decide whether two linear codes over F_q are identical up to a linear isometry of the Hamming space. The support splitting algorithm runs in polynomial time for all but a negligible proportion of all linear codes, and solves the latter problem by recovering the isometry when it is just a permutation of the code support. While for a binary alphabet isometries are exactly the permutations, this is not true for q>2. We explore in this paper, a generalization of the support splitting algorithm where we aim to retrieve any isometry between equivalent codes. Our approach is twofold; first we reduce the problem of deciding the equivalence of linear codes to an instance of permutation equivalence. To this end, we introduce the notion of the closure of a code and give some of its properties. In the aftermath, we exhibit how this algorithm can be adapted for q=3 and q=4, where its complexity is polynomial for almost all of its instances. Although the aforementioned reduction seems attractive, when q>4 the closure reduces the instances of the linear code equivalence problem to exactly those few instances of permutation equivalence that were hard for the support splitting algorithm. Finally, we argue that for q>4 the linear code equivalence problem might be hard for almost all instances.
Type de document :
Communication dans un congrès
International Workshop on Coding and Cryptography - WCC 2013, Apr 2013, Bergen, Norway. 2013
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00790861
Contributeur : Nicolas Sendrier <>
Soumis le : vendredi 20 septembre 2013 - 15:10:33
Dernière modification le : mercredi 29 novembre 2017 - 15:09:34
Document(s) archivé(s) le : vendredi 7 avril 2017 - 00:41:44

Fichier

codeq6_dcc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00790861, version 2

Collections

Citation

Nicolas Sendrier, Dimitrios E. Simos. How easy is code equivalence over Fq?. International Workshop on Coding and Cryptography - WCC 2013, Apr 2013, Bergen, Norway. 2013. 〈hal-00790861v2〉

Partager

Métriques

Consultations de la notice

438

Téléchargements de fichiers

172