Araştırma Makalesi
BibTex RIS Kaynak Göster

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

Yıl 2017, , 261 - 269, 15.09.2017
https://doi.org/10.13069/jacodesmath.327375

Öz

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.

Kaynakça

  • [1] B. Alspach, T. D. Parson, Isomorphism of circulant graphs and digraphs, Discrete Math. 25(2) (1979) 97–108.
  • [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] N. Brand, Polynomial isomorphisms of combinatorial objects, Graphs Combin. 7(1) (1991) 7–14.
  • [4] K. Guenda, T. A. Gulliver, On the permutation groups of cyclic codes, J. Algebraic Combin. 38(1) (2013) 197–208.
  • [5] M. Hall, Jr., The Theory of Groups, MacMillan, New York, 1970.
  • [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] 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] R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, (1978) 114–116.
  • [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] P. P. Palfy, Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. 8(1) (1987) 35–43.
  • [11] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory 46(4) (2000) 1193–1203.
  • [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] 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.
Yıl 2017, , 261 - 269, 15.09.2017
https://doi.org/10.13069/jacodesmath.327375

Öz

Kaynakça

  • [1] B. Alspach, T. D. Parson, Isomorphism of circulant graphs and digraphs, Discrete Math. 25(2) (1979) 97–108.
  • [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] N. Brand, Polynomial isomorphisms of combinatorial objects, Graphs Combin. 7(1) (1991) 7–14.
  • [4] K. Guenda, T. A. Gulliver, On the permutation groups of cyclic codes, J. Algebraic Combin. 38(1) (2013) 197–208.
  • [5] M. Hall, Jr., The Theory of Groups, MacMillan, New York, 1970.
  • [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] 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] R. J. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report 42-44, (1978) 114–116.
  • [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] P. P. Palfy, Isomorphism problem for relational structures with a cyclic automorphism, European J. Combin. 8(1) (1987) 35–43.
  • [11] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algorithm, IEEE Trans. Inform. Theory 46(4) (2000) 1193–1203.
  • [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] 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.
Toplam 13 adet kaynakça vardır.

Ayrıntılar

Konular Mühendislik
Bölüm Makaleler
Yazarlar

Kenza Guenda Bu kişi benim 0000-0002-1482-7565

T. Aaron Gulliver Bu kişi benim 0000-0001-9919-0323

Yayımlanma Tarihi 15 Eylül 2017
Yayımlandığı Sayı Yıl 2017

Kaynak Göster

APA Guenda, K., & Gulliver, T. A. (2017). On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications, 4(3), 261-269. https://doi.org/10.13069/jacodesmath.327375
AMA Guenda K, Gulliver TA. On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications. Eylül 2017;4(3):261-269. doi:10.13069/jacodesmath.327375
Chicago Guenda, Kenza, ve T. Aaron Gulliver. “On the Equivalence of Cyclic and Quasi-Cyclic Codes over Finite Fields”. Journal of Algebra Combinatorics Discrete Structures and Applications 4, sy. 3 (Eylül 2017): 261-69. https://doi.org/10.13069/jacodesmath.327375.
EndNote Guenda K, Gulliver TA (01 Eylül 2017) On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications 4 3 261–269.
IEEE K. Guenda ve T. A. Gulliver, “On the equivalence of cyclic and quasi-cyclic codes over finite fields”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 4, sy. 3, ss. 261–269, 2017, doi: 10.13069/jacodesmath.327375.
ISNAD Guenda, Kenza - Gulliver, T. Aaron. “On the Equivalence of Cyclic and Quasi-Cyclic Codes over Finite Fields”. Journal of Algebra Combinatorics Discrete Structures and Applications 4/3 (Eylül 2017), 261-269. https://doi.org/10.13069/jacodesmath.327375.
JAMA Guenda K, Gulliver TA. On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017;4:261–269.
MLA Guenda, Kenza ve T. Aaron Gulliver. “On the Equivalence of Cyclic and Quasi-Cyclic Codes over Finite Fields”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 4, sy. 3, 2017, ss. 261-9, doi:10.13069/jacodesmath.327375.
Vancouver Guenda K, Gulliver TA. On the equivalence of cyclic and quasi-cyclic codes over finite fields. Journal of Algebra Combinatorics Discrete Structures and Applications. 2017;4(3):261-9.