23.07.2020  Ausgabe 5/2020 Open Access
On decoding additive generalized twisted Gabidulin codes
 Zeitschrift:
 Cryptography and Communications > Ausgabe 5/2020
Wichtige 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 spacetime 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 subfamily of MRD codes are
Gabidulin codes which is the rank metric analog of ReedSolomon 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 subfamilies 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 BerlekampMassey and WelchBerlekamp 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 errorcorrecting 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 {d1}{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 {d1}{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 {d1}{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
q
^{r} elements for an arbitrary positive integer
r.
Anzeige
2.1 Linearized polynomial
A polynomial of the form
\(L(x)={\sum }_{i=0}^{k1}l_{i}x^{q^{i}}\) over
\(\mathbb {F}_{q^{n}}\) is known as a
qpolynomial [
29]. Define a set
It is easy to verify that
\(\left ({\mathcal{L}}_{k}(\mathbb {F}_{q^{n}}), +, \circ \right )\) forms a noncommutative
\(\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 noncommutative in general. For a nonzero
\(L(x)={\sum }_{i=0}^{k1}l_{i}x^{q^{i}}\) over
\(\mathbb {F}_{q^{n}}\), its
qdegree is given by
\(\deg _{q}(L(x))=\max \limits \{0\leq i<k  l_{i}\neq 0\}\).
$$ \mathcal{L}_{k}(\mathbb{F}_{q^{n}})=\left\{L(x)=\sum\limits_{i=0}^{k1}l_{i}x^{q^{i}}  L(x)\in \mathbb{F}_{q^{n}}[x]/(x^{q^{n}}x) \right\}. $$
(1)
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(
c
_{1}
x +
c
_{2}
y) =
c
_{1}
L(
x) +
c
_{2}
L(
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}^{k1}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\}\).
$$ \text{Rank}(L) := \dim_{\mathbb{F}_{q}}(\text{Img}(L))=n\dim_{\mathbb{F}_{q}}(\text{Ker}(L)), $$
For a linearized polynomial
\(L(x)={\sum }_{i=0}^{k}l_{i}x^{q^{i}}\) with
qdegree
k, i.e.,
l
_{k}≠ 0, it is clear that Ker(
L) has at most
q
^{k} elements. From the definition, the linearized polynomial
L(
x) has
Sheekey in [
40] characterizes a necessary condition for
L(
x) to have rank
n −
k as below.
$$ \text{Rank}(L) = n  \dim_{\mathbb{F}_{q}}(\text{Ker}(L)) \geq n  k. $$
Lemma 1
[
40] Suppose a linearized polynomial
\(L(x)=l_{0}x+l_{1}x^{q}+\cdots +l_{k}x^{q^{k}}\),
l
_{k}≠ 0, in
\({\mathcal{L}}_{n}({\mathbb {F}_{q^{n}}})\) has
q
^{k} roots in
\(\mathbb {F}_{q^{n}}\). Then
where
\(\text {Norm}_{q^{n}/q}(x)=x^{1+q+{\cdots } + q^{n1}}\) is the norm function from
\(\mathbb {F}_{q^{n}}\) to
\(\mathbb {F}_{q}\).
$$ \text{Norm}_{q^{n}/q}(l_{k})= (1)^{nk}\text{Norm}_{q^{n}/q}(l_{0}), $$
(2)
Furthermore, the necessary and sufficient condition for
L(
x) with
qdegree
k to have
q
^{k} 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 = (
a
_{0},…,
a
_{n− 1}) over
\(\mathbb {F}_{q^{n}}\), the Dickson matrix associated with
a is given by
and the Moore matrix associated with
a is given by
$$ D_{a}=\left( \begin{array}{l} a_{ij{(\text{mod}n)}}^{q^{j}} \end{array}\right)_{n\times n}=\left( \begin{array}{llll} a_{0}& a_{n1}^{q}& \ldots& a_{1}^{q^{n1}}\\ a_{1}& {a_{0}^{q}}&\ldots& a_{2}^{q^{n1}}\\ \vdots& \vdots&\ddots& \vdots\\ a_{n1}& a_{n2}^{q}&\ldots& a_{0}^{q^{n1}} \end{array}\right), $$
(3)
$$ M_{a}=\left( \begin{array}{l} a_{i}^{q^{j}} \end{array}\right)_{n\times n}=\left( \begin{array}{llll} a_{0}& {a_{0}^{q}}& \ldots& a_{0}^{q^{n1}}\\ a_{1}& {a_{1}^{q}}&\ldots& a_{1}^{q^{n1}}\\ \vdots& \vdots&\ddots& \vdots\\ a_{n1}& a_{n1}^{q}&\ldots& a_{n1}^{q^{n1}} \end{array}\right). $$
(4)
The Dickson matrix and Moore matrix have the following properties:
Lemma 2
For two vectors
a = (
a
_{0},…,
a
_{n− 1}) and
b = (
b
_{0},…,
b
_{n− 1}) over
\(\mathbb {F}_{q^{n}}\),
i)
\({D_{a}^{T}} = D_{a^{\prime }}\) with
\(a^{\prime }=(a_{0}, a_{n1}^{q}, \ldots , a_{1}^{q^{n1}})\);
ii)
D
_{a} ⋅
D
_{b} =
D
_{u}, where
u = (
u
_{0},…,
u
_{n− 1}) with
\(u_{i} ={\sum }_{j=0}^{n1}a_{ij(\text {mod } n)}^{q^{j}}b_{j}\);
iii)
\({M_{a}^{T}}\cdot M_{b} = D_{v}\), where
v = (
v
_{0},…,
v
_{n− 1}) with
\(v_{i} ={\sum }_{j=0}^{n1}a_{j}^{q^{i}}b_{j}\);
iv)
M
_{a} ⋅
D
_{b} =
M
_{w}, where
w = (
w
_{0},…,
w
_{n− 1}) with
\(w_{i} ={\sum }_{j=0}^{n1}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.
$$ \varphi\left( \sum\limits_{i=0}^{n1}l_{i}x^{q^{i}}\right) = D_{(l_{0}, \ldots, l_{n1})}=\begin{pmatrix} l_{ij(\text{mod }n)}^{q^{j}} \end{pmatrix}_{n\times n}. $$
(5)
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
$$ \text{Rank}(L)= \text{Rank}(D) \text{and} \det (L)=\det (D). $$
It is well known [
24] that given a linearized polynomial
\(L(x)={\sum }_{i=0}^{n1}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 nonsingular; or equivalently its associated Moore matrix is nonsingular. 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}^{n1}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
σ =
q
^{s} with
\(\gcd (s,n)=1\). The
σpolynomial
which reduces to a
qpolynomial over
\(\mathbb {F}_{q^{n}}\) for
s = 1, is a generalization of
qpolynomial. The aforementioned properties of
qpolynomials can be similarly obtained as for
σpolynomials. For instance, the
σpolynomial
\(L_{\sigma }(x)={\sum }_{i=0}^{k}l_{i}x^{\sigma ^{i}}\) with
l
_{k}≠ 0 also has
\( \text {Rank}(L) = n  \dim _{\mathbb {F}_{q}}(\text {Ker}(L)) \geq nk \) [
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.
$$ L_{\sigma}(x)=l_{0}x+l_{1}x^{\sigma} + {\cdots} + l_{n1}x^{\sigma^{n1}}, \quad l_{i} \in \mathbb{F}_{q^{n}}, $$
2.2 Maximum rank distance (MRD) codes
Let
n and
m be two positive integers. The
rank of a vector
a = (
a
_{1},
a
_{2},…,
a
_{n}) 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
a
_{i}’s over
\(\mathbb {F}_{q}\). The
rank distance between two vectors
\(a,b\in \mathbb {F}_{q^{m}}\) is defined as
d
_{R}(
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
Singletonlike bound
\(M\leq q^{\min \limits \{m(n d+1),n(md+1) \}}\).
The Gabidulin codes are the most wellknown 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
σ =
q
^{s} 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}^{k1}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.
$$ \mathcal{G}\mathcal{G}_{n, k}= \left\{(f(\alpha_{0}), f(\alpha_{1}),\ldots, f(\alpha_{n1}))  f(x)=\sum\limits_{i=0}^{k1}f_{i}x^{\sigma^{i}} \text{ and } f_{i} \in \mathbb{F}_{q^{m}} \right\}, $$
(6)
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
qdegree
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.
$$ \mathcal{H}_{k,s}(\eta, h) = \left\{ \sum\limits_{i=0}^{k1}f_{i}x^{q^{si}} + \eta f_{0}^{q^{h}}x^{q^{sk}}  f_{i} \in \mathbb{F}_{q^{n}} \right\} $$
(7)
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 interpolationbased 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
q
^{nk} and minimum rank distance
n −
k + 1.
$$ \mathcal{H}_{k,s,q_{0}}(\eta,h)= \left\{ \sum\limits_{i=0}^{k1}f_{i}x^{q^{si}} + \eta f_{0}^{{q_{0}^{h}}}x^{q^{sk}}  f_{i} \in \mathbb{F}_{q^{n}} \right\} $$
(8)
The above AGTG codes reduce to GTG codes when
q
_{0} =
q and to GG codes when
η = 0 or
q
_{0} = 2. Very recently, Sheekey in [
42] showed the existence of a new family of MRD codes which is not equivalent to AGTG codes and TrombettiZhou 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} =
q
^{si} 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 = (
f
_{0},…,
f
_{k− 1}) is the evaluation of the following linearized polynomial at points
α
_{0},
α
_{1},…,
α
_{n− 1}:
Let
\(\tilde {f}=(f_{0},\ldots , f_{k1}, \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.,
Then the encoding of AGTG codes can be expressed as
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_{k1}, \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.
$$f(x)=\sum\limits_{i=0}^{k1}f_{i}x^{[i]}+\eta f_{0}^{{q_{0}^{h}}}x^{[k]}.$$
$$ M= \begin{pmatrix} \alpha_{i}^{[j]} \end{pmatrix}_{n\times n}= \begin{pmatrix} \alpha_{0} & \alpha_{0}^{[1]} & {\ldots} & \alpha_{0}^{[n1]}\\ \alpha_{1}& \alpha_{1}^{[1]} & {\ldots} & \alpha_{1}^{[n1]} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ \alpha_{n1} & \alpha_{1}^{[1]} & {\ldots} & \alpha_{n1}^{[n1]} \\ \end{pmatrix}. $$
(9)
$$ (f_{0},\ldots, f_{k1})\mapsto c=(f(\alpha_{0}), \ldots, f(\alpha_{n1}))=\tilde{f}M^{T}. $$
(10)
3.2 Decoding AGTG codes with an errorinterpolation 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 {nk}{2}\rfloor \), the unique decoding task is to recover the unique codeword
c such that
\(d_{R}(c,r)\leq \lfloor \frac {nk}{2}\rfloor \).
When the rank
t of the error is strictly smaller than
\(\frac {nk}{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 2
t ≤
n − (
k + 1). However, when the rank
t achieves the unique errorcorrecting radius, i.e., (
n −
k) is even and
\(t=\frac {nk}{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 selfcompleteness, we briefly describe the process of interpolation decoding and how it is transformed to solving certain quadratic equation for the case that 2
t =
n −
k.
Suppose
\(g(x)={\sum }_{i=0}^{n1}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 = (
g
_{0},…,
g
_{n− 1}). From (
10) and (
11) it follows that
This is equivalent to
Letting
γ = (
γ
_{0},…,
γ
_{n− 1}) =
r ⋅ (
M
^{T})
^{− 1}, we obtain
since
\(\eta f_{0}^{{q_{0}^{h}}}+g_{k}=\gamma _{k},\) and
f
_{0} +
g
_{0} =
γ
_{0}.
$$ g(\alpha_{i})=e_{i}=r_{i}c_{i}, \quad i=0, \ldots, n1. $$
(11)
$$ r = c+e = (\tilde{f}+g) M^{T}. $$
$$ r \cdot (M^{T})^{1}=(f_{0}+g_{0},\ldots, f_{k1}+g_{k1}, \eta f_{0}^{{q_{0}^{h}}}+g_{k}, g_{k+1}, \ldots, g_{n1}). $$
(12)
$$ (g_{k+1}, \ldots, g_{n1}) = (\gamma_{k+1}, \ldots, \gamma_{n1}) \text{ and } \eta g_{0}^{{q_{0}^{h}}} + g_{k} = \gamma_{k}\eta \gamma_{0}^{{q_{0}^{h}}} $$
(13)
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
G
_{j} is the
jth column of
G.
$$ G=\begin{pmatrix}g^{[j]}_{ij~(\text{mod~}n)} \end{pmatrix}_{n\times n} = \begin{pmatrix} G_{0} & G_{1} & {\ldots} & G_{n1} \end{pmatrix} $$
(14)
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
G
_{0} can be expressed as a linear combination of
G
_{1},…,
G
_{t}, namely,
G
_{0} =
λ
_{1}
G
_{1} +
λ
_{2}
G
_{2} + ⋯ +
λ
_{t}
G
_{t}, where
λ
_{1},…,
λ
_{t} are elements in
\(\mathbb {F}_{q^{n}}\). This yields the following recursive equations
where the subscripts in
g
_{i}’s are taken modulo
n. Recall that the elements
g
_{k+ 1},…,
g
_{n− 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
qlinearized 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:
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.
$$ g_{i} = \lambda_{1} g^{[1]}_{i1} + \lambda_{2} g^{[2]}_{i2} + {\cdots} + \lambda_{t} g^{[t]}_{it}, \quad 0\leq i < n, $$
(15)
$$ g_{i} = \lambda_{1} g^{[1]}_{i1} + \lambda_{2} g^{[2]}_{i2} + {\cdots} + \lambda_{t} g^{[t]}_{it}, \quad k+t+1\leq i <n. $$
(16)
As discussed in the beginning of this section, for an error vector with
\(\text {Rank}(e)=t \leq \lfloor \frac {nk}{2}\rfloor \), i.e., 2
t +
k ≤
n, we can divide the discussion into two cases.
Case 1:
2
t +
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 BerlekampMassey (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 selfcompleteness we recall the modified BM algorithm in Algorithm 1. The coefficients of Λ
^{(n−k− 1)}(
x) are the desired
λ
_{i}’s.
Case 2:
2
t +
k =
n. In this case (
16) gives
n −
k −
t − 1 =
t − 1 independent affine equations in variables
λ
_{1},…,
λ
_{t}. For such an underdetermined 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).
$$ \lambda+\omega \lambda^{\prime} =(\lambda_{1}+\omega\lambda^{\prime}_{1}, \ldots, \lambda_{t}+\omega \lambda^{\prime}_{t}), $$
×
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
Rearranging the equations gives
where
c
_{0},
c
_{1},
c
_{2},
c
_{3} are derived from
λ,
\(\lambda ^{\prime }\) and the known
g
_{i}’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
This equation can be rearranged as
where
\(q={q_{0}^{u}}\),
v =
h +
u
s
t,
u
_{0},…,
u
_{3} are derived from
c
_{0},…,
c
_{5} and
η.
$$ \begin{array}{rcllll} g_{0}&=& (\lambda_{1}+\omega \lambda^{\prime}_{1}, \ldots, \lambda_{t}+\omega \lambda^{\prime}_{t}) \cdot (g_{n1}^{[1]}, \ldots, g_{nt}^{[t]})^{T} \\ g_{k+t}&=& (\lambda_{1}+\omega \lambda^{\prime}_{1}, \ldots, \lambda_{t}+\omega \lambda^{\prime}_{t}) \cdot (g_{k+t1}^{[1]}, \ldots, g_{k}^{[t]})^{T} \end{array} $$
$$ \begin{array}{rcl} g_{0} & = & c_{0} + c_{1} \omega \\ g_{k+t} &= & c_{2}+c_{3} \omega + (\lambda_{t}+\lambda^{\prime}_{t}\omega)g_{k}^{[t]}, \end{array} $$
(17)
$$ (\lambda_{t}+\lambda^{\prime}_{t}\omega)(c_{4}+\eta (c_{0}+c_{1}\omega)^{{q_{0}^{h}}})^{[t]} g_{k+t}+(c_{2}+c_{3}\omega)=0. $$
$$ u_{0}\omega^{{q_{0}^{v}}+1} + u_{1}\omega^{{q_{0}^{v}}}+u_{2}\omega + u_{3}=0. $$
(18)
Since the error
e with rank
\(t=\frac {nk}{2}=\frac {d1}{2}\) can be uniquely decoded, the polynomial
should have roots
w in
\(\mathbb {F}_{q^{n}}\) that lead to solutions
\(\lambda +\omega \lambda ^{\prime }\) in (
16) and (
g
_{0},
g
_{k}) in (
17).
$$ \mathcal{P}(x)=u_{0}x^{{q_{0}^{v}}+1}+u_{1}x^{{q_{0}^{v}}} + u_{2}x + u_{3} $$
With the coefficients
λ
_{1},…,
λ
_{t} in Step 1 and the initial state
g
_{n− 1},…,
g
_{n−t}, one can recursively compute
g
_{0},…,
g
_{k− 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 (
g
_{n− 1},…,
g
_{n−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}^{n1}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)\).
$$ \mathcal{P}(x)=u_{0}x^{{q_{0}^{v}}+1}+u_{1}x^{{q_{0}^{v}}} + u_{2}x + u_{3} = 0. $$
(19)
Assume
d = (
v,
u
n). We start with the simplest case that
u
_{0} = 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 (
u
_{1},
u
_{2}) = (0,0), then
\(\mathcal {P}(x)\) has no zero if
u
_{3}≠ 0 and every element in
\(\mathbb {F}_{q^{n}}\) as a zero otherwise;
ii)
if
u
_{1} = 0,
u
_{2}≠ 0, then
\(\mathcal {P}(x)\) has a unique zero
x = −
u
_{3}/
u
_{2};
iii)
if
u
_{1}≠ 0,
u
_{2} = 0, then
\(\mathcal {P}(x)\) has a unique zero
\(x=(u_{3}/u_{1})^{q_{0}^{nuv}}\).
iv)
if
u
_{1}
u
_{2}≠ 0,
u
_{3} = 0, then
\(\mathcal {P}(x)=0\) has
\({q_{0}^{d}}\) zeros in
\(\mathbb {F}_{q^{n}}\), if −
u
_{2}/
u
_{1} 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
u
_{0}≠ 0, we transform the equation
\(\mathcal {P}(x)=0\) into
where
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
solutions, depending on whether −
b is an
mth power; and that if
b = 0,
P(
x) = 0 has either zero as its unique solution or
\({q_{0}^{d}}\) solutions.
$$ P(x) = \frac{1}{u_{0}}\mathcal{P}(xu_{1}u_{0}^{1}) = x^{{q_{0}^{v}}+1}+ax + b = 0, $$
(20)
$$a=\frac{u_{2}}{u_{0}}+\left( \frac{u_{1}}{u_{0}}\right)^{{q_{0}^{v}}} \mathrm{and } b=\frac{u_{3}}{u_{0}}\frac{u_{1}u_{2}}{{u_{0}^{2}}}+\frac{u_{1}}{u_{0}}\left( \frac{u_{1}}{u_{0}}\right)^{{q_{0}^{v}}}+\left( \frac{u_{1}}{u_{0}}\right)^{{q_{0}^{v}}+1}.$$
$$ 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} $$
When
a
b≠ 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 crosscorrelation between
msequences [
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}{q1}}\). Bluher in [
2] showed that the projective polynomial
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).
$$a_{0}+a_{1}x+a_{2}x^{(2)}+\cdots+a_{l}x^{(l)}\in \mathbb{F}_{q^{n}}[x],$$
$$ P(x)=x^{q^{r}+1}+ax + b, \qquad a, b \in \mathbb{F}^{*}_{q^{n}}, $$
(21)
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
x
_{0},
x
_{1} and
\(x_{2}\in \mathbb {F}_{q^{n}}\), then all the roots can be characterized as
where (
A
_{0},
A
_{1},
A
_{2})≠(0,0,0) and
A
_{0} +
A
_{1} +
A
_{2} = 0.
$$P(x)=x^{q^{r}+1}+ax+b,~~~~a,b\in\mathbb{F}_{q^{n}}^{*}$$
$$ x_{A_{0},A_{1},A_{2}}=x_{0}x_{1}x_{2}\frac{\frac{A_{0}}{x_{0}}+\frac{A_{1}}{x_{1}}+\frac{A_{2}}{x_{2}}}{A_{0}x_{0}+A_{1}x_{1}+A_{2}x_{2}} $$
(22)
Proof
Suppose
P(
x
_{0}) = 0 for an element
x
_{0} in
\(\mathbb {F}_{q^{n}}\). For a nonzero
\(\lambda \in \mathbb {F}_{q^{n}}^{*}\), one has
$$ \begin{array}{@{}rcl@{}} P(\lambda+x_{0})&=&(\lambda+x_{0})^{q^{r}+1}+a(\lambda+x_{0})+b\\ &=& (\lambda^{q^{r}+1}+x_{0}\lambda^{q^{r}}+\lambda x_{0}^{q^{r}} + x_{0}^{q^{r}+1}) + \lambda a + ax_{0}+b \\ &=&(\lambda^{q^{r}+1}+x_{0}\lambda^{q^{r}}+(x_{0}^{q^{r}}+a)\lambda) + P(x_{0})\\ &=&\lambda^{q^{r}+1}(1+x_{0}/\lambda+(x_{0}^{q^{r}}+a)/\lambda^{q^{r}}). \end{array} $$
Thus
P(
λ +
x
_{0}) = 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
Depending on
x
_{0},
L
_{0}(
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).
$$ L_{0}(z)=(x_{0}^{q^{r}}+a)z^{q^{r}}+x_{0}z. $$
On the other hand, when
P(
x) has three distinct roots
x
_{0},
x
_{1} and
x
_{2}, 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
L
_{0}(
z) = 0, i.e.,
$$ \begin{array}{@{}rcl@{}} L_{0}^{\prime}\left( \frac{1}{x_{1}x_{0}}\right)=&L_{0}\left( \frac{1}{x_{1}x_{0}}\right)+1=0,\\ L_{0}^{\prime}\left( \frac{1}{x_{2}x_{0}}\right)=&L_{0}\left( \frac{1}{x_{2}x_{0}}\right)+1=0,\\ L_{0}^{\prime}\left( \frac{1}{x_{1}x_{0}}\right)L_{0}^{\prime}\left( \frac{1}{x_{2}x_{0}}\right)=&L_{0}\left( \frac{1}{x_{1}+x_{0}}\frac{1}{x_{2}+x_{0}}\right)=0. \\ \end{array} $$
So
\(y=\frac {1}{x_{1}x_{0}}\frac {1}{x_{2}x_{0}}\) is a root of
L
_{0}(
z). Hence,
\(z=\frac {1}{x_{1}x_{0}}+Ay\) runs through all roots of
\(L_{0}^{\prime }(z)\). Consequently, assuming (
A
_{0},
A
_{1},
A
_{2}) = (1,
A,−(
A + 1)),
runs through all roots of
P(
x) different from
x
_{0}, while
A runs through
\(\mathbb {F}_{q^{r_{0}}}\). □
$$\begin{aligned} x^{(A)} &=x_{0} + \frac{1}{z} =x_{0}+ \frac{1}{\frac{1}{x_{1}x_{0}}+Ay} \\&=x_{0}+ \frac{1}{\frac{1}{x_{1}x_{0}}+\frac{A}{x_{1}x_{0}}\frac{A}{x_{2}x_{0}}} \\&= x_{0}+ \frac{(x_{1}x_{0})(x_{2}x_{0})}{(x_{2}x_{0})+A(x_{2}x_{0})A(x_{1}x_{0})} \\&=x_{0}x_{1}x_{2}.\frac{\frac{1}{x_{0}}+\frac{A}{x_{1}}\frac{(A+1)}{x_{2}}}{x_{0}+Ax_{1} (A+1)x_{2}} \\&=x_{0}x_{1}x_{2}.\frac{\frac{A_{0}}{x_{0}}+\frac{A_{1}}{x_{1}}+\frac{A_{2}}{x_{2}}}{A_{0}x_{0}+A_{1}x_{1} A_{2}x_{2}} = x_{(A_{0},A_{1},A_{2})} \end{aligned} $$
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
F
_{c}(
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
F
_{c}(
x) in
\(\mathbb {F}_{q^{n}}\). Since for general AGTG codes, the parameter
q
_{0} 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
m
_{1} =
l/
d. Define two sequences of polynomials in recurrence as follows:
C
_{1}(
x) =
C
_{2}(
x) =
Z
_{1}(
x) = 1, and
for
i = 1,2,…,
m
_{1} − 1.
$$ \begin{array}{l} C_{i+2}(x) = C_{i+1}(x) + x^{2^{il}}C_{i}(x), \quad Z_{i}(x) = C_{i+1}(x) + xC_{i1}^{2^{l}}(x) \end{array} $$
(23)
Proposition 6
[
18, Prop. 35] Gvien a polynomial
$$ 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^{m1}}\);

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}^{d1}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$$ W= \frac{C_{m+1}(c)}{Z_{m+1}(c)} + \sum\limits_{i=0}^{\frac{d1}{2}}\left( \frac{\mathrm{N}^{m}_{d}(c)}{Z^{2}_{m_{1}}(c)}\right)^{2^{2i}}; $$

