# Counting Extended Irreducible Goppa Codes

Authors: John A. Ryan
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

We produce an upper bound on the number of extended irreducible Goppa codes over any
finite field.


---

## Body

## 1. Introduction

The advent of quantum computing has brought Goppa codes to the forefront. Most cryptosystems which are in general use today are asymmetric cryptosystems which are based on the integer factorization problem or the discrete logarithm problem and it is conjectured that these cryptosystems may become insecure when quantum computing is further developed [1]. One cryptosystem which may have potential to withstand attack by quantum computers is the McEliece cryptosystem which is based on the family of Goppa codes [1]. It is conjectured that this family of Goppa codes is near to random codes and a categorization has so far eluded researchers [2]. There have been many attempts to count the number of Goppa codes for fixed parameters and the author of this paper produced in 2004 a computer program which gives the best upper bound available today for the number of such codes [3]. Recent research has clearly shown that many Goppa codes become equivalent when extended by a parity check [4] and so the question of categorizing Goppa codes through their extended versions is now being proposed. As a first step, we investigate the possibility of counting extended Goppa codes using the tools which were developed for counting the nonextended versions. We begin by defining a degree r irreducible Goppa code Γ(L,g) over 𝔽q of length qn in terms of a single field element α of degree r over 𝔽qn. We then define the extended code Γ(L,g)¯. We give the well-known sufficient conditions on two elements of degree r,α and β, for the corresponding extended irreducible Goppa codes (the extended Goppa codes defined by α and β) to be equivalent. Denoting the set of all elements of degree r as 𝕊, counting the cardinality of the set 𝕊, and using the well-known conditions for equivalence we produce an upper bound on the number of inequivalent extended irreducible Goppa codes over 𝔽q of degree r and length qn+1.


## 2. Background

