In this paper, we consider an interpolation-based decoding algorithm for a large family of maximum rank distance codes, known as the additive generalized twisted Gabidulin codes, over the finite field \(\mathbb {F}_{q^{n}}\) for any prime power q. This paper extends the work of the conference paper Li and Kadir (2019) presented at the International Workshop on Coding and Cryptography 2019, which decoded these codes over finite fields in characteristic two.
Hinweise
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Error correction codes with the rank metric have found applications in space-time coding [27], random network coding [44] and cryptography [12]. Many important properties of rank metric codes including the Singleton like bound were independently studied by Delsarte [9] , Gabidulin [13] and Roth [38]. Codes that achieve this bound were called maximum rank distance (MRD) codes. The most famous sub-family of MRD codes are Gabidulin codes which is the rank metric analog of Reed-Solomon codes. They have been extensively studied in the literature [9, 12, 13, 25, 36, 38].
Finding new families of MRD codes has been an interesting research topic since the invention of Gabidulin codes. In [20, 39], the Frobenious automorphism in the Gabidulin codes were generalized to arbitrary automorphism and generalized Gabidulin (GG) codes were proposed. In the past few years, a considerable amount of work has been done on MRD codes. In [40], Sheekey twisted the evaluation polynomial of a Gabidulin code and proposed a large family of MRD codes termed twisted Gabidulin (TG) codes. Using the same idea for generalizing Gabidulin codes, arbitrary automorphism was employed to construct generalized twisted Gabidulin (GTG) codes. This family of MRD codes were first described in [40, Remark 9] and later comprehensively studied in [26]. Otal and Özbudak [30] later introduced a large family of MRD codes, known as additive generalized twisted Gabidulin (AGTG) codes, which contains all the aforementioned linear MRD codes as sub-families and new additive MRD codes. There are also some new families of MRD codes which are not equivalent to AGTG codes nor its subfamilies [5, 8, 42, 47]. Recent constructions of linear and nonlinear MRD codes were lately summarized in [31, 41].
Anzeige
MRD codes with efficient decoding algorithm are of great interest in practice. In his pioneering work [13], Gabidulin gave a decoding algorithm based on extended Euclidean algorithm. Subsequently, Richter and Plass in [36], and Loidreau [25] proposed modified version of Berlekamp-Massey and Welch-Berlekamp algorithms to decode Gabidulin codes. Some of the aforementioned algorithms were further optimized in [45, 48]. Nevertheless, the known decoding algorithms for Gabidulin codes cannot be directly applied to those new MRD codes with twisted evaluation polynomials, especially when the MRD codes are only linear over the ground field \(\mathbb {F}_{q}\) or its subfield. By modifying the decoding algorithm in [19] for subspace codes, Randrianarisoa and Rosenthal in [37] proposed a decoding method for the twisted Gabidulin codes, which works only for a limited option of parameters. Randrianarisoa later proposed an interpolation approach to decoding twisted Gabidulin codes in [35] , where he gave a brief discussion on the case when the rank of the error vector reaches the unique error-correcting radius of the twisted Gabidulin codes.
In this paper, we apply the interpolation approach by Randrianarisoa [35] in decoding additive generalized twisted Gabidulin (AGTG) codes, which contain (generalized) twisted Gabidulin codes and (generalized) Gabidulin codes as special cases. For AGTG codes with minimum rank distance d, if an error vector has rank strictly less than \(\frac {d-1}{2}\), the decoding process can be directly converted to the decoding of generalized Gabidulin codes, for which existing decoding algorithms in [25, 36, 48] can be applied. On the other hand, when the error vector has rank exactly \(\frac {d-1}{2}\) (with d being odd), a new problem arises and one needs an efficient way to solve a quadratic polynomial. Solving a given quadratic polynomial over finite fields in general is a challenging problem. The quadratic polynomial derived from the decoding of AGTG codes has a close connection to a projective polynomials P(x). Different from the short discussion in [35], we study the projective polynomial P(x) in greater depth. We start with the discussion on the number of roots of P(x) according to its coefficients and the characteristic of the finite field \(\mathbb {F}_{q^{n}}\), propose methods to find roots of P(x) for each case, and finally adopt the result in the decoding algorithm for AGTG codes.
The remainder of this paper is structured as follows. Section 2 introduces some preliminaries, where we particularly recall some properties of linearized polynomial and recently constructed twisted MRD codes. Section 3 summarizes the interpolation decoding approach for additive generalized twisted Gabidulin codes and identifies the crucial quadratic polynomial when the rank of error reaches \(\frac {d-1}{2}\) (with d being odd). Section 4 is dedicated to the study of the quadratic polynomial and to finding roots of the corresponding projective polynomial P(x). Section 5 integrates the interpolation decoding procedure and the result of Section 4 into an explicit algorithm and discusses the complexity of the proposed algorithm. Section 6 concludes the work of this paper.
2 Preliminaries
Let q be a power of a prime p. Throughout this paper we denote by \(\mathbb {F}_{q^{r}}\) the finite field with qr elements for an arbitrary positive integer r.
Anzeige
2.1 Linearized polynomial
A polynomial of the form \(L(x)={\sum }_{i=0}^{k-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\) is known as a q-polynomial [29]. Define a set
It is easy to verify that \(\left ({\mathcal{L}}_{k}(\mathbb {F}_{q^{n}}), +, \circ \right )\) forms a non-commutative \(\mathbb {F}_{q}\)-algebra, where + denotes the conventional polynomial addition and ∘ denotes the symbolic product given by a(x) ∘ b(x) = a(b(x)). Note that symbolic product is associative and distributive, but non-commutative in general. For a nonzero \(L(x)={\sum }_{i=0}^{k-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\), its q-degree is given by \(\deg _{q}(L(x))=\max \limits \{0\leq i<k | l_{i}\neq 0\}\).
When q is fixed or the context is clear, it is also customary to speak of a linearized polynomial as it satisfies the linearity property: L(c1x + c2y) = c1L(x) + c2L(y) for any \(c_{1}, c_{2}\in \mathbb {F}_{q}\) and any x,y in an arbitrary extension \(\mathbb {F}_{q^{n}}\). Hence a linearized polynomial \(L(x)\in {\mathcal{L}}_{n}(\mathbb {F}_{q^{n}})\) indicates an \(\mathbb {F}_{q}\)-linear transformation L from \(\mathbb {F}_{q^{n}}\) to itself.
Known MRD codes in the literature are mostly given in the terms of linearized polynomials. Some relevant definitions and auxiliary results are recalled below.
Definition 1
For a nonzero linearized polynomial \(L(x)={\sum }_{i=0}^{k-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\), its rank is given by
where \(\text {Img}(L)=\left \{L(x) | x \in \mathbb {F}_{q^{n}}\right \}\) and \(\text {Ker}(L)=\{x\in \mathbb {F}_{q^{n}} | L(x)=0\}\).
For a linearized polynomial \(L(x)={\sum }_{i=0}^{k}l_{i}x^{q^{i}}\) with q-degree k, i.e., lk≠ 0, it is clear that Ker(L) has at most qk elements. From the definition, the linearized polynomial L(x) has
$$ \text{Rank}(L) = n - \dim_{\mathbb{F}_{q}}(\text{Ker}(L)) \geq n - k. $$
Sheekey in [40] characterizes a necessary condition for L(x) to have rank n − k as below.
Lemma 1
[40] Suppose a linearized polynomial \(L(x)=l_{0}x+l_{1}x^{q}+\cdots +l_{k}x^{q^{k}}\), lk≠ 0, in \({\mathcal{L}}_{n}({\mathbb {F}_{q^{n}}})\) has qk roots in \(\mathbb {F}_{q^{n}}\). Then
where \(\text {Norm}_{q^{n}/q}(x)=x^{1+q+{\cdots } + q^{n-1}}\) is the norm function from \(\mathbb {F}_{q^{n}}\) to \(\mathbb {F}_{q}\).
Furthermore, the necessary and sufficient condition for L(x) with q-degree k to have qk roots in \(\mathbb {F}_{q^{n}}\) was independently characterized recently in [28, Theorem 7] and [7, Theorem 1.2], where all coefficients of L(x) are involved.
Below we recall two interesting matrices, of which properties and connection are critical for the decoding algorithm in this paper.
Definition 2
[24, 49] Given a vector a = (a0,…,an− 1) over \(\mathbb {F}_{q^{n}}\), the Dickson matrix associated with a is given by
Da ⋅ Db = Du, where u = (u0,…,un− 1) with \(u_{i} ={\sum }_{j=0}^{n-1}a_{i-j(\text {mod } n)}^{q^{j}}b_{j}\);
iii)
\({M_{a}^{T}}\cdot M_{b} = D_{v}\), where v = (v0,…,vn− 1) with \(v_{i} ={\sum }_{j=0}^{n-1}a_{j}^{q^{i}}b_{j}\);
iv)
Ma ⋅ Db = Mw, where w = (w0,…,wn− 1) with \(w_{i} ={\sum }_{j=0}^{n-1}a_{i}^{q^{j}}b_{j}\).
The proof follows from direct calculations and is thus omitted here.
Let \(\mathcal {D}_{n}(\mathbb {F}_{q^{n}})\) be the set of all n × n Dickson matrices over \(\mathbb {F}_{q^{n}}\). It is shown in [49] that \(\mathcal {D}_{n}(\mathbb {F}_{q^{n}})\) forms an \(\mathbb {F}_{q}\)-algebra and there is an isomorphism φ between \({\mathcal{L}}_{n}(\mathbb {F}_{q^{n}})\) and \(\mathcal {D}_{n}(F_{q^{n}})\) given by
A Dickson matrix D will be said to be associated with a linearized polynomial L(x) if φ(L(x)) = D.
Proposition 1
[49]. Let L be the linear transformation induced by a linearized polynomial \(L(x)\in {\mathcal{L}}_{n}(\mathbb {F}_{q^{n}})\) and D be the Dickson matrix associated with L(x). Then
It is well known [24] that given a linearized polynomial \(L(x)={\sum }_{i=0}^{n-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\), it is a permutation of \(\mathbb {F}_{q^{n}}\), i.e., Rank(L) = n, if and only if its associated Dickson matrix is non-singular; or equivalently its associated Moore matrix is non-singular. It follows from the fact that the determinant of a Moore matrix vanishes if and only if the entries of its first column are linearly dependent. In fact, more interesting connections between a linearized polynomial L(x) in \({\mathcal{L}}_{n}(\mathbb {F}_{q^{n}})\) and its associated Dickson matrix can be established.
Proposition 2
[35, Theorem 3] Assume a linearized polynomial \(L(x)={\sum }_{i=0}^{n-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\) has rank k. Then its associated Dickson matrix D in (5) has rank k over \(\mathbb {F}_{q^{n}}\). Moreover, any k × k submatrix formed by k consecutive rows and k consecutive columns in D is invertible.
Remark 1
Let σ = qs with \(\gcd (s,n)=1\). The σ-polynomial
which reduces to a q-polynomial over \(\mathbb {F}_{q^{n}}\) for s = 1, is a generalization of q-polynomial. The aforementioned properties of q-polynomials can be similarly obtained as for σ-polynomials. For instance, the σ-polynomial \(L_{\sigma }(x)={\sum }_{i=0}^{k}l_{i}x^{\sigma ^{i}}\) with lk≠ 0 also has \( \text {Rank}(L) = n - \dim _{\mathbb {F}_{q}}(\text {Ker}(L)) \geq n-k \) [15]. When q is replaced by σ in the definition of the Dickson and Moore matrices, they are called the σ-version Dickson matrix and the σ-version Moore matrix, respectively. The σ-version Dickson and Moore matrices have the same properties as characterized in Lemma 2 and Proposition 2.
2.2 Maximum rank distance (MRD) codes
Let n and m be two positive integers. The rank of a vector a = (a1,a2,…,an) over \(\mathbb {F}_{q^{m}}\) is defined as the dimension of \(\text {span}_{\mathbb {F}_{q}}\langle a_{1}, a_{2}, \ldots , a_{n}\rangle \) which is the vector space spanned by ai’s over \(\mathbb {F}_{q}\). The rank distance between two vectors \(a,b\in \mathbb {F}_{q^{m}}\) is defined as dR(a,b) = Rank(a − b).
Definition 3
A rank metric (n,M,d)-code over \(\mathbb {F}_{q^{m}}\) is a subset of \(\mathbb {F}_{q^{m}}^{n}\) with size M and minimum rank distance d. Furthermore, it is called a maximum rank distance (MRD) code if it attains the Singleton-like bound\(M\leq q^{\min \limits \{m(n -d+1),n(m-d+1) \}}\).
The Gabidulin codes are the most well-known MRD codes [13]. This family of MRD codes were further generalized in [20, 39], where the Frobenius automorphism of \(\mathbb {F}_{q^{n}}\) was replaced by a generic automorphism x↦xσ with σ = qs and \(\gcd (s,n)=1\). The generalized Gabidulin (GG) code \(\mathcal {GG}_{n,k}\) over \(\mathbb {F}_{q^{m}}\) with length n and dimension k is defined by
where α0,α1,…,αn− 1 in \(\mathbb {F}_{q^{m}}\) are linearly independent over \(\mathbb {F}_{q}\). When σ = q, i.e., s = 1, the code \(\mathcal {G}\mathcal {G}_{n, k}\) reduces to the original Gabidulin code [13]. The choice of independent points α0,α1,…,αn− 1 does not affect the rank property. Hence it is customary to express generalized Gabidulin codes without the evaluation points as \(\mathcal {G}\mathcal {G}_{n, k}= \left \{f(x)={\sum }_{i=0}^{k-1}f_{i}x^{\sigma ^{i}} | f_{i} \in \mathbb {F}_{q^{m}} \right \}\). We will also omit the evaluation points α0,α1,…,αn− 1 in the following introduction of recent twisted MRD codes [26, 30, 40]. For consistency with the parameters of MRD codes in [26, 30, 40], throughout what follows we always assume n = m.
Recent constructions of MRD codes largely depend on the number of roots of certain linearized polynomials. From Lemma 1 it is readily seen that a linearized polynomial L(x) of q-degree k has rank at least n − k + 1 if the condition (2) is not met. In [40] Sheekey adopted Lemma 1 to construct twisted Gabidulin (TG) codes and described the generalized twisted Gabidulin (GTG) codes, which was intensively studied by Lunardon et al. [26].
Proposition 3
[26, 40] Let n,k,s be positive integers such that k < n and \(\gcd (s, n)=1\). Let η be a nonzero element in \(\mathbb {F}_{q^{n}}\) satisfying \(\text {Norm}_{q^{sn}/q^{s}}(\eta )\neq (-1)^{nk}\). Then the set
is an MRD code with minimum rank distance d = n − k + 1.
The idea of manipulating some terms of linearized polynomials to construct new MRD codes was further extended in [30, 31, 33]. Below we recall from [30] the additive generalized twisted Gabidulin (AGTG) codes , for which we will propose an interpolation-based decoding algorithm in the next section.
Proposition 4
[30] Let \(n,k,s,h\in \mathbb {Z}^{+}\) satisfying \(\gcd (s,n)=1\) and k < n. Let \(q={q_{0}^{u}}\) and \(\eta \in \mathbb {F}_{q^{n}}\) such that \(\text {Norm}_{q^{sn}/{q_{0}^{s}}}(\eta )\neq (-1)^{nku}\). Then the set
is an \(\mathbb {F}_{q_{0}}\)-linear (but not necessarily \(\mathbb {F}_{q}\)-linear) MRD code of size qnk and minimum rank distance n − k + 1.
The above AGTG codes reduce to GTG codes when q0 = q and to GG codes when η = 0 or q0 = 2. Very recently, Sheekey in [42] showed the existence of a new family of MRD codes which is not equivalent to AGTG codes and Trombetti-Zhou codes in [47]. Recent MRD codes that are constructed based on Lemma 1 were formulated in a united manner in [41] and [22].
3 Encoding and decoding for AGTG codes
Throughout this section we will denote [i] := σi = qsi for i = 0,…,n − 1, where (s,n) = 1, for simplicity.
Below we briefly describe the encoding process of the AGTG codes, which provides the notational conventions and a reference for the interpolation decoding process.
3.1 Encoding AGTG codes
For an AGTG code with evaluation points α0,α1,…,αn− 1 that are linearly independent over \(\mathbb {F}_{q}\), the encoding of a message f = (f0,…,fk− 1) is the evaluation of the following linearized polynomial at points α0,α1,…,αn− 1:
Let \(\tilde {f}=(f_{0},\ldots , f_{k-1}, \eta f_{0}^{{q_{0}^{h}}}, 0, \ldots , 0)\) be a vector of length n over \(\mathbb {F}_{q^{n}}\) and M be the σ-version Moore matrix generated by αi’s, where 1 ≤ i,j ≤ n − 1, i.e.,
Here it is worth noting that in encoding process, one actually only needs to calculate the multiplication of the (k + 1)-tuple \((f_{0},\ldots , f_{k-1}, \eta f_{0}^{{q_{0}^{h}}})\) and the first k + 1 row of M. Here we express it as in (10) for being consistent with the decoding procedure.
3.2 Decoding AGTG codes with an error-interpolation polynomial g(x)
For a received word r = c + e with an error e added to the codeword c during transmission, when the error e has rank \(t\leq \lfloor \frac {n-k}{2}\rfloor \), the unique decoding task is to recover the unique codeword c such that \(d_{R}(c,r)\leq \lfloor \frac {n-k}{2}\rfloor \).
When the rank t of the error is strictly smaller than \(\frac {n-k}{2}\), the decoding of AGTG codes \({\mathcal{H}}_{k,s,q_{0}}(\eta ,h)\) can be converted to the decoding of GG codes \(\mathcal {G}\mathcal {G}_{n, k+1}\). More concretely, one can use the existing decoding algorithms, e.g., [25, 36, 48], for (generalized) Gabidulin codes to establish a system of n − (k + 1) − t independent affine equations and t unknowns, which is uniquely solvable since 2t ≤ n − (k + 1). However, when the rank t achieves the unique error-correcting radius, i.e., (n − k) is even and \(t=\frac {n-k}{2}\), one needs more equation(s) on the unknowns and new techniques are required. In the interpolation decoding for the TG codes by Randrianarisoa [35], the problem was converted to certain quadratic equations. However, how to efficiently solve the corresponding quadratic equations was little considered in [35].
Below we shall extend Randrianarisoa’s idea to the larger family of AGTG codes and investigate the quadratic equations in greater depth. For self-completeness, we briefly describe the process of interpolation decoding and how it is transformed to solving certain quadratic equation for the case that 2t = n − k.
Suppose \(g(x)={\sum }_{i=0}^{n-1}g_{i}x^{[i]}\) is an error interpolation polynomial such that
It is clear that the error vector e is uniquely determined by the polynomial g(x). Denote a vector g = (g0,…,gn− 1). From (10) and (11) it follows that
since \(\eta f_{0}^{{q_{0}^{h}}}+g_{k}=\gamma _{k},\) and f0 + g0 = γ0.
Therefore, the task of correcting error e is equivalent to reconstructing g(x) from the available information characterized in (13). This reconstruction process heavily depends on the property of the associated σ-version Dickson matrix of g(x) and will be discussed in Section 3.3.
3.3 Reconstructing the interpolation polynomial g(x)
Similarly to the definition in (3), the σ-version Dickson matrix associated with g(x) can be given by
where the indices i,j run through {0,1,…,n − 1} and Gj is the j-th column of G.
According to Proposition 2, the matrix G has rank t and any t × t matrix formed by t successive rows and columns in G is nonsingular. Then G0 can be expressed as a linear combination of G1,…,Gt, namely, G0 = λ1G1 + λ2G2 + ⋯ + λtGt, where λ1,…,λt are elements in \(\mathbb {F}_{q^{n}}\). This yields the following recursive equations
$$ g_{i} = \lambda_{1} g^{[1]}_{i-1} + \lambda_{2} g^{[2]}_{i-2} + {\cdots} + \lambda_{t} g^{[t]}_{i-t}, \quad 0\leq i < n, $$
(15)
where the subscripts in gi’s are taken modulo n. Recall that the elements gk+ 1,…,gn− 1 are known from (13). Hence we obtain the following linear equations with known coefficients and variables λ1,…,λt:
The above recurrence gives a generalized version of q-linearized shift register as described in [43], where (λ1,…,λt) is the connection vector of the shift register. It is the key equation for the decoding algorithm in this paper, by which we shall reconstruct g(x) in two major steps:
Step 1. derive the coefficients λ1,…,λt from (13) and (16);
Step 2. use λ1,…,λt to compute gk− 1,…,g0 recursively from (15).
Note that Step 1 is the critical and challenging step in the decoding process, and Step 2 is simply a recursive that can be done fast. The following discussion shows how the procedure of Step 1 works.
As discussed in the beginning of this section, for an error vector with \(\text {Rank}(e)=t \leq \lfloor \frac {n-k}{2}\rfloor \), i.e., 2t + k ≤ n, we can divide the discussion into two cases.
Case 1:
2t + k < n. In this case, (16) contains n − k − t − 1 ≥ t affine equations in variables λ1,…,λt, which has rank t. Hence the variables λ1,…,λt can be uniquely determined. Here we assume the code has high code rate, for which the Berlekamp-Massey (BM) algorithm is more efficient [14]. Another reason for choosing the BM algorithm is that it outputs the intermediate polynomial B(n−k− 1)(x) which will be used in Case 2. Although the recurrence (16) is a generalized version of the ones in [36, 43], the modified BM algorithm [36, 43] can be applied here to recover the coefficients λ1,…,λt. For self-completeness we recall the modified BM algorithm in Algorithm 1. The coefficients of Λ(n−k− 1)(x) are the desired λi’s.
Case 2:
2t + k = n. In this case (16) gives n − k − t − 1 = t − 1 independent affine equations in variables λ1,…,λt. For such an under-determined system of linear equations, we will have a set of solutions (λ1,…,λt) that has dimension 1 over \(\mathbb {F}_{q^{n}}\). Namely, the solutions will be of the form
where \(\lambda , \lambda ^{\prime }\) are fixed elements in \(\mathbb {F}_{q^{n}}^{t}\) and ω runs through \(\mathbb {F}_{q^{n}}\). As shown in [43, Th. 10], the solution can be derived from the modified BM algorithm with a free variable ω. Next we will show how the element ω is determined by other information in (13).
×
Observe that in (15), by taking i = 0 and i = k + t and substituting the solution \(\lambda +\omega \lambda ^{\prime }\), one gets the following two equations
where c0,c1,c2,c3 are derived from λ, \(\lambda ^{\prime }\) and the known gi’s. Furthermore, from (13) we have \( -\eta g_{0}^{{q_{0}^{h}}} + g_{k} = \gamma _{k}-\eta \gamma _{0}^{{q_{0}^{h}}}\). Denoting \(c_{4}= \gamma _{k}-\eta \gamma _{0}^{{q_{0}^{h}}} \) and substituting \(g_{k}=c_{4}+\eta g_{0}^{{q_{0}^{h}}}\) into (17) gives
should have roots w in \(\mathbb {F}_{q^{n}}\) that lead to solutions \(\lambda +\omega \lambda ^{\prime }\) in (16) and (g0,gk) in (17).
With the coefficients λ1,…,λt in Step 1 and the initial state gn− 1,…,gn−t, one can recursively compute g0,…,gk− 1 according to (15) in Step 2. Note that not all solutions of \(\mathcal {P}(x)\) lead to correct coefficients of the error interpolation polynomial. In fact, by the expression of Dickson matrix of g(x), correct g(x) should have the sequence (gn− 1,…,gn−t,…) generated from (15) has period n. In other words, if the output sequence has period n, we know that the corresponding polynomial \(g(x)={\sum }_{i=0}^{n-1}g_{i}x^{[i]}\) is the desired error interpolation polynomial. From the above discussion, the remaining task of decoding is to efficiently find roots of \(\mathcal {P}(x)\) in \(\mathbb {F}_{q^{n}}\), which will be discussed in the next section.
4 Finding roots of the polynomial \(\mathcal {P}(x)\)
This subsection is dedicated to finding solutions to the following equation in \(\mathbb {F}_{q^{n}} = \mathbb {F}_{q_{0}^{nu}}\):
When \(q={q_{0}^{u}}=q_{0}\), the polynomial \(\mathcal {P}\) can be reduced to P(x) in [35, Page 10]. In [35], the author converted solving P(x) = 0 to the factorization of the linearized polynomial \(x^{q^{2l}}+ax^{q^{l}}+bx\). Nevertheless, factoring \(x^{q^{2l}}+ax^{q^{l}}+bx\) is not necessarily easy and there’s no efficient algorithm, as far as we know, for factoring this linearized polynomial. Therefore, it’s important to further investigate how to efficiently solve \(\mathcal {P}(x)\).
Assume d = (v,un). We start with the simplest case that u0 = 0. In this case, (19) is reduced to an affine equation \(u_{1}x^{{q_{0}^{v}}} + u_{2}x + u_{3}=0\). Furthermore,
i)
if (u1,u2) = (0,0), then \(\mathcal {P}(x)\) has no zero if u3≠ 0 and every element in \(\mathbb {F}_{q^{n}}\) as a zero otherwise;
ii)
if u1 = 0, u2≠ 0, then \(\mathcal {P}(x)\) has a unique zero x = −u3/u2;
iii)
if u1≠ 0, u2 = 0, then \(\mathcal {P}(x)\) has a unique zero \(x=(-u_{3}/u_{1})^{q_{0}^{nu-v}}\).
iv)
if u1u2≠ 0, u3 = 0, then \(\mathcal {P}(x)=0\) has \({q_{0}^{d}}\) zeros in \(\mathbb {F}_{q^{n}}\), if − u2/u1 is a \(({q_{0}^{d}}-1)\) power of an element in \(\mathbb {F}_{q^{n}}\); otherwise, \(\mathcal {P}(x)=0\) has a single zero x = 0.
When u0≠ 0, we transform the equation \(\mathcal {P}(x)=0\) into
The polynomial P(x) can be seen as a reduced version of the original polynomial \(\mathcal {P}(x)\). It is clear that if a = 0, then P(x) = 0 has either no solution or
$$ m=\gcd({q_{0}^{v}}+1,q_{0}^{nu}-1) = \begin{cases} {q_{0}^{d}}+1, & \text{ if } \frac{nu}{\gcd(un, v)} \text{ is even,} \\ 2, & \text{ if } \frac{nu}{\gcd(un, v)} \text{ and $q_{0}$ are odd},\\ 1, & \text{ if } \frac{nu}{\gcd(un, v)} \text{ is odd, and $q_{0}$ is even}\\ \end{cases} $$
solutions, depending on whether − b is an m-th power; and that if b = 0, P(x) = 0 has either zero as its unique solution or \({q_{0}^{d}}\) solutions.
When ab≠ 0, the polynomial \(P(x)=x^{{q_{0}^{v}}+1}+ax + b\) over \(\mathbb {F}_{q_{0}^{un}}\) has a variety of applications in the construction of different sets with Singer parameters [10], construction error correcting codes [3], APN functions [4] and computing cross-correlation between m-sequences [11, 16].
The polynomial P(x) is a type of projective polynomials [1], which in general has the form
where \(x^{(i)}=x^{\frac {q^{i}-1}{q-1}}\). Bluher in [2] showed that the projective polynomial
$$ P(x)=x^{q^{r}+1}+ax + b, \qquad a, b \in \mathbb{F}^{*}_{q^{n}}, $$
(21)
where q is any prime power and r,n are arbitrary two positive integers, has exactly \(0, 1, 2, q^{r_{0}}+1\) possible number of zeros in \(\mathbb {F}_{q^{n}}\) with \(r_{0} = \gcd (r, n)\). Before the discussion on finding roots of P(x), it is important to know the possible number of roots and the corresponding conditions on the coefficients of P(x). In the following we will discuss different ways to find and express the zeros of P(x).
First, we present a relations among roots of P(x), which is inspired by [11, Lemma 22] and generalized for any prime power q.
Proposition 5
For positive integers r,n and a prime power q, the projective polynomial
has 0,1,2 or \(q^{r_{0}}+1\) roots \(x\in \mathbb {F}_{q^{n}}\), where \(r_{0}=\gcd (r,n)\). Moreover, if P has three different roots x0,x1 and \(x_{2}\in \mathbb {F}_{q^{n}}\), then all the roots can be characterized as
Thus P(λ + x0) = 0 if and only if \(\frac {1}{\lambda }\) is a solution of the affine equation \(L_{0}^{\prime }(z)=L_{0}(z)+1=0\), where
$$ L_{0}(z)=(x_{0}^{q^{r}}+a)z^{q^{r}}+x_{0}z. $$
Depending on x0, L0(z) may have a single solution if \(x_{0}^{q^{r}}+a = 0\) or \(q^{r_{0}}\) solutions if \(x_{0}(x_{0}^{q^{r}}+a)^{-1}\) is a \((q^{r_{0}}-1)\)-th power in \(\mathbb {F}_{q^{n}}\). Hence the affine equation \(L_{0}^{\prime }(z)=0\) has either 0, 1 or \(q^{r_{0}}\) nonzero solutions in \(\mathbb {F}_{q^{n}}\). For each nonzero solution z of \(L_{0}^{\prime }(z)=0\), we get a root \(x_{0}+\frac {1}{z}\) of the projective polynomial P(x).
On the other hand, when P(x) has three distinct roots x0,x1 and x2, we obtain two different roots \(\frac {1}{x_{1}-x_{0}}\) and \(\frac {1}{x_{2}-x_{0}}\) of the affine equation \(L_{0}^{\prime }(z)=0\) and their difference \( \frac {1}{x_{1}-x_{0}} - \frac {1}{x_{2}-x_{0}}\) is a root of the linearized polynomial L0(z) = 0, i.e.,
So \(y=\frac {1}{x_{1}-x_{0}}-\frac {1}{x_{2}-x_{0}}\) is a root of L0(z). Hence, \(z=\frac {1}{x_{1}-x_{0}}+Ay\) runs through all roots of \(L_{0}^{\prime }(z)\). Consequently, assuming (A0,A1,A2) = (1,A,−(A + 1)),
runs through all roots of P(x) different from x0, while A runs through \(\mathbb {F}_{q^{r_{0}}}\). □
The above result gives a method to express all the roots of the projective polynomials \(P(x)=x^{q^{r}+1}+ax+b, a, b\in \mathbb {F}_{q^n}^{*}\) in terms of the three known roots in \(\mathbb {F}_{q^n}\). Moreover, from its proof, a method to describe the roots of the projective polynomial P(x) in terms of the roots of the affine polynomial \(L_{0}^{\prime }(z)\). Nevertheless, the condition that characterizes the exact number of solutions to the affine equation \(L_{0}^{\prime }(z)=(x_{0}^{q^{r}}+a)z^{q^{r}}+x_{0}z+1\) is not clear.
In order to investigate the number of roots of \(P(x)=x^{q^{r}+1}+ax+b\) in \(\mathbb {F}_{q^{n}}\) according to its coefficients, we need to divide the discussion into two cases: q is even; or q is odd and \(\gcd (r,n)=1\).
4.1 Solving the equation P(x) = 0 over finite fields of characteristic 2
When the finite field \(\mathbb {F}_{q^{n}}\) has characteristic 2, the polynomial P(x) can be further converted to \(F_{c}(x) = x^{q^{r}+1}+x + c=0\), which was intensively studied in [17, 18, 21]. Helleseth and Kholosha in [17, 18] explicitly gave the root of Fc(x) = 0 in terms of the coefficient c when it has a single zero in \(\mathbb {F}_{q^{n}}\) and when it has two zeros in \(\mathbb {F}_{q^{n}}\) if \(\gcd (r,n)\) is odd. Very recently, Kim and Mesnager in [21] further studied the equation for the case q = 2 and \(\gcd (r, n)=1\) and explicitly calculated all possible zeros of Fc(x) in \(\mathbb {F}_{q^{n}}\). Since for general AGTG codes, the parameter q0 is always greater than 2. Below we shall recall the result by Helleseth and Kholosha [18] and apply it to find the roots of the projective polynomial P(x) in some cases.
Note that the AGTG codes are defined over \(\mathbb {F}_{q^{n}}\) with q a prime power. In this context, we assume q is a power of 2. To avoid potential confusion of notations, below we recall the result from [18] and treat the underlying finite field as \(\mathbb {F}_{2^{m}}\), where m is a positive integer. Let l be a positive integer with \(d=\gcd (l,m)\) and denote m1 = l/d. Define two sequences of polynomials in recurrence as follows: C1(x) = C2(x) = Z1(x) = 1, and
$$ F_{c}(x) = x^{2^{l}+1} + x + c, \quad c \in \mathbb{F}_{2^{m}}^{*}, $$
(24)
i) it has exactly one zero in \(\mathbb {F}_{2^{m}}\) if and only if \(Z_{m_{1}}(c)=0\) and \(C_{m_{1}}(c)\neq 0\); and this zero is given by \(x=(cC_{m_{1}}^{2^{l}-1}(c))^{2^{m-1}}\);
ii) it has exactly two zeros \(\mathbb {F}_{2^{m}}\) if and only if \(Z_{m_{1}}(c)\neq 0\) and \(\text {Tr}_{1}^{d}(\mathrm {N}^{m}_{d}(c)/Z^{2}_{m_{1}}(c))=0\), where the trace function \(\text {Tr}_{1}^{d}(z)={\sum }_{i=0}^{d-1}z^{2^{i}}\) and \(\mathrm {N}^{m}_{d}(z)\) is the norm function defined by \(\mathrm {N}^{m}_{d}(z) = {\prod }_{i=0}^{m_{1}-1}x^{2^{di}}\). Moreover, if d is odd, then these two zeros are \((W+\mu )Z_{m_{1}}(c)/C_{m_{1}}(c)\) for μ ∈{0,1}, where
iii) it has exactly 2d + 1 zeros in \(\mathbb {F}_{2^{m}}\) if and only if \(C_{m_{1}}(c)=0\).
As an illustration, we apply Proposition 6 i) to a general polynomial G(x) in the following proposition, which will be used to explicitly give the zero of P(x) in \(\mathbb {F}_{2^{m}}\) with m = nuw. The second cases can be applied in a similar manner.
over \(\mathbb {F}_{2^{m}}\) has exactly one zero in \(\mathbb {F}_{2^{m}}\) if and only if one of the following conditions holds:
i)
\(a_{2}=a_{1}^{2^{l}}\) and \(a_{3}=a_{1}^{2^{l}+1}\); or
ii)
\(a_{2}=a_{1}^{2^{l}}\), \(a_{3}\neq a_{1}^{2^{l}+1}\) and m1 is odd; or
iii)
\(a_{2}\neq a_{1}^{2^{l}}\), \(Z_{m_{1}}(c)=0\) and \(C_{m_{1}}(c)\neq 0\) with \(c={(a_{1}a_{2}+a_{3})}\big /{(a_{1}+a_{2}^{2^{n-l}})^{2^{l}+1}}\).
Moreover, for Cases (i) and (ii), the zero of G(x) is given by \(x=a_{1}+(a_{1}a_{2}+a_{3})^{\frac {1}{2^{l}+1}}\); for Case (iii), the unique zero is given by \(x=(a_{1}+a_{2}^{2^{n-l}})(cC_{m_{1}}^{2^{l}-1}(c))^{2^{n-1}}+a_{1}\).
Proof
It is relatively easy to verify Case i) and Case ii). In fact, when \(a_{2}=a_{1}^{2^{l}}\), one obtains the equation
The statement of Case i) immediately follows; and for Case ii), it is easily seen that the equation has a single solution only if \(\gcd (2^{l}+1, 2^{n}-1)=1\), equivalently, \(m_{1}=n/\gcd (l, n)\) is odd.
For Case iii), the equation G(x) = 0 can be reduced to a polynomial of the form \(F_{c}(y)=y^{2^{l}+1}+y+c=0\) by the following substitution
$$s =(a_{1}^{2^{l}}+a_{2})^{2^{m-l}}=(a_{1}+a_{2}^{2^{m-l}}) \text{ and } c=\frac{a_{1}a_{2}+a_{3}}{s^{2^{l}+1}} = \frac{a_{1}a_{2}+a_{3}}{(a_{1}+a_{2}^{2^{m-l}})^{(2^{l}+1)}}.$$
It is clear that y is a zero of \(F_{c}(y)=y^{2^{l}+1} + y + c\) if and only if x = sy + a1 is a zero of G(x). The desired statement follows from Proposition 6. □
Corollary 1
Let q0 = 2w for a positive integer w, l = wv, m = wun and \(m_{1}=m/\gcd (l, m)\). Let Ci(x),Zi(x) be defined as in (23) respectively. Then the polynomial \(x^{{q_{0}^{v}}+1} + a_{1}x^{{q_{0}^{v}}} + a_{2}x + a_{3} \) over \(\mathbb {F}_{q^{n}}\) has exactly one solution in \(\mathbb {F}_{q^{n}}\) given by
i)
x = a1 if \(a_{2}=a_{1}^{{q_{0}^{v}}}\) and a3 = a1a2;
ii)
\(x=a_{1}+(a_{1}a_{2}+a_{3})^{\frac {1}{{q_{0}^{v}}+1}}\) if \(a_{2}=a_{1}^{{q_{0}^{v}}}\), a3≠a1a2 and m1 is odd;
iii)
\(x=(a_{1}+a_{2}^{q_{0}^{n-v}})(cC_{m_{1}}^{{q_{0}^{v}}-1}(c))^{2^{m-1}}+a_{1}\) if \(a_{2}\neq a_{1}^{{q_{0}^{v}}}\), \(Z_{m_{1}}(c)=0\) and \(C_{m_{1}}(c)\neq 0\) with \(c={(a_{1}a_{2}+a_{3})}\big /{(a_{1}+a_{2}^{q_{0}^{n-v}})^{{q_{0}^{v}}+1}}\).
4.2 Solving the equation P(x) = 0 over \(\mathbb {F}_{q^{n}}\) when \(\gcd (r, n)=1\)
For the projective polynomial \(P(x)=x^{q^{r}+1}+ax+b\) with \(\gcd (r,n)=1\), McGuire and Sheekey recently in [28] gave a complete criteria on the coefficients a,b for P(x) = 0 to have 0,1,2 and q + 1 solutions in \(\mathbb {F}_{q^{n}}\) by the analysis of the companion matrix of P(x).
Let σ = qr and define a sequence of 2 × 2 matrices as follows:
$$ C_{0} = I_{2}, C=C_{1} = \left( \begin{array}{cc} 0&-b\\ 1& -a \end{array} \right), \text{ and } C_{k}=C_{k-1}C^{\sigma^{k-1}}=CC_{k-1}^{\sigma}, $$
(25)
where C1 is termed the companion matrix of P(x), and \(C_{k}^{{\sigma }^{i}}\) is the matrix obtained from Ck by applying to each of its entries the automorphism \(x\mapsto x^{{\sigma }^{i}}\). Furthermore, define a matrix
where N(a) denotes the field norm of \(a\in \mathbb {F}_{q^{n}}\) from \(\mathbb {F}_{q^{n}}\) to \(\mathbb {F}_{q}\) and u = bq/aq+ 1. Note that if Gn− 1 = 0 then AP will be a diagonal matrix.
Theorem 1
[28] The number of roots of the projective polynomial P(x) in \(\mathbb {F}_{q^{n}}\) is given by
where nλ is the dimension of the eigenspace of AP corresponding to the eigenvalue λ. The number of roots of L(x) in \(\mathbb {F}_{q^{n}}\) is given by \(q^{n_{1}}\). In other words, the dimension of the kernel of L(x) is 2 −Rank(AL − I2).
Theorem 2
[28] The polynomial P(x) has \(\frac {q^{d}-1}{q-1}\) roots in \(\mathbb {F}_{q^{n}}\) if and only if
$$A_{P}=\lambda I_{2},$$
where d is the dimension of the eigenspace of the matrix AP.
The characteristic polynomial \(S_{P}(x)\in \mathbb {F}_{q}[x]\) of a 2 × 2 matrix AP is of the form
where Tr(AP) is the trace of the matrix AP and it is defined as the sum of its diagonal elements and \(\det (A_{L})\) is the determinant of the matrix AP. The polynomial SP(x) can have 0,1 or 2 roots in \(\mathbb {F}_{q}\). For odd prime power q, the discriminant ΔS of the quadratic polynomial SP(x) is of the form
if ΔS is a non-square in \(\mathbb {F}_{q}\), SP(x) has no solutions in \(\mathbb {F}_{q}\), then P(x) has no solution in \(\mathbb {F}_{q^{n}}\).
Case 2)
If ΔS = 0, SP(x) has a unique solution λ in \(\mathbb {F}_{q}\), then P(x) has 1 or q + 1 solutions in \(\mathbb {F}_{q^{n}}\).
i)
If the dimension of the eigenspace corresponding to λ is two, then P(x) has q + 1 solutions in \(\mathbb {F}_{q^{n}}\). Due to Theorem 2, this will happen if and only if AP = λI2 i.e. Gn− 1 = 0 and \(G_{n}\in \mathbb {F}_{q}\).
ii)
If the dimension of the eigenspace corresponding to λ is one, then P(x) has one solution in \(\mathbb {F}_{q^{n}}\). Due to Theorem 2, this will happen if and only if AP is not a multiple of I2 i.e. Gn− 1≠ 0.
Case 3)
If ΔS is a non-zero square in \(\mathbb {F}_{q}\), SP(x) has two distinct roots (eigenvalues) in \(\mathbb {F}_{q}\). If dimension of the eigenspaces corresponding to each eigenvalue is one, due to Theorem 1, P(x) has two solutions in \(\mathbb {F}_{q^{n}}\).
Note that the projective polynomial \(P(x)=x^{q^{r}+1}+ax+b\) associates with the following linearized polynomial
$$ L(x) = xP(x^{q^{r}-1})= x^{q^{2r}} + ax^{q^{r}} + bx, \quad a, b \in \mathbb{F}_{q^{n}}. $$
It is readily seen that if we can efficiently solve the linearized polynomial L(x), the roots of P(x) can be obtained accordingly. In [28] the authors also applied companion matrices to study the number of roots of the above linearized polynomial. Further works on the roots of linearized polynomials can be found in [7, 32, 46].
Below we provide another way of studying the roots of the linearized polynomials L(x) via the Dickson matrix directly.
Theorem 3
Let α0,α1,…,αn− 1 be a basis of \(\mathbb {F}_{q^{n}}\) over \(\mathbb {F}_{q}\) and \(L(x)={\sum }_{i=0}^{n-1}{l_{i}}x^{q^{i}}\) a linearized polynomial in \({\mathcal{L}}_{n}(\mathbb {F}_{q^{n}})\) with rank r. Let D be the associate Dickson matrix of L(x). Suppose D0,D1,…,Dn− 1 are the n rows of D and Dr = z0D0 + z1D1 + ⋯ + zr− 1Dr− 1, where z0,…,zr− 1 in \(\mathbb {F}_{q^{n}}\). Then the elements
From Proposition 2 it is clear that the r-th row Dr can be expressed by a linear combination of D0,D1,…,Dr− 1 as \(D_{r}={\sum }_{t=0}^{r-1}z_{t}D_{t}\). That is to say, the vector z = (z0,…,zn− 1) = (z0,…,zr− 1,− 1,0,…,0) satisfies z ⋅ D = (0,…,0). Define
It follows from the pattern of the Dickson matrix D that \( {D_{z}^{T}} \cdot D = 0_{n\times n}, \) where 0n×n is the n × n all zero matrix.
According to the definition of Dz, it is clear that it has rank at least n − r. On the other hand, since the Dickson matrix D has rank r and all rows of Dz are solution of (y0,…,yn− 1)D = (0,…,0), the rank of Dz is at most n − r. This means that Dz has rank exactly n − r.
Let Mα be the Moore matrix associated with the basis α0,…,αn− 1. It follows from Lemma 2 i) and iv) that
Hence L(βi) = 0 for i = 0,1,…,n − 1. Moreover, since the Moore matrix Mα is nonsingular, the rank of Mβ is the same as that of the rank of Dz, which implies that the rank of β0,…,βn− 1 over \(\mathbb {F}_{q}\) is equal to n − r. Thus the linear combination of β0,…,βn− 1 over \(\mathbb {F}_{q}\) yields all the solution of L(x) in \(\mathbb {F}_{q^{n}}\). The desired conclusion follows. □
From Theorem 3, we see that finding solutions of a linearized polynomial can be converted to the task of computing the rank of its associated Dickson matrix D = (D0,…,Dn− 1)T and of finding a solution of Dr = x0D0 + ⋯ + xr− 1Dr− 1. In general, calculating the rank of a Dickson matrix D is nontrivial. Recently Csajbók in [6] proposed an interesting characterization of the rank of D.
Theorem 4
[6] Let D be the associated Dickson matrix of a linearized polynomial \(L(x)={\sum }_{i=0}^{n-1}l_{i}x^{q^{i}}\) over \(\mathbb {F}_{q^{n}}\). Denote by Dt the submatrix of D by removing the first t rows and the last t columns. Then L(x) has rank r if and only if
By Theorem 4, in order to determine the rank of the Dickson matrix associated with L(x), we need to calculate the determinant of D0,D1 and D2. The calculation for the case D2 is trivial. We only need to consider D0 and D1. To this end, we need the following result.
where N(a) denotes the field norm of \(a\in \mathbb {F}_{q^{n}}\) from \(\mathbb {F}_{q^{n}}\) to \(\mathbb {F}_{q}\), Mn is a tridiagonal matrix of order n and Mn− 1 = D1.
Note that D2 is a lower triangular matrix and its determinant can be directly computed |D2| = 1. In order to prove Theorem 5 we need the following observation.
Using Laplace expansion on the last column for n ≥ 2 gives
□
Proof of Theorem 5.
The proof follows immediately by applying Laplace expansion and Lemma 3. Note that the determinant of an upper (lower) triangular matrix is the product of the elements in its main diagonal.
Theorem 5 characterizes the conditions for the associated Dickson matrix of \(L(x)=x^{q^{2r}}+ax^{q^{r}}+bx\) to have rank n,n − 1 and n − 2. According to Theorem 3, one can obtain the roots of L(x) by finding the coefficients in the linear combination of the first n − 1 rows of D when D has rank n − 2 and coefficients in the linear combination of all rows of D when D has rank n − 1. Here the modified BM algorithm [43] will be employed, which requires \(\mathcal {O}(n^{2})\) operations in \(\mathbb {F}_{q^{n}}\) for these two cases. With the coefficients, the roots of L(x) are given by Theorem 3.
Instead of using Theorem 3 to compute the roots of the linearized polynomial L(x), one may use the probabilistic method given in [46]. The problem of finding the root space of the linearized polynomial L(x) is reduced to find the image space of another linearized polynomial K(x) derived from
$$x^{q^{n}}-x=W(x)\circ K(x),$$
where \(W(x)=\gcd (L(x),x^{q^{n}}-x)\). The idea is to randomly choose \(y_{i}\in \mathbb {F}_{q^{n}}\) and calculate K(yi) until the base elements for the image space of K(x) are obtained. Since L(x) has σ-degree 2, we need to find two basis elements K(y1),K(ys) for the image space of K(x). According to [46], the algorithm has complexity in the order of \(\mathcal {O}(n)\) operations in \(\mathbb {F}_{q^{n}}\). In general the expected number of \(y_{j}\in \mathbb {F}_{q^{n}}\) that need to be evaluated in order to find n linearly independent basis elements K(y0),…,K(yn− 1) is given by \(\frac {1}{1-q^{j-n}}\) [46]. □
5 The decoding algorithm of AGTG codes
With the discussion in Sections 3.2–4, we summarize the interpolation polynomial decoding algorithm of AGTG codes in Algorithm 2, and analyze its complexity accordingly.
Recall that reconstruction the error interpolation polynomial g(x) is to solve (15) based on the available information in (13). For the case that \(t=\frac {n-k}{2}\) with even n − k, according to Algorithm 1, Λ(n−k− 1)(x) is the linearized polynomial obtained after n − k iteration and its coefficients are the desired vector (λ1,…,λt). L is the linear complexity of Λ(n−k− 1)(x) and B(n−k− 1)(x) is the auxiliary linearized polynomial which is used to store the value of Λ(i)(x) with the largest degree Li such that Li < L. Hence one can obtain from Algorithm 1 two t-dimensional vectors λ and \(\lambda ^{\prime }\) over \(\mathbb {F}_{q^{n}}\). Then the solution of (15) is given as
If u0 = 0 calculate its zeros by cases i)-iv) after (19) or use Theorem 5, Berlekamp Massey Algorithm 1, Theorem 3 and Corollary 1 otherwise. The above process therefore can be integrated into the explicit Algorithm 2.
Remark 2
In the proposed Algorithm 2, we reconstruct the error interpolation polynomial g(x) by two major steps: calculate the coefficients λ1,…,λt by the modified BM algorithm, and deal with the case t = ⌊(n − k)/2⌋ by investigating the zero of the established polynomial \(\mathcal {P}(x)\). Section 4 investigates the solutions to \(\mathcal {P}(x)=0\) In the process, the calculation of the characterized conditions in Theorem 2 dominates the overall complexity. In Line 1 of Algorithm 2, the calculation of the interpolation polynomial γ(x) at points (αi,ri) for 1 ≤ i ≤ n. It has complexity in the order of \(\mathcal {O}(n^{3})\) operations over \(\mathbb {F}_{q^{n}}\), which can be further optimized by the method in [34]. For the remaining steps in Algorithm 2, the modified BM algorithm dominates the overall complexity. Since the modified BM algorithm has operations in the order of \(\mathcal {O}(n^{2})\) over \(\mathbb {F}_{q^{n}}\), the overall complexity of Algorithm 2 is in the order of \(\mathcal {O}(n^{2})\) over \(\mathbb {F}_{q^{n}}\) when normal bases are used in the interpolation step.
×
6 Conclusion
This paper further investigates the interpolation-based decoding algorithm for additive generalized twisted Gabidulin codes over finite fields with any characteristic. The main contribution of this paper includes the discussion of efficiently finding the roots of the involved project polynomials and their corresponding linearized polynomials.
Acknowledgments
The authors would like to thank the anonymous reviewers for their valuable suggestions and comments. The work of C. Li was supported by the Research Council of Norway (No. 247742/O70, No. 311646/O70), and was supported in part by the National Natural Science Foundation of China under Grant (No. 61771021).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
is given by the recurrence relation
where |M0| = 1 and |M− 1| = 0.