On the equivalence of cyclic and quasi-cyclic codes over finite fields

Abstract

This paper studies the equivalence problem for cyclic codes of length $p^r$ and quasi-cyclic codes of length $p^rl$. In particular, we generalize the results of Huffman, Job, and Pless (J. Combin. Theory. A, 62, 183--215, 1993), who considered the special case $p^2$. This is achieved by explicitly giving the permutations by which two cyclic codes of prime power length are equivalent. This allows us to obtain an algorithm which solves the problem of equivalency for cyclic codes of length $p^r$ in polynomial time. Further, we characterize the set by which two quasi-cyclic codes of length $p^rl$ can be equivalent, and prove that the affine group is one of its subsets.

Keywords

• Cyclic code,Quasi-cyclic code,Equivalence,Automorphism,Permutation

References

1. [1] B. Alspach, T. D. Parson, Isomorphism of circulant graphs and digraphs, Discrete Math. 25(2) (1979) 97–108.
2. [2] L. Babai, P. Codenotti, J. A. Groshow, Y. Qiao, Code equivalence and group isomorphism, in Proc. ACM-SIAM Symp. on Discr. Algorithms, San Francisco, CA, (2011) 1395–1408.
3. [3] N. Brand, Polynomial isomorphisms of combinatorial objects, Graphs Combin. 7(1) (1991) 7–14.
4. [4] K. Guenda, T. A. Gulliver, On the permutation groups of cyclic codes, J. Algebraic Combin. 38(1) (2013) 197–208.
5. [5] M. Hall, Jr., The Theory of Groups, MacMillan, New York, 1970.
6. [6] W. C. Huffman, V. Job, V. Pless, Multipliers and generalized multipliers of cyclic objects and cyclic codes, J. Combin. Theory Ser. A 62(2) (1993) 183–215.
7. [7] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes III: Generator theory, IEEE Trans. Inform. Theory 51(7) (2005) 2692–2700.
8. [8] R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, (1978) 114–116.

9. [9] A. Otmani, J.–P. Tillich, L. Dallot, Cryptanalysis of a McEliece cryptosystem based on quasi-cyclic LDPC codes, in Proc. Conf. on Symbolic Computation and Crypt., Beijing, China, (2008) 69–81.
10. [10] P. P. Palfy, Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. 8(1) (1987) 35–43.
11. [11] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory 46(4) (2000) 1193–1203.
12. [12] N. Sendrier, D.E. Simos, How easy is code equivalence over $F_q$?, in Proc. Int. Workshop on Coding Theory and Crypt., Bergen, Norway, 2013.
13. [13] N. Sendrier, D. E. Simos, The hardness of code equivalence over $F_q$ and its application to codebased cryptography, in P. Gaborit (Ed.), Post-Quantum Cryptography, Springer Lecture Notes in Computer Science 7932, Limoges, France (2013) 203–216.