Letq be a power of a prime number; let 𝔽q be the field of order q and 𝔽qn its extension of order n. In this paper all codes will be over 𝔽q. The family of Goppa codes was first introduced by Goppa in 1971 [5]. For our purposes we focus on irreducible Goppa, codes, and define irreducible Goppa codes as follows.Definition 1.
Letg(z)∈𝔽qn[z] be irreducible of degree r and let L=𝔽qn={ζi:0≤i≤qn-1}. Then the irreducible Goppa code Γ(L,g) is defined as the set of all vectors c_=(c0,c1,…cqn-1) with components in 𝔽q which satisfy the condition
(1)∑i=0qn-1‍ciz-ζi≡0mod⁡g(z).The polynomialg(z) is called the Goppa Polynomial. The set L is called the Defining Set. Since g(z) is irreducible over 𝔽qn the code is called an irreducible Goppa code. Since g(z) is of degree r the code Γ(L,g) is called a Goppa code of degreer. In this paper g(z) is always irreducible of degree r over 𝔽qn.Remark 2.
The definition we have given is specific for “irreducible Goppa codes.” In the literature, in general, a Goppa code is defined with Defining SetL⊆𝔽qn such that no element of L is a root of the Goppa polynomial g(z). Since, in this paper, g(z) is irreducible we take L as large as possible; that is, L=𝔽qn. Note further that in fixing an order on the elements in L we are implicitly putting an order on the coordinates of the Goppa code as the ordered elements in L label the component positions in the codewords. Thus the length of the Goppa code is qn.Next we define extended irreducible Goppa codes.Definition 3.
LetΓ(L,g) be a Goppa code of length qn over 𝔽q. Then the extended code Γ(L,g)¯ is defined by
(2)Γ(L,g)¯={∑i=0qn‍(c0,c1,⋯,cqn):(c0,c1,⋯,cqn-1)∈Γ(L,g),∑i=0qn‍ci=0}.Remark 4.
The extended codeΓ(L,g)¯ is often described as the code obtained from Γ(L,g) by adding a parity check to each codeword of Γ(L,g).It is shown in [6] that if α is any root of the Goppa polynomial g(z) then Γ(L,g) is completely described by any root α of g(z) and a parity check matrix H(α) is given by
(3)H(α)=(1α-ζ01α-ζ1⋯1α-ζqn-1),
where L=𝔽qn={ζi:0≤i≤qn-1}. We may denote this code by C(α).Remark 5.
C
¯
(
α
) denotes the same code as Γ(L,g)¯, where g(α)=0.Remark 6.
Note that in using this parity check matrix to defineC(α) we are implicitly fixing an order on L and, consequently, an order on the components of the codewords in the code C(α).Considering that any irreducible Goppa code can be defined by an element of degreer over 𝔽qn and, conversely, any such element of degree r defines an irreducible Goppa code, we make the following definition.Definition 7.
The set𝕊=𝕊(n,r) is the set of all elements in 𝔽qnr of degree r over 𝔽qn.Finally, as background material, we recall a sufficient condition which is well known for two extended irreducible Goppa codes to be equivalent.Consider the mapsπζ1,ζ2,ξ1,ξ2,i defined on 𝕊 by
(4)πζ1,ζ2,ξ1,ξ2,i:α⟼ζ1αqi+ξ1ζ2αqi+ξ2
for fixed i,ζj, and  ξj where 0≤i<nr,ζj,ξj∈𝔽qn,j=1,2, and ζ1ξ2≠ζ2ξ1.For simplicity, where there is no confusion, we writeπ for πζ1,ζ2,ξ1,ζ2.It is well known that ifπ(α)=β then C¯(α) is equivalent to C¯(β) (see [7]).Remark 8.
Note that in the definition ofπ the scalars ζj and ξj are defined up to scalar multiplication. Hence we may assume that ζ1=1 or ξ1=1 if ζ1=0.Remark 9.
Note that the mapπζ1,ζ2,ξ1,ξ2,i can be broken up into the composition of two maps, namely, (1)
the mapπζ1,ζ2,ξ1,ξ2 defined on 𝕊 by πζ1,ζ2,ξ1,ξ2:α↦(ζ1α+ξ1)/(ζ2α+ξ2) and(2)
the mapσi:α↦αqi, where σ denotes the Frobenius automorphism of 𝔽qnr leaving 𝔽q fixed.We immediately justify the statement thatπζ1,ζ2,ξ1,ξ2 is a map on 𝕊.Lemma 10.
π
ζ
1
,
ζ
2
,
ξ
1
,
ξ
2 is a map defined on 𝕊.Proof.
Supposeπζ1,ζ2,ξ1,ξ2(α)=(ζ1α+ξ1)/(ζ2α+ξ2)=β where β is an element of degree s strictly less that r over 𝔽qn (note that β∈𝔽qnr and so β cannot have degree greater than r over 𝔽qn)
(5)ζ1α+ξ1=ζ2αβ+ξ2β,α=ξ2β-ξ1ζ1-ζ2β.
But this is impossible since β∈𝔽qns,ζi,ξi∈𝔽qn and so the right hand side is an element of 𝔽qns contradicting the fact that α is an element of degree r over 𝔽qn.In the light of the foregoing, we make two more definitionsDefinition 11.
LetF denote the set of all maps {πζ1,ζ2,ξ1,ξ2:ζj,ξj∈𝔽qn,j=1,2andζ1ξ2≠ζ2ξ1}.Definition 12.
LetG denotes the set of all maps {σi:1≤i≤n×r}.Lemma 13.
F together with the operation of composition of maps ∘ is a group.Proof.
Letπζ1,ζ2,ξ1,ξ2,πζ3,ζ4,ξ3,ξ4∈F. First we show that F is closed under the operation of ∘:
(**)πζ3,ζ4,ξ3,ξ4∘πζ1,ζ2,ξ1,ξ2(α)=ζ3((ζ1α+ξ1)/(ζ2α+ξ2))+ξ3ζ4((ζ1α+ξ1)/(ζ2α+ξ2))+ξ4=ζ3ζ1α+ζ3ξ1+ζ2ξ3α+ξ2ξ3ζ4ζ1α+ζ4ξ1+ζ2ξ4α+ξ2ξ4=(ζ3ζ1+ζ2ξ3)α+ζ3ξ1+ξ2ξ3(ζ4ζ1+ζ2ξ4)α+ζ4ξ1+ξ2ξ4.We need to show (ζ3ζ1+ζ2ξ3)(ζ4ξ1+ξ2ξ4)≠(ζ4ζ1+ζ2ξ4)(ζ3ξ1+ξ2ξ3). The Left Hand Side (LHS) is equal to ζ3ζ1ζ4ξ1+ζ2ξ3ζ4ξ1+ζ3ζ1ξ2ξ4+ζ2ξ3ξ2ξ4 and the Right Hand side (RHS) is equal to ζ4ζ1ζ3ξ1+ζ2ξ4ζ3ξ1+ζ4ζ1ξ2ξ3+ζ2ξ4ξ2ξ3. Observe that the first and last terms of the LHS are the same as the first and last terms of the RHS and so our task now is to show that ζ2ξ3ζ4ξ1+ζ3ζ1ξ2ξ4≠ζ2ξ4ζ3ξ1+ζ4ζ1ξ2ξ3 or equivalently show that ζ2ξ1ζ4ξ3-ζ2ξ1ζ3ξ4≠ζ1ξ2ζ4ξ3-ζ1ξ2ζ3ξ4; that is ζ2ξ1(ζ4ξ3-ζ3ξ4)≠ζ1ξ2(ζ4ξ3-ζ3ξ4).
But this is immediate from the fact thatζ1ξ2≠ζ2ξ1 and ζ3ξ4≠ζ4ξ3.
Secondly, associativity follows from the associativity of mappings. Thirdly, observe thatπ1,0,0,1 is the identity. Finally, given πζ1,ζ2,ξ1,ξ2 to find πζ3,ζ4,ξ3,ξ4 such that πζ3,ζ4,ξ3,ξ4∘πζ1,ζ2,ξ1,ξ2=π1,0,0,1 is a matter of solving the equation ((ζ3ζ1+ζ2ξ3)a+ζ3ξ1+ξ2ξ3)/((ζ4ζ1+ζ2ξ4)a+ζ4ξ1+ξ2ξ4)=a. See (**) above. This is a matter of solving the four equations:(a)
ζ3ζ1+ζ2ξ3=1(b)
ζ3ξ1+ξ2ξ3=0(c)
ζ4ζ1+ζ2ξ4=0(d)
ζ4ξ1+ξ2ξ4=1in the four unknowns ζ3,ζ4,ξ3 and ξ4. We know from linear algebra that this is always possible.Lemma 14.
G together with the operation of composition of maps is a cyclic group of order n×r.Proof.
ObserveG=<σ> where σ:α↦αq is the Frobenius automorphism of 𝔽qnr leaving 𝔽q fixed. Since σnr is the identity on 𝔽qnr the result follows.