iii) it has exactly 2 ^{d} + 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 =
n
u
w. The second cases can be applied in a similar manner.
Proposition 7
The polynomial
over
\(\mathbb {F}_{2^{m}}\) has exactly one zero in
\(\mathbb {F}_{2^{m}}\) if and only if one of the following conditions holds:
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^{nl}})(cC_{m_{1}}^{2^{l}1}(c))^{2^{n1}}+a_{1}\).
$$ G(x) = x^{2^{l}+1} + a_{1} x^{2^{l}} + a_{2} x + a_{3} $$
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
m
_{1} 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^{nl}})^{2^{l}+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.
$$ G(x)=(x+a_{1})^{2^{l}+1}+(a_{1}a_{2}+a_{3})=0. $$
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
where
It is clear that
y is a zero of
\(F_{c}(y)=y^{2^{l}+1} + y + c\) if and only if
x =
s
y +
a
_{1} is a zero of
G(
x). The desired statement follows from Proposition 6. □
$$ \begin{array}{llll} F_{c}(y) &=&s^{(2^{l}+1)}G(sy+a_{1}) \\ &= &s^{(2^{l}+1)}\left( (sy+a_{1})^{2^{l}+1} + a_{1} (sy+a_{1})^{2^{l}} + a_{2} (sy+a_{1}) + a_{3}\right) \\&=&s^{(2^{l}+1)}\left( s^{2^{l}+1}y^{2^{l}+1} + s(a_{1}^{2^{l}}+a_{2})y + a_{1}a_{2}+a_{3}\right) \\&=&y^{2^{l}+1} + y + c, \end{array} $$
$$s =(a_{1}^{2^{l}}+a_{2})^{2^{ml}}=(a_{1}+a_{2}^{2^{ml}}) \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^{ml}})^{(2^{l}+1)}}.$$
Corollary 1
Let
q
_{0} = 2
^{w} for a positive integer
w,
l =
w
v,
m =
w
u
n and
\(m_{1}=m/\gcd (l, m)\). Let
C
_{i}(
x),
Z
_{i}(
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 =
a
_{1} if
\(a_{2}=a_{1}^{{q_{0}^{v}}}\) and
a
_{3} =
a
_{1}
a
_{2};
ii)
\(x=a_{1}+(a_{1}a_{2}+a_{3})^{\frac {1}{{q_{0}^{v}}+1}}\) if
\(a_{2}=a_{1}^{{q_{0}^{v}}}\),
a
_{3}≠
a
_{1}
a
_{2} and
m
_{1} is odd;
iii)
\(x=(a_{1}+a_{2}^{q_{0}^{nv}})(cC_{m_{1}}^{{q_{0}^{v}}1}(c))^{2^{m1}}+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}^{nv}})^{{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
σ =
q
^{r} and define a sequence of 2 × 2 matrices as follows:
where
C
_{1} is termed the companion matrix of
P(
x), and
\(C_{k}^{{\sigma }^{i}}\) is the matrix obtained from
C
_{k} by applying to each of its entries the automorphism
\(x\mapsto x^{{\sigma }^{i}}\). Furthermore, define a matrix
Since
\(\det (C_{1})=b\) and
\(N(b)=b^{1+\sigma +{\cdots } +\sigma ^{n1}}\), one can easily verify
\(\det (A_{P})=N(b)\). Denote
where
\(a^{(i)}=a^{\frac {{\sigma }^{i}1}{\sigma 1}}\) and
G
_{n} can be computed using the recursive relation
Then it follows that
Hence one can express
A
_{P} associated with
P(
x) in terms of
G
_{n} as follows:
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 =
b
^{q}/
a
^{q+ 1}. Note that if
G
_{n− 1} = 0 then
A
_{P} will be a diagonal matrix.
$$ C_{0} = I_{2}, C=C_{1} = \left( \begin{array}{cc} 0&b\\ 1& a \end{array} \right), \text{ and } C_{k}=C_{k1}C^{\sigma^{k1}}=CC_{k1}^{\sigma}, $$
(25)
$$ A_{P}=C_{n}=CC^{\sigma}{\cdots} C^{{\sigma}^{n1}}. $$
(26)
$$ X=\left( \begin{matrix} b/a& 0\\ 0& 1 \end{matrix}\right), Z_{n}=\left( \begin{matrix} a^{(n1)}& 0\\ 0&a^{(n)} \end{matrix}\right) \text{ and } \quad Y_{m}=\left( \begin{matrix} G_{n2}^{\sigma}& G_{n1}^{\sigma}\\ G_{n1}& G_{n} \end{matrix}\right), $$
(27)
$$ G_{n}^{{\sigma}^{2}}G_{n}=G_{n1}^{\sigma}G_{n1}^{{\sigma}^{2}}. $$
(28)
$$ A_{P}=C_{n}=XY_{n}Z_{n}. $$
(29)
$$ A_{P}= N(a)\left( \begin{matrix} u^{q^{1}}.G_{n2}^{\sigma}& \frac{b}{a}.G_{n1}^{\sigma}\\ \frac{1}{a^{{\sigma}^{1}}}.G_{n1}& G_{n} \end{matrix}\right) $$
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
A
_{P} 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(
A
_{L} −
I
_{2}).
$$\sum\limits_{\lambda\in \mathbb{F}_{q}}^{~}\frac{q^{n_{\lambda}}1 }{q1},$$
Theorem 2
[
28] The polynomial
P(
x) has
\(\frac {q^{d}1}{q1}\) roots in
\(\mathbb {F}_{q^{n}}\) if and only if
where
d is the dimension of the eigenspace of the matrix
A
_{P}.
$$A_{P}=\lambda I_{2},$$
The characteristic polynomial
\(S_{P}(x)\in \mathbb {F}_{q}[x]\) of a 2 × 2 matrix
A
_{P} is of the form
where Tr(
A
_{P}) is the trace of the matrix
A
_{P} and it is defined as the sum of its diagonal elements and
\(\det (A_{L})\) is the determinant of the matrix
A
_{P}. The polynomial
S
_{P}(
x) can have 0,1 or 2 roots in
\(\mathbb {F}_{q}\). For odd prime power
q, the discriminant Δ
_{S} of the quadratic polynomial
S
_{P}(
x) is of the form
$$ S_{P}(x)=x^{2}\text{Tr}(A_{P})x+\det(A_{P}), $$
(30)
$$ \begin{array}{@{}rcl@{}} {\Delta}_{S}=&\text{Tr}(A_{P})^{2}4\det(A_{P}). \end{array} $$
(31)
Case 1)
if Δ
_{S} is a nonsquare in
\(\mathbb {F}_{q}\),
S
_{P}(
x) has no solutions in
\(\mathbb {F}_{q}\), then
P(
x) has no solution in
\(\mathbb {F}_{q^{n}}\).
Case 2)
If Δ
_{S} = 0,
S
_{P}(
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
A
_{P} =
λ
I
_{2} i.e.
G
_{n− 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
A
_{P} is not a multiple of
I
_{2} i.e.
G
_{n− 1}≠ 0.
Case 3)
If Δ
_{S} is a nonzero square in
\(\mathbb {F}_{q}\),
S
_{P}(
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
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].
$$ L(x) = xP(x^{q^{r}1})= x^{q^{2r}} + ax^{q^{r}} + bx, \quad a, b \in \mathbb{F}_{q^{n}}. $$
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}^{n1}{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
D
_{0},
D
_{1},…,
D
_{n− 1} are the
n rows of
D and
D
_{r} =
z
_{0}
D
_{0} +
z
_{1}
D
_{1} + ⋯ +
z
_{r− 1}
D
_{r− 1}, where
z
_{0},…,
z
_{r− 1} in
\(\mathbb {F}_{q^{n}}\). Then the elements
are roots of
L(
x). Moreover, the kernel of
L(
x) in
\(\mathbb {F}_{q^{n}}\) is given by
$$ {\upbeta}_{i} =\sum\limits_{j=0}^{r1} \alpha_{i}^{q^{nj}}z_{j}^{q^{nj}}  \alpha_{i}^{q^{nr}} , \quad i=0, 1, \ldots, n1, $$
$$ \ker(L) = \text{span}_{\mathbb{F}_{q}}\langle {\upbeta}_{0}, {\upbeta}_{1}, \ldots, {\upbeta}_{n1}\rangle. $$
Proof
From Proposition 2 it is clear that the
rth row
D
_{r} can be expressed by a linear combination of
D
_{0},
D
_{1},…,
D
_{r− 1} as
\(D_{r}={\sum }_{t=0}^{r1}z_{t}D_{t}\). That is to say, the vector
z = (
z
_{0},…,
z
_{n− 1}) = (
z
_{0},…,
z
_{r− 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 0
_{n×n} is the
n ×
n all zero matrix.
$$ {D_{z}^{T}} = D_{(z_{0}, z_{n1}^{q}, \ldots, z_{1}^{q^{n1}})} = \begin{pmatrix}[ c] z_{0} & {\ldots} &z_{r1} & 1 & 0 & {\ldots} & 0 \\ 0 & {z_{0}^{q}} &{\ldots} & z_{r1}^{q} & 1 & {\ldots} & 0 \\ {\vdots} & {\ddots} & {\ddots} & {\ldots} & {\ddots} & {\ddots} & \vdots\\ 0& {\ldots} &0 &z_{0}^{q^{nr1} }& {\ldots} &z_{r1}^{q^{nr1} }&1 \\ &&&\!\!\!\!\ddots&\!{\ddots} &{\ddots} & \\ &&&&\!\!\!{\ddots} &{\ddots} \\ z_{1}^{q^{n1} } & {\ldots} &z_{r}^{q^{n1} }& 0 & \ldots&0 &z_{0}^{q^{n1} } \end{pmatrix}. $$
According to the definition of
D
_{z}, 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
D
_{z} are solution of (
y
_{0},…,
y
_{n− 1})
D = (0,…,0), the rank of
D
_{z} is at most
n −
r. This means that
D
_{z} 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
where
\(z^{\prime }=(z_{0}, z_{n1}^{q}, \ldots , z_{1}^{q^{n1}})=(z_{0}, 0, \ldots , 0, 1, z_{r1}^{q^{n(r1)}}, \ldots , z_{1}^{q^{n1}})\) and
for
i = 0,1,…,
n − 1. Recall that
\({D_{z}^{T}} \cdot D = 0_{n\times n}\). It immediately follows 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
D
_{z}, 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. □
$$ M_{\alpha}{D_{z}^{T}}=M_{\alpha}D_{z^{\prime}} = M_{\upbeta}=\left( \begin{array}{llll} {\upbeta}_{0}& {{\upbeta}_{0}^{q}}& \ldots& {\upbeta}_{0}^{q^{n1}}\\ {\upbeta}_{1}& {{\upbeta}_{1}^{q}}&\ldots& {\upbeta}_{1}^{q^{n1}}\\ \vdots& \vdots&\ddots& \vdots\\ {\upbeta}_{n1}& {\upbeta}_{n1}^{q}&\ldots& {\upbeta}_{n1}^{q^{n1}} \end{array}\right), $$
$$ {\upbeta}_{i} = \sum\limits_{j=0}^{n1} \alpha_{i}^{q^{j}}z_{nj}^{q^{j}} = \sum\limits_{j=0}^{n1} \alpha_{i}^{q^{nj}}z_{j}^{q^{nj}} = \sum\limits_{j=0}^{r1} \alpha_{i}^{q^{nj}}z_{j}^{q^{nj}}  \alpha_{i}^{q^{nr}} $$
$$ 0_{n\times n}= M_{\upbeta}\cdot D= \left( \begin{array}{llll} {\upbeta}_{0}& {{\upbeta}_{0}^{q}}& \ldots& {\upbeta}_{0}^{q^{n1}}\\ {\upbeta}_{1}& {{\upbeta}_{1}^{q}}&\ldots& {\upbeta}_{1}^{q^{n1}}\\ \vdots& \vdots&\ddots& \vdots\\ {\upbeta}_{n1}& {\upbeta}_{n1}^{q}&\ldots& {\upbeta}_{n1}^{q^{n1}} \end{array}\right)\left( \begin{array}{llll} l_{0}& l_{n1}^{q}& \ldots& l_{1}^{q^{n1}}\\ l_{1}& {l_{0}^{q}}&\ldots& l_{2}^{q^{n1}}\\ \vdots& \vdots&\ddots& \vdots\\ l_{n1}& l_{n2}^{q}&\ldots& l_{0}^{q^{n1}} \end{array}.\right) $$
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 = (
D
_{0},…,
D
_{n− 1})
^{T} and of finding a solution of
D
_{r} =
x
_{0}
D
_{0} + ⋯ +
x
_{r− 1}
D
_{r− 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}^{n1}l_{i}x^{q^{i}}\) over
\(\mathbb {F}_{q^{n}}\). Denote by
D
_{t} 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
$$ D_{0}=\cdots=D_{nr1}=0\text{ ~~and ~~} D_{nr}\neq 0. $$
By Theorem 4, in order to determine the rank of the Dickson matrix associated with
L(
x), we need to calculate the determinant of
D
_{0},
D
_{1} and
D
_{2}. The calculation for the case
D
_{2} is trivial. We only need to consider
D
_{0} and
D
_{1}. To this end, we need the following result.
Theorem 5
The determinant of the Dickson matrix
$$ D_{0}=\left[\begin{array}{ccccccccc} b&0&0&&&{\ldots} &0&1&a^{q^{r(n1)}}\\ a&b^{q^{r}}&0&&&{\ldots} &0&0&1\\ 1&a^{q^{r}}&b^{q^{2r}}& & & &&0&0\\ 0&1&a^{q^{2r}}& & & &&\vdots&\vdots\\ {\vdots} && & && \ddots&{\ddots} & &\\ & & & & & \ddots~~~&a^{q^{r(n3)}}&b^{q^{r(n2)}}&0\\ 0&\ldots& & && &1 &a^{q^{r(n2)}}&b^{q^{r(n1)}} \end{array}\right] $$
(32)
associated with the linearized polynomial
\(L(x)=x^{q^{2r}}+ax^{q^{r}}+bx\) can be calculated using the recursive relation
where
N(
a) denotes the field norm of
\(a\in \mathbb {F}_{q^{n}}\) from
\(\mathbb {F}_{q^{n}}\) to
\(\mathbb {F}_{q}\),
M
_{n} is a tridiagonal matrix of order
n and
M
_{n− 1} =
D
_{1}.
$$ D_{0}=(1)^{n+1}\cdot a^{q^{r(n1)}}M_{n1}+2b^{q^{r(n1)}} M_{n2}+N(a)+1, $$
(33)
Note that
D
_{2} is a lower triangular matrix and its determinant can be directly computed 
D
_{2} = 1. In order to prove Theorem 5 we need the following observation.
Lemma 3
The determinant of the tridiagonal matrix
is given by the recurrence relation
where 
M
_{0} = 1 and 
M
_{− 1} = 0.
(34)
$$ M_{n}=a^{q^{n1}}M_{n1}b^{q^{n1}}\cdot c^{q^{n2}}M_{n2}, $$
(35)
Proof
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
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(
y
_{i}) 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(
y
_{1}),
K(
y
_{s}) 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(
y
_{0}),…,
K(
y
_{n− 1}) is given by
\(\frac {1}{1q^{jn}}\) [
46]. □
$$x^{q^{n}}x=W(x)\circ K(x),$$
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 {nk}{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
L
_{i} such that
L
_{i} <
L. Hence one can obtain from Algorithm 1 two
tdimensional vectors
λ and
\(\lambda ^{\prime }\) over
\(\mathbb {F}_{q^{n}}\). Then the solution of (
15) is given as
from which the coefficients
g
_{0},…,
g
_{k} can be calculated recursively. The relation of
g
_{0} and
g
_{k} in (
13) leads to a quadratic equation
If
u
_{0} = 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.
$$ \lambda+\omega \lambda^{\prime} =(\lambda_{1}+\omega\lambda^{\prime}_{1}, \ldots, \lambda_{t}+\omega \lambda^{\prime}_{t}), $$
$$ \mathcal{P}(x)=u_{0}x^{{q_{0}^{v}}+1}+u_{1}x^{{q_{0}^{v}}} + u_{2}x + u_{3} = 0. $$
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},
r
_{i}) 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 interpolationbased 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.