ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.327375 J. Algebra Comb. Discrete Appl. 4(3) • 261–269 Received: 21 February 2016 Accepted: 21 March 2017 Journal of Algebra Combinatorics Discrete Structures and Applications On the equivalence of cyclic and quasi-cyclic codes over finite fields Research Article Kenza Guenda, T. Aaron Gulliver Abstract: This paper studies the equivalence problem for cyclic codes of length pr and quasi-cyclic codes of length prl. In particular, we generalize the results of Huffman, Job, and Pless (J. Combin. Theory. A, 62, 183–215, 1993), who considered the special case p2. 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 pr in polynomial time. Further, we characterize the set by which two quasi-cyclic codes of length prl can be equivalent, and prove that the affine group is one of its subsets. 2010 MSC: 94B05, 94B15, 94B60 Keywords: Cyclic code, Quasi-cyclic code, Equivalence, Automorphism, Permutation 1. Introduction The equivalence problem for codes has many practical applications such as code-based cryptogra- phy [8, 9, 12, 13]. As a consequence, this problem has received considerable attention in the litera- ture [2, 3, 6, 11, 12]. However, progress in obtaining results has been slow. Brand ([3]) characterized the set of permutations by which two combinatorial cyclic objects on pr elements are equivalent. Using these results, Huffman et al. ([6]) explicitly gave this set for the case p2, and constructed algorithms to find the equivalence between cyclic objects and extended cyclic objects. In [6], a negative answer was given to the generalization of their results to the case pr, r > 2. This is due to the fact that the permutations of Brand that are crucial to the proofs do not generate a Sylow subgroup of Spr . Babai et al. ([2]) gave an exponential time algorithm for determining the equivalence of codes. Sendrier ([11]) proposed the support splitting algorithm to solve the problem of code equivalence in the binary case. However, in [12] Kenza Guenda (Corresponding Author); Faculty of Mathematics USTHB, University of Science and Technology of Algiers, Algeria (email: ken.guenda@gmail.com). T. Aaron Gulliver; Department of Electrical and Computer Engineering, University of Victoria, PO Box 1700, STN CSC, Victoria, BC, Canada V8W 2Y2 (email: agullive@ece.uvic.ca). 261 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 the authors showed that extending the support splitting algorithm to q ≥ 5 results in an exponential growth in complexity, which makes this approach impractical. In this paper, we study the equivalence problem for cyclic codes of length pr and quasi-cyclic codes of length prl over finite fields. We generalize the results of [6] (which are only for the special case p2), by explicitly giving the permutations by which two cyclic codes of prime power length are equivalent. Further, the set of Brand is extended to the class of quasi-cyclic codes of length prl. The remainder of this paper is organized as follows. In Section 2, some preliminary results are presented. Section 3 considers the equivalence of cyclic codes, in particular cyclic codes of length pr. Then in Section 4, the equivalence of quasi-cyclic codes of length prl is investigated. 2. Preliminaries Let C be a linear code of length n over the finite field of q elements, Fq, and σ a permutation of the symmetric group Sn, acting on {0,1, . . . ,n − 1}. For a code C, we associate another linear code σ(C) defined by σ(C) = {(xσ−1(0), . . . ,xσ−1(n−1)) ; (x0, . . .xn−1) ∈ C}. We say that the codes C and C′ are permutation equivalent if there exists a permutation σ ∈ Sn such that C′ = σ(C). The automorphism group of C is the subgroup of Sn given by Aut(C) = {σ ∈ Sn ;σ(C) = C}. A linear code C of length n over Fq is called quasi-cyclic of index l or an l-quasi-cyclic code if its automorphism group contains the permutation T l given by T l : Zn −→ Zn i 7−→ i + l mod n, (1) where T : i 7→ i + 1 is the cyclic shift. This definition is equivalent to saying that for all c ∈ C we have T l(c) ∈ C. The index l of C is the smallest integer satisfying this property. It can easily be proven that l is a divisor of n. In the case l = 1, the code is called a cyclic code. This is a code with an automorphism group that contains the cyclic shift T. 3. Equivalence of cyclic codes In this section, we consider the permutation equivalence of cyclic codes. Later we will show that there is a very close link between the equivalence of some quasi-cyclic codes and cyclic codes. This provides further motivation to study the equivalence of cyclic codes. We begin with some well known results. Let n be a positive integer. The set of permutations AG(n) = {τa,b : a 6= 0,(a,n) = 1,b ∈ Zn} is the subgroup of Sn formed by the permutations defined as follows τa,b : Zn −→ Zn x 7−→ (ax + b) mod n. (2) The group AG(n) is called the group of affine transformations. The affine transformations Ma = τa,0, (3) 262 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 are called multipliers. The affine group AGL(1,p) is the group of affine transformations over Zp. For d ∈ Z∗p, the generalized multiplier µd ∈ Sp2 was defined in [6] as follows. Let k ∈ Zp2 and k = i + jp for some 0 ≤ i,j ≤ p−1, so that kµd = (id) mod p + pj. Then from Palfy ([10]) and Alspach and Parson ([1]), we have the following results. Theorem 3.1. [6, Theorem 1] Let C and C′ be cyclic codes of length n over a finite field. Suppose one of the following holds for n: (i) gcd(n,φ(n)) = 1 or n = 4, or (ii) n = pr,p > r are primes and the p-Sylow subgroup of the automorphism group of C has order p. Then C and C′ are equivalent by a multiplier. In the case n = p2, Huffman et al. ([6]) gave the following result. Theorem 3.2. [6, Theorem 3.1] Let C and C′ be cyclic codes of length p2 with p an odd prime, where T ∈ Aut(C) and T ∈ Aut(C′). Then if C and C′ are equivalent, they are equivalent by a multiplier or a generalized multiplier times a multiplier. For n = pr, r > 2 the equivalence of cyclic codes of length n is very complex, but in the next section this problem is partially solved. 3.1. Equivalence of cyclic codes of length pr Let C be a cyclic code of length pr, p an odd prime and r > 1. Further let T be the cyclic shift modulo pr and P a p-Sylow subgroup of Aut(C). The following subset of Spr was introduced by Brand ([3]) H(P) = {σ ∈ Spr|σ−1Tσ ∈ P}. The set H(P) is well defined since 〈T〉 is a subgroup of Aut(C) of order pr, so it is a p-group of Aut(C). From Sylow’s Theorem, there exists a p-Sylow subgroup P of Aut(C) such that 〈T〉 ≤ P . Furthermore, in some cases the set H(P) is a group. Lemma 3.3. [3, Lemma 3.1] Let C and C′ be cyclic codes of length pr, and P be a p-Sylow subgroup of Aut(C) which contains T. Then C and C′ are equivalent if and only if C and C′ are equivalent by an element of H(P). Lemma 3.3 shows the importance of having information on the p-Sylow subgroup of Aut(C). The following results provide some of this information. Proposition 3.4. [4, Proposition 9] Let C be a cyclic code of length pr with r > 1, and Mq be the multiplier defined by Mq(i) = iq mod pr. Then the group Aut(C) contains the subgroup K = 〈T,Mq〉 of order prordpr (q). Let pl, l ≥ r, be the p-part of the order of K. Then a p-Sylow subgroup P of Aut(C) has order ps such that l ≤ s ≤ pr−1 + pr−2 + · · ·+ 1. Now we define the sets of Brand. Let p be an odd prime. For n < p, we define the following subsets of Spr Qn = {f : Zpr → Zpr|f(x) = n∑ i=0 aix i,ai ∈ Zpr for each i,(p,a1) = 1, and pr−1 divides ai for i = 2,3, . . . ,n}. 263 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 Qn1 = {f ∈ Q n|f(x) = n∑ i=0 aix i, with a1 ≡ 1 mod pr−1}. The sets Qn and Qn1 are subgroups of Spr [3, Lemma 2.1]. Note that Q 1 = AG(pr). Lemma 3.5. Let C be a cyclic code of length pr where p is odd and m > 1. Let P be a p-Sylow subgroup of Aut(C) which contains T. If 1 ≤ n < p, then: (i) |Qn| = (p−1)p2r+n−2 and |Qn1 | = pr+n, (ii) AG(pr) = NSpr (〈T〉) ⊂ H(P), (iii) Qn+1 = H(Qn1 ), (iv) NSpr (Q n 1 ) = Q n+1. Proof. For part (i), from [3, Lemma 3.2] we have the map (a0, . . . ,an) −→ f where f(x) = ∑n i=0 aix i is injective if n < p − 1. Thus in Qn, the coefficient a0 can take pr different values, and a1 can take pr−1(p−1) values. For 2 ≤ i ≤ n, ai can take p values. From these results we have |Qn| = p2r+n−2(p−1). For Qn1 , the coefficient of a0 can take p r different values, and ai for 1 ≤ i ≤ n can take p values, so that |Qn1 | = pr+n. Now we prove that AG(pr) = NSpr (〈T〉). Let σ be an element of NSpr (〈T〉). Then there is a j ∈ Zn\{0} such that σTσ−1 = Tj, or equivalently σT = Tjσ. Hence σT(0) = σ(1) = Tjσ(0) = σ(0)+j and σT(1) = σ(1) +j = σ(0) + 2j, so that σ(k) = σ(0) +kj for any k ∈ Zn. Then (j,n) = 1 follows from the fact that the order of T equals the order of Tj. The last inclusion is obvious. Part (iii) follows from [3, Lemma 3.7]. For part (iv), we begin with the ≤ condition. Let h ∈ NSpr (Q n 1 ) and g = h −1Th. As T ∈ Qn1 , it must be that g ∈ Qn1 . Since the order of g is equal to the order of T (which is pr), from [3, Lemma 3.6] there exists f ∈ Qn+1 such that f−1gf = T , so then f−1h−1Thf = T. The only elements of Spr which commute with T (a complete cycle of length pr), are the powers of T . Thus hf = Tj for some j. Since Qn+1 is a subgroup of Spr and 〈T〉≤ Qn+1, h ∈ Qn+1, and hence NSpr (Q n 1 ) ≤ Qn+1. Now consider the ≥ condition. Let g ∈ Qn+1 where g(x) = ∑n+1 i=0 gix i with p - g1 and pr−1|gi for 2 ≤ i ≤ n. Further, let h ∈ Qn1 , where h(x) = ∑n i=0 hix i with h1 ≡ 1 mod pr−1 and pr−1|hi for 2 ≤ i ≤ n. We have hg(x) = n∑ i=0 hi  n+1∑ j=0 gjx j  i = h0 + h1 n+1∑ i=0 gjx j + n∑ i=2 hi  n+1∑ j=0 gjx j  i . Since pr−1|hi, for i ≥ 2 and pr−1|gj for j ≥ 2, any terms in ∑n i=2 hi (∑n+1 j=0 gjx j )i involving gj for j ≥ 2 vanish modulo pr, so that hg(x) = h0 + h1 n+1∑ j=0 gjx j + n∑ i=2 hi (g0 + g1x) i . By [3, Lemma 2.1] g−1(x) = n+1∑ i=1 bix i, with b1 = g −1 1 and bi = −gig −(i+1) 1 for 2 ≤ j ≤ n + 1. (4) We now determine g−1hg in order to prove that it is in Qn1 . This is given by g−1hg(x) = n+1∑ k=1 bk  h0 + h1 n+1∑ j=0 gjx j + n∑ i=2 hi(g0 + g1x) i −g0  k 264 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 = b1  h0 + h1 n+1∑ j=0 gjx j + n∑ i=2 hi (g0 + g1x) i −g0   + n+1∑ k=2 bk  h0 + h1 n+1∑ j=0 gjx j + n∑ i=2 hi(g0 + g1x) i −g0  k. As pr−1|gj for j ≥ 2, hence pr−1|bk for k ≥ 2. Furthermore, we have pr−1|hi for i ≥ 2, and thus g−1hg(x) = b1  h0 + h1 n+1∑ j=0 gjx j + n+1∑ j=0 hi(g0 + g1x) i −g0   + n+1∑ k=2 bk (h0 + h1 (g0 + g1x)−g0) k . Let g−1hg(x) = ∑n+1 r=0 crx r, and note that cn+1 = b1h1gn+1 + bn+1(h1g1)n + 1. Then replacing the bi with their values from (4), we obtain cn+1 = g −1 1 h1gn+1 −gn+1g −(n+2) 1 h n+1 1 g n+1 1 = g −1 1 h1(gn+1 −gn+1h n 1 ). As h1 ≡ 1 mod pr−1, we have that hn1 ≡ 1 mod pr−1. In addition, as pr−1|gn+1, it must be that gn+1hn1 ≡ gn+1 mod p r. Therefore, cn+1 = 0, and pr−1|ci for 2 ≤ i ≤ n. Then we only need to show that c1 ≡ 1 mod pr−1. As gj ≡ 0 mod pr−1 for j ≥ 2, hi ≡ 0 mod pr−1 for i ≥ 2, and bk ≡ 0 mod pr−1 for k ≥ 2, so then c1 ≡ b1h1g1 mod pr−1. Finally, since b1 = g−11 , we have that c1 ≡ h1 ≡ 1 mod p r−1. Next, we require the following theorems which characterize some p subgroups of Spr . Theorem 3.6. [4, Theorem 10] Let n be a positive integer less than p− 1. If P is a p subgroup of Spr with Qn1 � P ≤ Qn+1, then P = Q n+1 1 . Further, the group Q 1 1 is a normal subgroup of Q 1 and is the unique p subgroup of Spr of order pr+1 which contains T. Theorem 3.7. [4, Theorem 11] Let G be a subgroup of Spr and P a p-Sylow subgroup of G of order ps such that T ∈ P. Then the following hold: (i) if s = r, then P = 〈T〉, (ii) if r < s ≤ p + r −1, then we have P = Qs−r1 . Corollary 3.8. Let C and C′ be two cyclic codes of length pr, and let P be a p-Sylow subgroup of Aut(C) such that T ∈ P. If |P| = ps and s ≤ p + r − 1, then C and C′ can be equivalent only under the action of a permutation of the following subgroups of Spr : (i) AG(pr) if s = r, (ii) Qs−r+1 if s > r. Proof. The result follows from Lemmas 3.3 and 3.5, and Theorem 3.7. Remark 3.9. Since each affine transformation can be written as the product of a power of T and a multiplier, and T ∈ Aut(C), we must have τa,b ∈ C whenever Ma ∈ C. Hence from Corollary 3.8, if s = r then two cyclic codes of length pr are equivalent if and only if they are equivalent by a multiplier. In order to solve the equivalence problem for cyclic codes, we need the p-Sylow subgroup of Aut(C). To determine this, for i ≤ i ≤ p−1 consider the polynomial fi ∈ Qi1 defined by fi(x) = x + p r−1(x + x2 + . . . + xi). 265 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 Theorem 3.10. Let G be a subgroup of Spr with a p-Sylow subgroup P which contains T. Then the following hold: (i) if there is no fi ∈ G, then P = 〈T〉, (ii) if I is the largest value of i such that fi ∈ G and I ≤ p−2, then P = QI1. Proof. If there is no fi ∈ G, then there is no fi in P . If |P | = pr, we can take P = 〈T〉, but then from Theorem 3.6 any p-Sylow subgroup of ps, s > r, must contain Q11, which is impossible. Assume that I is the largest i such that fi ∈ G and I ≤ p− 2. Let P be a p-Sylow subgroup of G of order s, and s be such that I + r ≤ s < p + r − 1. From Theorem 3.7, we have that a p-Sylow subgroup of any subgroup of G ≤ Spr which contains T has order ps with m < s ≤ p + r − 1. Then we have P = Qs−r1 , so that s− r = I. Now if s ≤ I + r ≤ p + r − 1, we have from Theorem 3.7 that P = Qs−r1 , so Q I 1 ∩G ≤ Q s−r 1 . The assumption on I gives I = s−r. Assume now that s > p + r−1. Since I ≤ p−2, we have that s > p + r−1 > r + I. We will prove that this case cannot occur. Further, as T = f1 ∈ Q11, from Theorem 3.6 Q11 is the unique subgroup of Spr of order pr+1 which contains T , so that Q11 � P . Since Q 1 1 � Q 2 1, it must be that Q 1 1 � Q 2 1 ∩P ≤ Q2. Hence we have that Q21∩P = Q21, which gives Q21 ≤ P . Using the same approach for 2 ≤ i ≤ I, we obtain QI ≤ P . The assumption on s gives that QI � P , so QI1 � Q I+1 1 ∩P ≤ Q I+1 (QI+1 can be considered as it was assumed that I ≤ p− 2). Hence from Theorem 3.6, we obtain that QI+11 ∩P = Q I+1 1 , which contradicts the assumption on I. This theorem suggests the following algorithm for I ≤ p−2. Algorithm A: Let p be an odd prime and C and C′ be two cyclic codes of length pm. Then the equivalence of C and C′ can be determined as follows. Step 1: Find the order of the p-Sylow subgroup of Aut(C) as follows. Find the largest I such that fI ∈ Aut(C), and set s = I + r. Step 2: Find f ∈ QI+1 such that C′ = fC. Remark 3.11. To find the required I in Algorithm A we can use (for example), a binary search which requires checking at most dlog2(p−1)e+1 of the fi. Furthermore, the cardinality of QI+1 is (p−1)p2r+I−2. This proves that the algorithm has polynomial time complexity. 4. Equivalence of quasi-cyclic codes In this section, we characterize the equivalence problem for quasi-cyclic codes. Consider the cycles σi = (i, i + l, i + 2l, . . . , i + (m−1)l) for 0 ≤ i ≤ l−1. The cycles σi have order m and satisfy T l = σ0 . . .σl−1. (5) This gives that |(T l)| = lcm(|σ0|, . . . , |σl−1|) = m. Proposition 4.1. Let n = lm with (m,l) = 1, and 〈T l〉 be the subgroup of Sn generated by the permu- tation T l. Therefore the normalizer of 〈T l〉 in Sn contains the following groups: (i) Q = 〈σ0, . . . ,σl−1,T〉, (ii) AG(n). Proof. It is obvious that T ∈ NSn(〈T l〉). As the cycles in (5) are pairwise disjoint, it must be that σ0 . . .σl−1 = T l. Furthermore, as the cycles σi are disjoint, we have that σ −1 i T lσi = T l. 266 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 We consider the affine transformation τa,b ∈ AG(n), which shows that τa,b ∈ NSn(〈T l〉) is equivalent to proving the existence of an α ∈ N∗ such that τa,bT lτ−1a,b = T lα. The permutation τa,b can be decomposed as τa,b = τ1,bτa,0. Then combining this decomposition with (5), we obtain the following equality τa,bT lτ−1a,b = τ1,bτa,0σ0 . . .σl−1τ −1 a,0τ −1 1,b . (6) A well known result [5, Lemma 5.1] gives that if σ = σ0 . . .σl−1 is a product of disjoint cycles and S is a permutation from Sn, then SσS−1 = S(σ0)S(σ1) . . .S(σl−1), where S(σi) = (S(σ1i), . . . ,S(σmi)) for the cycle σi = (σ1i, . . . ,σmi). For ra = a mod l, we obtain that τa,0(σi) = σaira. This gives τa,0(σ0)τa,0(σ1) . . .τa,0(σl−1) = σ a 0σ a ra . . .σ a ra(l−1) = T la. For rb = b mod l, we obtain τ1,bσiτ −1 1,b = τi+rb, and hence τ1,bT lτ−11,b = l−1∏ i=0 σi+rb = T l. Finally, we obtain τa,bT lτ−1a,b = τ1,bτa,0T lτ−1a,0τ −1 1,b = τ1,bT laτ−11,b = T la. This gives α = a, so that τa,b ∈ NSn(< T l >). 4.1. Quasi-cyclic codes of length prl We now consider quasi-cyclic codes of length n = prl with p a prime number such that (p,l) = (p,q) = 1. In this case, 〈T l〉 ≤ Aut(C) is a subgroup of order pr. Hence it is contained in a p-Sylow subgroup P . Lemma 4.2. Let C and C′ be two quasi-cyclic codes of length n = prl, and P be a p-Sylow subgroup of Aut(C) such that T l ∈ P. Then C and C′ are equivalent only if they are equivalent by the elements of the set H′(P) = {σ ∈ Sn|σ−1T lσ ∈ P}. Proof. Since C and C′ are equivalent, there exists a permutation σ ∈ Sn such that C′ = σ(C). This gives the following relationship between the automorphism groups Aut(C) and Aut(C′) Aut(C′) = σAut(C)σ−1. (7) Let P be a Sylow subgroup of Aut(C). Then from (7) we have that σPσ−1 = P ′′ is a Sylow p-subgroup of Aut(C′). From Sylow’s Theorem, there exists τ ∈ Aut(C′) such that τP ′τ−1 = P ′′ . We can assume that 〈T l〉 ≤ P ′ since 〈T l〉 is a p-group. Let γ = τ−1σ, then γ is an isomorphism between C and C′ because γ(C) = τ−1σ(C) = τ−1C′ = C′. Then γ−1T lγ = σ−1τT lτ−1σ ∈ σ−1P ′′ σ = P as τT lτ−1 ∈ τP ′τ−1, and hence γ ∈ H′(P). It is obvious that if P = 〈T l〉, then we have NSn(〈T l〉) = H′(〈T l〉). The following proposition gives other properties of H′(P). 267 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 Proposition 4.3. Let P be a Sylow p-subgroup of Aut(C). Then the group H′(P) has the following properties: (i) if P = 〈T l〉, then NSn(〈T l〉) = H′(〈T l〉), (ii) NSn(〈T l〉) ⊂ H′(P), (iii) NSn(P) ⊂ H′(P). Proof. The first property is obtained from the definition of H′(P). To prove the second property we consider a permutation σ in NSn(〈T l〉), the normalizer of 〈T l〉 in Sn. Then permutation σ satisfies σ−1〈T l〉σ = 〈T l〉⊂ P . Hence, we have that NSn(〈T l〉) ⊂ H′(P). (8) Now consider NSn(P), the normalizer of P in Sn. The permutation σ ∈ NSn(P) shows that σ−1Pσ = P . Thus for T l ∈ P we have σ−1T lσ ∈ P , so that NSn(P) ⊂ H ′(P). (9) Corollary 4.4. The set H′(P) satisfies AG(n) ⊂ H′(P). Proof. From Proposition 4.1 we have AG(n) ≤ NSn(〈T l〉). Furthermore, Proposition 4.3 gives that NSn(〈T l〉) ⊂ H′(P), which completes the proof. From Corollary 4.4, we have AG(n) ⊂ H′(P). As the multipliers are elements of AG(n), this proves that two quasi-cyclic codes of length n can be equivalent by a multiplier. This extends the results on 1-generator quasi-cyclic codes in [7]. References [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. 268 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 http://dx.doi.org/10.1016/0012-365X(79)90011-6 http://dx.doi.org/10.1016/0012-365X(79)90011-6 http://www.ams.org/mathscinet-getitem?mr=2858409 http://www.ams.org/mathscinet-getitem?mr=2858409 http://dx.doi.org/10.1007/BF01789458 http://dx.doi.org/10.1007/s10801-012-0399-4 http://dx.doi.org/10.1007/s10801-012-0399-4 http://dx.doi.org/10.1016/0097-3165(93)90043-8 http://dx.doi.org/10.1016/0097-3165(93)90043-8 https://doi.org/10.1109/TIT.2005.850142 https://doi.org/10.1109/TIT.2005.850142 https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19780016269.pdf#page=123 https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19780016269.pdf#page=123 http://dx.doi.org/10.1016/S0195-6698(87)80018-5 http://dx.doi.org/10.1016/S0195-6698(87)80018-5 K. Guenda, T. A. Gulliver / J. Algebra Comb. Discrete Appl. 4(3) (2017) 261–269 [11] N. Sendrier, Finding the permutation between equivalent linear codes: The support splitting algo- rithm, IEEE Trans. Inform. Theory 46(4) (2000) 1193–1203. [12] N. Sendrier, D.E. Simos, How easy is code equivalence over Fq?, in Proc. Int. Workshop on Coding Theory and Crypt., Bergen, Norway, 2013. [13] N. Sendrier, D. E. Simos, The hardness of code equivalence over Fq and its application to code- based cryptography, in P. Gaborit (Ed.), Post-Quantum Cryptography, Springer Lecture Notes in Computer Science 7932, Limoges, France (2013) 203–216. 269 http://orcid.org/0000-0002-1482-7565 http://orcid.org/0000-0001-9919-0323 https://doi.org/10.1109/18.850662 https://doi.org/10.1109/18.850662 https://hal.inria.fr/hal-00790861/ https://hal.inria.fr/hal-00790861/ http://dx.doi.org/10.1007/978-3-642-38616-9_14 http://dx.doi.org/10.1007/978-3-642-38616-9_14 http://dx.doi.org/10.1007/978-3-642-38616-9_14 Introduction Preliminaries Equivalence of cyclic codes Equivalence of quasi-cyclic codes References