## 3. Strategy to Count All Extended Irreducible Goppa Codes for Fixedq,n, and r

We apply the following method to count the number of extended Goppa codes. Observe that each elementα∈𝕊 defines an extended irreducible Goppa code C¯(α) over 𝔽q of degree r of length qn+1 and conversely each such extended Goppa code is defined by an element α∈𝕊. We count the number of orbits in 𝕊 under the action of the group F and this gives us an upper bound on the number of irreducible extended Goppa codes.We first confirm the details thatF acts on 𝕊.Lemma 15.
The groupF acts on 𝕊.Proof.
We have already seen thatπ(α)∈𝕊,forallα∈𝕊. Clearly π1,0,0,1(α)=α,forallα∈𝕊. That πζ3,ζ4,ξ3,ξ4∘πζ1,ζ2,ξ1,ξ2(α)=πζ3,ζ4,ξ3,ξ4(πζ1,ζ2,ξ1,ξ2(α)) is merely the definition of ∘.The orbit containingα is the set
(6){ζ1α+ξ1ζ2α+ξ2:ζj,ξj∈𝔽qn,j=1,2,ζ1ξ2-ζ2ξ1≠0}
and we denote this set by O(α). We denote the set of all orbits in 𝕊 under the action of F by 𝕆; that is, 𝕆={O(α):α∈𝕊}. It follows from Group Theory and Lemma 15 that the set of all orbits in 𝕊 under the group action of F partition the set 𝕊 and that 𝕆 partitions the set 𝕊.Theorem 16.
For anyα∈𝕊, |O(α)|=q3n-qn:
(7)O(α)={ζ1α+ξ1ζ2α+ξ2:ζj,ξj∈𝔽qn,j=1,2,ζ1ξ2-ζ2ξ1≠0}.First remember that the elementsζi,ξi are defined up to scalar multiplication so we may assume that, if ζ1≠0, then ζ1=1 (see Remark 8).(1)
Ifζ1=0, then w.l.o.g. ξ1=1 and there are qn(qn-1)=q2n-qn possibilities.(2)
Ifζ1=1, then we need to exclude the cases when ξ2=ζ2ξ1.
(a)
Considerξ2=0, and then exclude
(i)
theqn cases when ζ2=0 and ξ1∈𝔽qn,(ii)
theqn-1 cases when ζ2≠0∈𝔽qn and ξ1=0.(b)
Considerξ2≠0. There are qn-1 such cases. In each such case, for each ξ1≠0 (and there are qn-1 of them) there is a unique solution for ζ2. Hence there are (qn-1)2 possibilities when ξ2≠0.So the total number of possibilities under item(2) is q3n-(2qn-1)-(qn-1)2=q3n-q2n.Adding the possibilities under(1) and (2) we get q3n-q2n+q2n-qn=q3n-qn.Theorem 17.
The number of inequivalent extended irreducible Goppa codes over𝔽q of degree r and length qn+1 is less than or equal to |𝕊|/(q3n-qn).Proof.
Any extended irreducible Goppa code is defined by an element of𝕊. The elements of 𝕊 contained in the orbit O(α) define codes equivalent to C(α). Since 𝕆 partitions 𝕊 and by Theorem 16 every set in 𝕆 has q3n-qn elements, we conclude that |𝕆|=|𝕊|/(q3n-qn). This gives an upper bound on the number of inequivalent extended irreducible Goppa codes.Remark 18.
Note that this bound can be improved upon by further action of the groupG of Frobenius automorphisms. It is possible to show that G acts on 𝕆={O(α):α∈𝕊} and then the number of orbits in 𝕆 under G gives an improved upper bound on the number of inequivalent extended irreducible Goppa codes. This research is in progress.



---

*Source: 871871-2014-02-12.xml*