ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.327368 J. Algebra Comb. Discrete Appl. 4(3) • 235–246 Received: 9 June 2016 Accepted: 7 December 2016 Journal of Algebra Combinatorics Discrete Structures and Applications Enumeration of extended irreducible binary Goppa codes of degree 2m and length 2n + 1 Research Article Augustine I. Musukwa, Kondwani Magamba, John A. Ryan Abstract: Let n be an odd prime and m > 1 be a positive integer. We produce an upper bound on the number of inequivalent extended irreducible binary Goppa codes of degree 2m and length 2n +1. Some examples are given to illustrate our results. 2010 MSC: 11T71, 68R99 Keywords: Goppa codes, Extended codes, Irreducible Goppa codes, Equivalent codes 1. Introduction This paper focuses on the class of codes called Goppa codes. It was V. D. Goppa who, in the early 1970’s, described this class of codes. Goppa codes form a subclass of alternant codes which has an interesting algebraic structure [6]. Goppa codes are said to contain good parameters. This might be the reason why they are of high practical value. The McEliece cryptosystem and the Niederreiter cyptosystem are examples of public-key cryptosystems in cryptography which make use of Goppa codes. The McEliece cryptosystem is believed to be a cryptosystem which may have potential to withstand attack by quantum computers [3]. As this cryptosystem chooses a Goppa code at random as its key, knowledge of the number of inequivalent Goppa codes for fixed parameters may facilitate in the evalu- ation of the security of such a cryptosystem. This paper seeks to find a tight bound on the number of inequivalent extended irreducible binary Goppa codes of degree 2m. The count employs the tools which were used to count the non-extended versions (see [8]). Augustine I. Musukwa (Corresponding Author), John A. Ryan; Mzuzu University, P/Bag 201, Luwinga, Mzuzu 2, Malawi (email: augulela@yahoo.com, jar@mzuzu.org). Kondwani Magamba; Malawi University of Science and Technology, P.O. Box 5196, Limbe, Malawi (email: kmagamba@must.ac.mw). 235 http://orcid.org/0000-0001-8792-6954 http://orcid.org/0000-0003-4025-9802 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 2. Preliminaries As this paper is focused on irreducible Goppa codes we begin with the definition of irreducible Goppa codes. Definition 2.1. Let q be a power of a prime number and g(z) ∈ Fqn [z] be irreducible of degree r. Let L = Fqn = {ζi : 0 ≤ i ≤ qn − 1}. Then an irreducible Goppa code Γ(L,g) is defined as the set of all vectors c = (c0,c1, ...,cqn−1) with components in Fq which satisfy the condition qn−1∑ i=0 ci z − ζi ≡ 0 (mod g(z)). The set L is called the defining set and its cardinality defines the length of Γ(L,g). The polynomial g(z) is called the Goppa polynomial. If the degree of g(z) is r then the code is called an irreducible Goppa code of degree r. The roots of g(z) are contained in Fqnr \ Fqn. If α is any root of g(z) then it completely describes Γ(L,g). Chen in [2] described a parity check matrix H(α) for Γ(L,g) which is given by H(α) = ( 1 α− ζ0 1 α− ζ1 · · · 1 α− ζqn−1 ) . We will sometimes denote this code by C(α). We next give the definition of extended irreducible Goppa codes. Definition 2.2. Let Γ(L,g) be an irreducible Goppa code of length qn. Then the extended code Γ(L,g) is defined by Γ(L,g) = {(c0,c1, ...,cqn ) : (c0,c1, ...,cqn−1) ∈ Γ(L,g) and ∑qn i=0 ci = 0}. Next we define the set which contains all the roots of all possible g(z) of degree r. Definition 2.3. We define the set S = S(n,r) as the set of all elements in Fqnr of degree r over Fqn. Any irreducible Goppa code can be defined by an element in S. The converse is also true, that is, any element in S defines an irreducible Goppa code. Since an irreducible Goppa code Γ(L,g) is determined uniquely by the Goppa polynomial g(z), or by a root α of g(z), we define the mapping below. (For further details, see [2].) Definition 2.4. The relation πζ,ξ,i defined on S by πζ,ξ,i : α 7→ ζαq i + ξ for fixed i,ζ,ξ where 1 ≤ i ≤ nr, ζ 6= 0,ξ ∈ Fqn is a mapping on S. This map sends irreducible Goppa codes into equivalent codes and we generalise this as follows: Theorem 2.5. (Ryan, [8]): If α and β are related by an equation of the form α = ζβq i + ξ for some ζ 6= 0,ξ ∈ Fqn, then the codes C(α) and C(β) are equivalent. The map in Definition 2.4 can be broken up into the composition of two maps as follows: 1. πζ,ξ defined on S by πζ,ξ : α 7→ ζα + ξ and 2. the map σi : α 7→ αq i , where σ denotes the Frobenius automorphism of Fqnr leaving Fq fixed. 236 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 From these two maps we define the following sets of mappings. Definition 2.6. Let H denote the set of all maps {πζ,ξ : ζ 6= 0,ξ ∈ Fqn}. Definition 2.7. Let G denote the set of all maps {σi : 1 ≤ i ≤ nr}. The sets of maps H and G together with the operation composition of maps both form groups which act on S. Definition 2.8. The action of H on S induces orbits denoted by A(α) where A(α) = {ζα + ξ : ζ 6= 0,ξ ∈ Fqn}. We refer to A(α) as an affine set containing α where α is an element of degree r over Fqn and ζ,ξ ∈ Fqn. Since ζ 6= 0,ξ ∈ Fqn then to form the set A(α) the number of choices for ζ is qn−1 and ξ has qn choices and so |A(α)| = qn(qn − 1). Definition 2.9. Let A denote set of all affine sets, i.e., A = {A(α) : α ∈ S}. Next, we define a mapping on S which sends extended irreducible Goppa codes into equivalent extended irreducible Goppa codes. Definition 2.10. The relation πζ1,ζ2,ξ1,ξ2,i defined on S by πζ1,ζ2,ξ1,ξ2,i : α 7→ ζ1α qi + ξ1 ζ2αq i + ξ2 fixed i,ζj,ξj where 0 ≤ i ≤ nr, ζj,ξj ∈ Fqn, j = 1, 2 and ζ1ξ2 6= ζ2ξ1 is a mapping on S. Since the scalars ζj and ξj are defined up to scalar multiplication, we may assume that ζ2 = 1 or ξ2 = 1 if ζ2 = 0. We have the following generalisation: Theorem 2.11. (Berger, [1]): If πζ1,ζ2,ξ1,ξ2,i(α) = β then C(α) is equivalent to C(β). The map in Definition 2.10 can be broken up into the composition of two maps as follows: 1. the map πζ1,ζ2,ξ1,ξ2 defined on S by πζ1,ζ2,ξ1,ξ2 : α 7→ ζ1α+ξ1 ζ2α+ξ2 , and 2. the map σi : α 7→ αq i , where σ denotes the Frobenius automorphism of Fqnr leaving Fq fixed. From these two maps we give the following two definitions. Definition 2.12. Let F denote the set of all maps {πζ1,ζ2,ξ1,ξ2 : ζj,ξj ∈ Fqn, j = 1, 2 and ζ1ξ2 6= ζ2ξ1}. F forms a group under the operation of composition of maps which acts on S. Definition 2.13. Let α ∈ S. Then the orbit in S containing α under the action of F is O(α) = {ζ1α+ξ1 ζ2α+ξ2 : ζj,ξj ∈ Fqn,j = 1, 2 and ζ1ξ2 − ζ2ξ1 6= 0}. The cardinality of O(α) is found in [10] and we state it in the theorem: Theorem 2.14. For any α ∈ S, |O(α)| = q3n −qn = (qn − 1)(qn)(qn + 1). Definition 2.15. Let OF denote the set of all orbits in S under the action of F, i.e., OF = {O(α) : α ∈ S}. Observe that OF is a partition of the set S. Note that G acts on the set OF . 237 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 Remark 2.16. From now on we take q = 2. It is shown in [9] that each of the sets O(α) in OF can be partitioned into 2n + 1 sets. The theorem below provides more details. Theorem 2.17. O(α) = A(α) ∪A( 1 α ) ∪A( 1 α+1 ) ∪A( 1 α+ξ1 ) ∪A( 1 α+ξ2 ) ∪ ·· ·∪A( 1 α+ξ2n−2 ) where F2n = {0, 1,ξ1,ξ2, ...,ξ2n−2}. Observe that the sets OF and A are different. OF is a partition on S and also A is a partition on S. The number of elements in A is 2n + 1 times the number of elements in OF , i.e., |A| = (2n + 1) ×|OF |. G also acts on A = {A(α) : α ∈ S}. 3. Counting extended irreducible binary Goppa codes of degree 2m 3.1. Technique of counting We wish to produce an upper bound on the number of inequivalent extended irreducible binary Goppa codes of degree r = 2m. We intend to achieve this by employing the tools developed for counting the non-extended versions. In counting the non-extended irreducible Goppa codes we consider the action of H on S. This gives orbits in S denoted by A(α) called affine sets. We then consider the action of G on the set A where A = {A(α) : α ∈ S}. The number of orbits in A under G gives us an upper bound on the number of inequivalent irreducible Goppa codes. Now to count extended irreducible Goppa codes we consider the action of F on S. This action induces orbits in S denoted by O(α). Next we consider the action of G on OF = {O(α) : α ∈ S}. The number of orbits in OF under G gives us an upper bound on the number of inequivalent extended irreducible Goppa codes. To find the number of orbits in A and OF we use the Cauchy Frobenius Theorem whose proof can be found in [4]. Since the Cauchy Frobenius Theorem is central in this paper we state it as follows. Theorem 3.1 (Cauchy Frobenius Theorem). Let E be a finite group acting on a set X. For any e ∈ E, let Xe denote the set of elements of X fixed by e. Then the number of orbits in X under the action of E is 1|E| ∑ e∈H |Xe|. 3.2. Cardinality of S In order to simplify our notation we denote all the factors of the degree 2m by 2i for 0 ≤ i ≤ m. Now to find the number of elements in S we use the lattice of subfields of F2nM , where M = 2m as done in [7]. Figure 1 shows the lattice of subfields of F2nM . Remark 3.2. In Figure 1 observe that the elements of degree 2m over F2n lie in F2n(2m) and F22m . So the number of elements of degree 2m in F2n(2m) is |S| = 2n(2 m) − 2n(2 m−1). 3.3. The number of fixed affine sets in A Note that the group G defined in Definition 2.7 is a cyclic group of order n2m, where n > 2 is prime, and it’s subgroups are all of the form 〈σk〉, where k is a factor of n2m. Further, note that G acts on A. In this section, we determine the G-orbits of this action. 238 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 F2n(2m) F 2n(2 m−1) F22m F 2n(2 m−2) F22(m−1) ... ... ... F22n F222 F2n F22 F2 Figure 1. We first need to know the number of affine sets A(α) which are in A. By Remark 3.2, |S| = 2n(2 m) − 2n(2 m−1). Since |A(α)| = 2n(2n − 1) then |A| = |S|/(2n(2n − 1)). The expected length of orbits in A under the action of G are all factors of n2m. The trivial subgroup 〈σn(2 m)〉, containing the identity, fixes every affine set in A. In the following subsections, we separately consider the remaining subgroups of G, i.e., 〈σn(2 m−1)〉, 〈σ2 m 〉, 〈σ2 m−1 〉, 〈σ2 s 〉 and 〈σn(2 s)〉 where 0 ≤ s < m− 1. 3.3.1. 〈σn(2 m−1)〉 a subgroup of G of order 2 Suppose the orbit in A under the action of G containing A(α) contains n(2m−1) affine sets, i.e, {A(α),σ(A(α)),σ2(A(α)), ...,σn(2 m−1)−1(A(α))}. Then A(α) is fixed by 〈σn(2 m−1)〉. That is σn(2 m−1)(A(α)) = A(α). So we have σn(2 m−1)(α) = α2 n(2m−1) = ζα + ξ for some ζ 6= 0,ξ ∈ F2n. So applying σn(2 m−1) for the second time we get α = σn(2 m)(α) = σn(2 m−1)(ζα + ξ) = ζ2 n(2m−1) α2 n(2m−1) + ξn(2 m−1) = ζα2 n(2m−1) + ξ = ζ(ζα + ξ) + ξ = ζ2α + (ζ + 1)ξ. We conclude that ζ = 1 as otherwise ζ 6= 1 would mean (1 − ζ2)α ∈ F2n contradicting the fact that α ∈ S. Now consider α2 n(2m−1) = α + ξ for some ξ 6= 0 ∈ F2n. Multiplying both sides by ξ−1 we get (ξ−1α)2 n(2m−1) = (ξ−1α) + 1. We may assume that α satisfies the equation x2 n(2m−1) + x + 1 = 0. (1) If α satisfies (1) then certainly all the 2n elements in the set {α + ξ : ξ ∈ F2n} also satisfy (1) while the remaining elements in A(α) do not satisfy (1). This follows because the equation (ζα + ξ)2 n(2m−1) = 239 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 ζα2 n(2m−1) + ξ = ζ(α + 1) + ξ = ζα + ζ + ξ = (ζα + ξ) + 1 holds if and only if ζ = 1. Hence if α satisfies (1) then A(α) contains precisely 2n roots of (1). We now find the number of elements of S which satisfy (1). We know that x2 n(2m−1) + x + 1 = 2n(2 m−1)−1∏ i=1 (x2 + x + βi) (2) where βi denotes all the elements of F2n(2m−1) which have trace 1 over F2 [5]. We know that there are precisely 2n(2 m−1)−1 such βi. Note that the trace function we are dealing with is from the field F2n(2m−1) to F2. So even if an element is in a proper subfield of F2n(2m−1), in calculating its trace we regard it as an element of F 2n(2 m−1). We further observe that if β ∈ F2n(2m−2), then TraceF 2n(2 m−1)|F2 (β) = 2 · TraceF 2n(2 m−2)|F2 (β). Since the characteristic is 2, then we conclude that none of the βi in the decomposition of x2 n(2m−1) +x+ 1 in (2) lie in F 2n(2 m−1). However 22 m−1−1 of the βi lie in F22m−1 and the remaining 2n(2 m−1)−1 − 22 m−1 lie in F 22 m−1n (not in any of its subfields). Furthermore, all the quadratic factors on the right hand side of (2) are irreducible over F 2n(2 m−1). This is due to linearity of the trace function and the fact that Trace(βi) = 1 for each βi. The 22 m−1−1 quadratic equations corresponding to the βi in F22m−1 have F22m as their splitting field while the remaining 2 n(2m−1)−1 − 22 m−1−1 quadratic equations have F2n(2m) as their splitting field. So all the 2n(2 m−1) roots lie in S. Conversely if α ∈ S satisfies (∗) then A(α) is fixed under 〈σn(2 m−1)〉. We may conclude that there are precisely 2 n(2m−1) 2n = 2n(2 m−1−1) affine sets A(α) fixed under 〈σn(2 m−1)〉. 3.3.2. 〈σn(2 s)〉 a subgroup of G of order 2m−s Suppose the orbit in A under the action of G containing A(α) contains n(2s) affine sets where 0 ≤ s < m− 1. As in Subsection 3.3.1, we have A(α) fixed by 〈σn(2 s)〉 and σn(2 s)(α) = α2 n(2s) = ζα + ξ for some ζ 6= 0,ξ ∈ F2n. Applying σn(2 s) for 2m−s times to α we obtain α = σn(2 m)(α) = ζ2 m−s α + (ζ2 m−s−1 + ζ2 m−s−2 + · · · + ζ2 + ζ + 1)ξ. We conclude that ζ2 m−s = 1 otherwise ζ2 m−s 6= 1 would mean (1 −ζ2 m−s )α ∈ F2n contradicting the fact that α ∈ S. The possibilities are that ζ2 m−s = 1, ζ2 m−s−1 = 1, ζ2 m−s−2 = 1, · · · , ζ2 2 = 1, ζ2 = 1 or ζ = 1. Since 2n − 1 is odd then it is not divisible by 2d where 1 ≤ d ≤ m−s. Hence ζ2 m−s = 1 implies ζ = 1. So α2 n(2s) = α + ξ for some ξ 6= 0 ∈ F2n. If we multiply both sides by ξ−1 we obtain (ξ−1α)2 n(2s) = (ξ−1α) + 1. We assume that α satisfies the equation x2 n(2s) + x + 1 = 0. Using similar argument to the one in Subsection 3.3.1, all roots of x2 n(2s) + x + 1 = 0 lie in F 22 s+1 and F 2n(2 s+1) (and not in S). We conclude that there is no affine set A(α) fixed under 〈σn(2 s)〉. 3.3.3. 〈σ2 m 〉 a subgroup of G of order n Suppose the orbit in A under the action of G containing A(α) contains 2m affine sets. Then A(α) is fixed under 〈σ2 m 〉. In [8], it is proved that the number of affine sets fixed by 〈σr〉 is |S(1,r)|/(q(q − 1)). Hence the number of affine sets fixed by 〈σ2 m 〉 is |S(1, 2m)|/(2(2 − 1)) = (22 m − 22 m−1 )/2 = 22 m−1 − 22 m−1−1. 3.3.4. 〈σ2 m−1 〉 a subgroup of G of order 2n Suppose the orbit in A under the action of G containing A(α) contains 2m−1 affine sets. Then A(α) is fixed by 〈σ2 m−1 〉. So we have σ2 m−1 (α) = α2 2m−1 = ζα + ξ for some ζ 6= 0,ξ ∈ F2n. But if A(α) is fixed under 〈σ2 m−1 〉 then it is also fixed under 〈σ2 m 〉 since 〈σ2 m 〉 ⊂ 〈σ2 m−1 〉. So A(α) contains a fixed point. That is A(α) contains some elements which satisfy x2 2m = x and these elements are in 240 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 F22m \ F22m−1 . Assume α ∈ F22m \ F22m−1 then applying σ 2m−1 twice to α we obtain α = α2 2m = ζ2 2m−1 (ζα + ξ) + ξ2 2m−1 = ζ2 2m−1 +1α + ζ2 2m−1 ξ + ξ2 2m−1 = ζ2 2m−1 +1α + ζ2 2m−1 ξ + ξ2 2m−1 . We conclude that ζ2 2m−1 +1 = 1 otherwise ζ2 2m−1 +1 6= 1 would mean (1−ζ2 2m−1 +1)α ∈ F2n contradicting the fact that α is of degree 2m. Now we show that 22 m−1 + 1 is relatively prime to 2n − 1. We simply show that any number of the form 2d + 1 is relatively prime to 2n − 1. That is it suffices to show that (2d + 1, 2n − 1) = 1. We show this by contradiction. Assume that (2d + 1, 2n − 1) 6= 1. That is there must be some odd prime p which divides both 2d + 1 and 2n − 1. This implies that 2n ≡ 1 (mod p) and 2d ≡ −1 (mod p). So 2d ≡ −1 (mod p) implies 22d ≡ (−1)2 = 1 ≡ 2n (mod p). Thus n ≡ 2d (mod (p− 1)). Since p− 1 is even then n is also even. This establishes a contradiction since n is an odd prime. Hence (2d + 1, 2n − 1) = 1 for odd n. It follows that (22 m−1 + 1, 2n − 1) = 1 from which we conclude that ζ2 2m−1 +1 = 1 implies ζ = 1. So α = ζ2 2m−1 +1α + ζ2 2m−1 ξ + ξ2 2m−1 implies α = α + ξ + ξ2 2m−1 . Clearly, ξ is in the intersection of the fields of order 22 m−1 and 2n. Since (2m−1,n) = 1 then ξ is 0 or 1. But ξ = 0 is impossible since this would mean that α ∈ F 22 m−1 . So ξ must be 1. So we have α2 2m−1 = α + 1. Clearly α satisfies the equation x2 2m−1 + x + 1 = 0. (3) Observe that α + 1 also satisfies (3) and one can easily check that these are the only elements in A(α) which satisfy (3). Using an argument similar to the one in Subsection 3.3.1, all the 22 m−1 roots of x2 2m−1 + x + 1 lie in F22m \ F22m−1 . Hence we conclude that there are 2 2m−1−1 affine sets fixed under 〈σ2 m−1 〉. 3.3.5. 〈σ2 s 〉 a subgroup of G of order n(2m−s) Suppose the orbit in A under the action of G containing A(α) contains 2s affine sets where 0 ≤ s < m − 1. Then A(α) is fixed by 〈σ2 s 〉 and σ2 s (α) = α2 2s = ζα + ξ for some ζ 6= 0,ξ ∈ F2n. As in Subsection 3.3.4, if A(α) is fixed under 〈σ2 s 〉 then it is also fixed under 〈σ2 m 〉 since 〈σ2 m 〉 ⊂ 〈σ2 s 〉. Assume α ∈ F22m \F22m−1 then applying σ 2s to α for 2m−s times we obtain α = α2 2m = ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s +22 s +1α + ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s +22 s ξ + ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s ξ2 2s + ζ2 n·2s +2(n−1)·2 s +···+23·2 s ξ2 2·2s + · · · + ζ2 n·2s +2(n−1)·2 s ξ2 (n−2)·2s + ζ2 n·2s ξ2 (n−1)·2s + ξ2 n·2s (4) where n = 2m−s − 1. Observe that ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s +22 s +1 must be equal to 1 otherwise it would mean that (1 − ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s +22 s +1)α ∈ F2n contradicting the fact that α is of degree 2m. We now show that 2n·2 s +2(n−1)·2 s +· · ·+23·2 s +22·2 s +22 s +1 and 2n−1 are coprime. First observe that 241 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 2n·2 s +2(n−1)·2 s +· · ·+23·2 s +22·2 s +22 s +1 = (22 s(n+1)−1)/(22 s −1) = (22 m −1)/(22 s −1). But (2m,n) = 1 so (22 m −1, 2n−1) = 1 from which we conclude that (2n·2 s +2(n−1)·2 s +· · ·+23·2 s +22·2 s +22 s +1, 2n−1) = 1. We can now conclude that ζ2 n·2s +2(n−1)·2 s +···+23·2 s +22·2 s +22 s +1 = 1 implies ζ = 1. Since ζ = 1 then (4) becomes α = α + ξ + ξ2 2s + ξ2 2·2s + · · · + ξ2 (n−2)2s + ξ2 (n−1)2s + ξ2 n·2s . It is clear that ξ is in the intersection of the fields of order 22 s and 2n. Since (2s,n) = 1 then ξ is 0 or 1. But ξ = 0 is impossible since this would mean that α ∈ F22s . So ξ must be 1. So we have α2 2s = α + 1. Clearly α satisfies the equation x2 2s + x + 1 = 0. Observe that α + 1 also satisfies the equation x2 2s + x + 1 = 0 and one can easily check that these are the only elements in A(α) which satisfy x2 2s + x + 1 = 0. Using similar argument to the one in Subsection 3.3.1, all the 22 s roots of x2 2s + x + 1 lie in F22s−1 not in S. Hence we conclude that there is no affine set fixed under 〈σ2 s 〉. 3.4. The number of orbits in A under the action of G We use Table 1 to present the information in Section 3.3. This table shows the number of affine sets which are fixed under the action of various subgroups of G. The subgroups which do not fix any affine set are left out. The subgroups are listed in ascending order of the number of elements in the subgroup. So the first row is the subgroup 〈σn(2 m)〉 which is merely the trivial subgroup containing the identity. Column 3 lists the number of elements in subgroup which are not already counted in subgroups in the rows above it in the table. This is to avoid repetition when we multiply column 3 by column 4 in order to get the total number of fixed affine sets by the elements in G. Table 1. Subgroup Order of No. of elements No. of fixed Product of G Subgroup not in previous affine sets of columns subgroup 3 and 4 〈σ2 mn〉 1 1 2 n(2m)−2n(2 m−1) 2n(2n−1) 2n(2 m)−2n(2 m−1) 2n(2n−1) 〈σn(2 m−1)〉 2 1 2n(2 m−1−1) 2n(2 m−1−1) 〈σ2 m 〉 n n−1 22 m−1 −22 m−1−1 (n−1)(22 m−1 −22 m−1−1) 〈σ2 m−1 〉 2n n−1 22 m−1−1 (n−1)22 m−1−1 By the Cauchy Frobenius Theorem, the number of orbits in A under the action of G is (2n(2 m)−2n(2 m−1))/(2n(2n−1))+2n(2 m−1−1)+(n−1)×22 m−1 n(2m) . Remark 3.3. The number of orbits in A under the action of G gives us an upper bound on the number of irreducible Goppa codes. 3.5. The number of fixed O(α) in OF We are going to consider the action of G on OF so that we find the number of O(α)’s which are fixed in OF . This is done by acting all subgroups of G on OF . We begin by finding the number of elements in OF . By Remark 3.2, |S| = 2n(2 m) − 2n(2 m−1). Since |O(α)| = 2n(2n − 1)(2n + 1) then |OF | = |S| 2n(2n−1)(2n+1). Since G acts on OF and its cardinality is n(2m) then the expected lengths for the orbits in OF under the action of G are all the factors of n(2m). Every O(α) in OF is fixed by a trivial subgroup 〈σn(2 m)〉 containing the identity. As in Section 3.3, we consider the remaining subgroups of G, i.e., 〈σn(2 m−1)〉, 〈σ2 m−1 〉, 〈σ2 s 〉 and 〈σn(2 s)〉 where 0 ≤ s < m− 1. 242 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 3.5.1. 〈σn(2 m−1)〉 a subgroup of G of order 2 Suppose O(α) ∈ OF is fixed under 〈σn(2 m−1)〉. Then 〈σn(2 m−1)〉 acts on O(α) = A(α) ∪ A( 1 α ) ∪ A( 1 α+1 )∪A( 1 α+ξ1 )∪A( 1 α+ξ2 )∪A( 1 α+ξ2 )∪·· ·∪A( 1 α+ξ2n−2 ). We can consider O(α) as a set of 2n + 1 affine sets. 〈σn(2 m−1)〉 partitions this set of 2n + 1 affine sets. The only possibility are orbits of length 1 or 2. Since O(α) contains an odd number of affine sets then the possibility that all orbits are of length 2 is excluded. So there has to be at least one orbit of length 1, i.e., O(α) must contain an affine set which is fixed under 〈σn(2 m)〉. By Subsection 3.3.1, there are 2n(2 m−1−1) such affine sets. We claim that any fixed O(α) in OF contains precisely one affine set which is fixed under 〈σn(2 m−1)〉. It suffices to show that O(α) cannot contain two affine sets which are fixed under 〈σn(2 m−1)〉. Without loss of generality, suppose A(α) is fixed under 〈σn(2 m−1)〉. Recall that O(α) = A(α)∪A( 1 α )∪A( 1 α+1 )∪A( 1 α+ξ1 )∪A( 1 α+ξ2 )∪A( 1 α+ξ3 )∪·· ·∪ A( 1 α+ξ2n−2 ). We show that none of the affine sets after A(α) in the above decomposition of O(α) is fixed under 〈σn(2 m−1)〉. This is done by showing that no element in any of these affine sets satisfies the equation x2 n(2m−1) + x + 1 = 0 (see Equation (1) in Subsection 3.3.1). By Subsection 3.3.1, the 2n elements in the set {α+ξ : ξ ∈ F2n} satisfy the equation x2 n(2m−1) +x+1 = 0 from which we see that α2 n(2m−1) = α+1. It is sufficient to show that no element in A( 1 α ) satisfies x2 n(2m−1) +x+ 1 = 0. A typical element in A( 1 α ) has the form ζ α +ξ and substituting this in x2 n(2m−1) +x+ 1 we get ( ζ α +ξ)2 n(2m−1) + ( ζ α +ξ) + 1 = α 2+α+ζ α2+α 6= 0, since α is an element of degree 2m over F2n. We conclude that A( 1α) is not fixed under 〈σ n(2m−1)〉 and in fact A(α) is the only affine set in O(α) fixed under 〈σn(2 m−1)〉. It follows that the number of O(α)’s in OF which are fixed under 〈σn(2 m−1)〉 is 2n(2 m−1−1). 3.5.2. 〈σn(2 s)〉 a subgroup of G of order 2m−s Suppose O(α) ∈ OF is fixed under 〈σn(2 s)〉 where 0 ≤ s < m. Then 〈σn(2 s)〉 acts on O(α). We can consider O(α) as a set of 2n + 1 affine sets. 〈σn(2 s)〉 partitions this set of 2n + 1 affine sets. The only possible lengths of orbits are all factors of 2m−s. Since O(α) contains an odd number of affine sets then the possibility that all orbits are of even length is precluded. By Subsection 3.3.2, there is no affine set fixed under 〈σn(2 s)〉. So we also preclude the possibility of length 1. Hence we conclude that no O(α) in OF is fixed under 〈σn(2 s)〉. 3.5.3. 〈σ2 m 〉 a subgroup of G of order n Suppose O(α) ∈ OF is fixed under 〈σ2 m 〉. Then 〈σ2 m 〉 acts on O(α) which is seen as a set of 2n + 1 affine sets. 〈σ2 m 〉 partitions this set of 2n + 1 affine sets. The only possible lengths of orbits are 1 and n. Since 2n + 1 ≡ 2 + 1 = 3 (mod n) (by Fermat Little Theorem) then n does not divide 2n + 1. So there must be at least three affine sets in O(α) fixed under 〈σ2 m 〉. We claim that there are only three affine sets in O(α) which are fixed under 〈σ2 m 〉. Recall that O(α) = A(α) ∪A( 1 α ) ∪A( 1 α+1 ) ∪A( 1 α+ξ1 ) ∪A( 1 α+ξ2 ) ∪ A( 1 α+ξ3 )∪·· ·∪A( 1 α+ξ2n−2 ). Without loss of generality, suppose A(α) in O(α) is fixed under 〈σ2 m 〉. So, by Subsection 3.3.3, A(α) contains a fixed point, i.e., some elements of A(α) satisfy the equation x2 2m = x. It is clear that α and α + 1 in A(α) satisfy x2 2m = x. Since ( 1 α )2 2m = 1 α and ( 1 α+1 )2 2m = 1 α+1 it is clear that A( 1 α ) and A( 1 α+1 ) also contain fixed points, i.e., A( 1 α ) and A( 1 α+1 ) are also fixed. We now show that no affine set after A( 1 α+1 ) in the decomposition of O(α) is fixed under 〈σ2 m 〉. First observe that, for ν ∈ F2n \ {0, 1}, we have ν2 2m 6= ν since (2m,n) = 1. So ( 1 α+ν )2 2m = 1 α+ν2 2m = 1 α+η implies that σ2 m (A( 1 α+ν )) = A( 1 α+η ) as required. Therefore A(α), A( 1 α ) and A( 1 α+1 ) are the only affine sets fixed under 〈σ2 m 〉. By Subsection 3.3.3, there are 22 m−1 − 22 m−1−1 affine sets which are fixed under 〈σ2 m 〉. Hence the number of O(α)’s in OF which are fixed under 〈σ2 m 〉 is (22 m−1 − 22 m−1−1)/3. 243 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 3.5.4. 〈σ2 m−1 〉 a subgroup of G of order 2n Suppose O(α) ∈ OF is fixed under 〈σ2 m−1 〉. Then 〈σ2 m−1 〉 acts on O(α) which is seen as a set of 2n + 1 affine sets. 〈σ2 m−1 〉 partitions this set of 2n + 1 affine sets. O(α) = A(α) ∪ A( 1 α ) ∪ A( 1 α+1 ) ∪ A( 1 α+ξ1 )∪A( 1 α+ξ2 )∪A( 1 α+ξ3 )∪·· ·∪A( 1 α+ξ2n−2 ). The possible lengths of orbits are all factors of 2n. But the possibility that all orbits are of even length is precluded since the O(α) contains odd number of affine sets. It is also not possible to have length n for all orbits since n - (2n + 1) (see Subsection 3.5.3). So there must be at least one affine set fixed under 〈σ2 m−1 〉. We claim that any O(α) fixed under 〈σ2 m−1 〉 contains precisely one affine set fixed under 〈σ2 m−1 〉. By Subsection 3.3.4, an affine set fixed under 〈σ2 m−1 〉 contains some elements which satisfy the equation x2 2m−1 + x + 1 = 0. Suppose A(α) is fixed under 〈σ2 m−1 〉. It is clear that α and α + 1 satisfy x2 2m−1 + x + 1 = 0. We also observe that ( 1 α )2 2m−1 = 1 α+1 and ( 1 α+1 )2 2m−1 = 1 α which imply that σ2 m−1 (A( 1 α )) = A( 1 α+1 ) and σ2 m−1 (A( 1 α+1 )) = A( 1 α ). We can conclude that A( 1 α ) and A( 1 α+1 ) form an orbit of length 2. Since 〈σ2 m 〉 ⊂ 〈σ2 m−1 〉 then any O(α) or affine set fixed under 〈σ2 m−1 〉 is also fixed under 〈σ2 m 〉. By Subsection 3.3.3, no affine set after A( 1 α+1 ) in the decomposition of O(α) is fixed under 〈σ2 m 〉. So we conclude that 〈σ2 m−1 〉 does not fix any affine set after A( 1 α+1 ) in the decomposition of O(α). By Subsection 3.3.4, there are 22 m−1−1 affine sets fixed under 〈σ2 m−1 〉. So we conclude that the number of O(α)’s in OF which are fixed under 〈σ2 m−1 〉 is 22 m−1−1. 3.5.5. 〈σ2 s 〉 a subgroup of G of order n(2m−s) Suppose O(α) ∈ OF is fixed under 〈σ2 s 〉 where 0 ≤ s < m − 1. Then 〈σ2 s 〉 acts on O(α) which is seen as a set of 2n + 1 affine sets. 〈σ2 s 〉 partitions this set of 2n + 1 affine sets. The possible lengths of orbits are all factors of n(2m−s). Since O(α) contains an odd number of affine sets then the possibility that all orbits are of even length is precluded. Since 2n + 1 ≡ 3 (mod n) (see Subsection 3.5.3) we also preclude the possibility that all orbits are of length n. We now consider the possibility of x affine sets partitioned in orbits of length 2 and 2n + 1 − x affine sets partitioned in orbits of length n or 2n, i.e., 2n + 1 − x ≡ 0 (mod n). Since 2n + 1 ≡ 3 (mod n), x has the form kn + 3 where k is an odd integer. Since 2|x then k is non zero. So there are kn + 3 > 3 affine sets permuted in orbits of length 2 under 〈σs〉. Since 〈σs+1〉 ⊂ 〈σs〉 it is easy to observe that two affine sets that form an orbit under 〈σs〉 are fixed under 〈σs+1〉. If s = m− 2 then it would mean that there exist a fixed O(α) under 〈σ2 m−1 〉 which contains more than 3 affine sets fixed under 〈σ2 m−1 〉, contradicting Subsection 3.5.4. No affine set is fixed under 〈σ2 s+1 〉 for s < m− 2 (see Subsection 3.3.5) so it would be a contradiction to say that more than 3 affine sets in each fixed O(α) are fixed under 〈σ2 s+1 〉. A similar argument can be used to show that length of multiple of 2 and n are also not possible. So there must be at least an affine set in O(α) fixed under 〈σ2 s 〉. By Subsection 3.3.5, no affine set is fixed by 〈σ2 s 〉. Hence there is no O(α) in OF which is fixed under 〈σ2 s 〉. 3.6. The number of orbits in OF under the action of G Table 2 shows the number of O(α)’s in OF which are fixed under the various subgroups of G. The structure of this table is similar to that of Table 1. The subgroups which do not fix any O(α) are left out. The subgroups are listed in ascending order of the number of elements in the subgroup. So the first row is the subgroup 〈σn(2 m)〉 since it contains only the identity. Column 3 lists the number of elements in subgroup which are not already counted in subgroups in the rows above it in the table. This is to avoid repetition when we multiply column 3 by column 4 in order to get the total number of fixed O(α)’s by the elements in G. By the Cauchy Frobenius Theorem, the number of orbits in OF under the action of G is (2n(2 m)−2n(2 m−1))/(2n(2n−1)(2n+1))+2(2 m−1−1)n+(n−1)[(22 m−1+22 m−1 )/3] n(2m) . 244 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 Table 2. Subgroup Order of No. of elements No. of fixed Product of G Subgroup not in previous O(α)’s of columns subgroup 3 and 4 〈σn(2 m)〉 1 1 2 n(2m)−2n(2 m−1) 2n(2n−1)(2n+1) 2n(2 m)−2n(2 m−1) 2n(2n−1)(2n+1) 〈σn(2 m−1)〉 2 1 2(2 m−1−1)n 2(2 m−1−1)n 〈σ2 m 〉 n n−1 22 m−1 −22 m−1−1 (n−1)(22 m−1 −22 m−1−1)/3 〈σ2 m−1 〉 2n n−1 22 m−1−1 (n−1)22 m−1−1 We state this result in the following theorem: Theorem 3.4 (The Main Theorem). Let n be an odd prime number and m > 1. The number of inequivalent extended irreducible binary Goppa codes of degree 2m and length 2n + 1 is at most (2n(2 m) − 2n(2 m−1))/(2n(2n − 1)(2n + 1)) + 2(2 m−1−1)n + (n− 1)[(22 m−1 + 22 m−1 )/3] n(2m) . Example 3.5. We find an upper bound on the number of irreducible Goppa codes and extended irreducible Goppa codes of degree 4 for n = 5, 7, 11, 13 and 17 as follows: n Upper bound on number Upper bound on number of of irreducible Goppa codes extended irreducible Goppa codes 5 56 4 7 596 10 11 95420 94 13 1290872 316 17 252648992 3856 Example 3.6. We find an upper bound on the number of irreducible Goppa codes of degree 16 and extended irreducible Goppa codes for n = 7 and 11. n Upper bound on number Upper bound on number of of irreducible Goppa codes extended irreducible Goppa codes 7 2,851,857,368,342,478,330,960,957,440 22,107,421,460,024,199,242,917,600 11 1.29813175585637777519535861321×1044 6.33544048734200963988747188270 ×1040 4. Conclusion In this paper we have produced an upper bound on the number of extended irreducible binary Goppa codes of degree 2m and length 2n + 1 where n is a prime number. The result is presented in the Theorem 3.4. 245 http://orcid.org/0000-0001-8792-6954 A. I. Musukwa et al. / J. Algebra Comb. Discrete Appl. 4(3) (2017) 235–246 References [1] T. P. Berger, Goppa and related codes invariant under a prescribed permutation, IEEE Trans. Inform. Theory 46(7) (2000) 2628–2633. [2] C. L. Chen, Equivalent irreducible Goppa codes, IEEE Trans. Inform. Theory 24(6) (1978) 766–769. [3] H. Dinh, C. Moore, A. Russell, McEliece and Niederreiter cryptosystems that resist quantum Fourier sampling attacks, In: Rogaway P. (eds) Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science 6841 (2011) 761–779. [4] I. M. Isaacs, Algebra: A Graduate Text, Brooks/Cole, Pacific Grove, 1994. [5] R. Lidl, H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, London, 1994. [6] S. Ling, C. Xing, Coding Theory; A First Course, Cambridge University Press, United Kingdom, 2004. [7] K. Magamba, J. A. Ryan, Counting irreducible polynomials of degree r over Fqn and generating Goppa codes using the lattice of subfields of Fqnr , J. Discrete Math. 2014 (2014) 1–4. [8] J. A. Ryan, Irreducible Goppa Codes, Ph.D. Dissertation, University College Cork, 2004. [9] J. A. Ryan, A new connection between irreducible and extended irreducible Goppa codes, Proc. SAMSA (2012) 152–154. [10] J. A. Ryan, Counting extended irreducible binary quartic Goppa codes of length 2n + 1, IEEE Trans. Inform. Theory 61(3) (2015) 1174–1178. 246 http://orcid.org/0000-0001-8792-6954 https://doi.org/10.1109/18.887871 https://doi.org/10.1109/18.887871 https://doi.org/10.1109/TIT.1978.1055951 https://doi.org/10.1007/978-3-642-22792-9_43 https://doi.org/10.1007/978-3-642-22792-9_43 https://doi.org/10.1007/978-3-642-22792-9_43 http://dx.doi.org/10.1155/2014/263179 http://dx.doi.org/10.1155/2014/263179 http://samsa-math.org/wp-content/uploads/2013/04/SAMSA2012ProceedingsComplete.pdf http://samsa-math.org/wp-content/uploads/2013/04/SAMSA2012ProceedingsComplete.pdf https://doi.org/10.1109/TIT.2015.2389246 https://doi.org/10.1109/TIT.2015.2389246 Introduction Preliminaries Counting extended irreducible binary Goppa codes of degree 2m Conclusion References