Power error locating pairs

Abstract

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed–Solomon or algebraic geometry codes, the algorithm is a reformulation of the so-called power decoding algorithm. Asymptotically, it corrects errors up to Sudan’s radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan’s and Kötter’s approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.

1 Introduction

Algebraic codes such as Reed–Solomon codes or algebraic geometry codes are of central interest in coding theory because, compared to random codes, these structured codes benefit from polynomial time decoding algorithms that can correct a significant amount of errors. The decoding of Reed–Solomon and algebraic geometry codes is a fascinating topic at the intersection of algebra, algorithms, computer algebra and complexity theory.

1.1 Decoding of Reed–Solomon codes

Reed–Solomon codes benefit from an algebraic structure coming from univariate polynomial algebras. Thanks to this structure, one can easily prove that they are maximum distance separable (MDS). In addition, one can design an efficient unique decoding algorithm based on the resolution of a so-called key equation [1, 2, 10, 46] and correcting up to half the minimum distance. This decoding algorithm is sometimes referred to as Welch–Berlekamp algorithm in the literature.

In the late nineties, two successive breakthroughs due to Sudan [41] and Guruswami and Sudan [11] permitted to prove that Reed–Solomon codes and algebraic geometry codes can be decoded in polynomial time with an asymptotic radius reaching the so-called Johnson bound [17]. These algorithms have decoding radius exceeding half the minimum distance at the price that they may return a list of codewords instead of a single one. This drawback has actually a very limited impact since in practice, the list size is almost always less than or equal to 1 (see [21] for further details). Note that decoding Reed–Solomon codes beyond the Johnson bound remains a fully open problem: it is proved in [13] that the maximum likelihood decoding problem for Reed–Solomon codes is NP–hard but the possible existence of a theoretical limit between the Johnson bound and the covering radius under which decoding is possible in polynomial time remains an open question with only partial answers as in [36].

All the previously described decoders are worst case, i.e. correct any corrupted codeword at distance less than or equal to some fixed bound t. On the other side, some probabilistic algorithms may correct more errors at the cost of some rare failures. For instance, it is known for a long time that the classical Welch–Berlekamp algorithm applied to interleaved Reed–Solomon is a probabilistic decoder reaching the channel capacity [38] when the number of interleaved codewords tends to infinity. Inspired by this approach Bossert et. al. [39] proposed a probabilistic decoding algorithm for decoding genuine Reed–Solomon codes by interleaving the received word and some of its successive powers with respect to the component wise product. This algorithm has been called power decoding in the sequel. A striking feature of this power decoding is that it has the same decoding radius as Sudan algorithm. Moreover an improvement of the algorithm due to Rosenkilde [28] permits to reach Guruswami–Sudan radius, that is to say the Johnson bound.

However, compared to Sudan algorithm which is worst case and returns always the full list of codewords at bounded distance from the received word, the power decoding algorithm returns at most one element and might fail. The full analysis of its failure probability and the classification of failure cases is still an open problem but practical experimentations give evidences that this failure probability is very low.

1.2 Decoding of algebraic geometry codes

All the previously described decoding algorithms for Reed–Solomon codes have natural extensions to algebraic geometry codes at the cost of a slight deterioration of the decoding radius which is proportional to the curve’s genus. The problem of decoding algebraic geometry codes motivated hundreds of articles in the last three decades. The story starts in the late 80’s with an article of Justesen, Larsen, Jensen, Havemose and Høholdt [16] proposing a syndrome based decoding algorithm for codes from plane curves. The algorithm has then been extended to arbitrary curves by Skorobogatov and Vlăduţ [42]. The original description of these algorithms was strongly based on algebraic geometry. However, subsequently, Pellikaan [29, 30] and independently Kötter [18] proposed an abstract description of these algorithms expurgated from the formalism of algebraic geometry. This description was based on an object called error correcting pair . An error correcting pair for a code C is a pair of codes A, B satisfying some dimension and minimum distance constraints and such that the space $A * B$ spanned by the component wise products of words of A and B is contained in $C^\perp$. The existence of such a pair provides an efficient decoding algorithm essentially based on linear algebra. This approach provides a unified framework to describe algebraic decoding for Reed–Solomon codes, algebraic geometry codes and some cyclic codes [7, 8].

Concerning list decoding, Sudan and Guruswami–Sudan algorithms extend naturally to algebraic geometry codes. Sudan algorithm has been extended to algebraic geometry codes by Shokrollahi and Wasserman [43] and Guruswami–Sudan original article [11] treated the list decoding problem for both Reed–Solomon and algebraic geometry codes. Similarly, the power decoding algorithm generalises to such codes. As far as we know, no reference provides such a generalisation in full generality, however, such an algorithm is presented for the case of Hermitian curves in [26] and the generalisation to arbitrary curves is rather elementary and sketched in Appendix 1.

For further details on unique and list decoding algorithms for algebraic geometry codes, we refer the reader to the excellent survey papers [3, 14].

1.3 Our contribution

In summary, on the one hand, Reed–Solomon and algebraic geometry codes benefit from a Welch–Berlekamp like unique decoding algorithm, a Sudan-like list decoding algorithm and a power decoding. On the other hand, an abstract unified point of view for the unique decoding of these codes is given by error correcting pairs. In the present article we partially fill the gap by proposing a new algorithm in the spirit of error correcting pairs algorithms but permitting to correct errors beyond half the minimum distance. For Reed–Solomon and algebraic geometry codes, our algorithm is nothing but an abstraction of the power decoding algorithm, exactly as Pellikaan’s error correcting pairs algorithm is an abstraction of Welch–Berlekamp. However, this abstract version applies to any code equipped with a power error locating pair such as many cyclic codes [7, 8], for which our algorithm permits to correct errors beyond the Roos bound [33].

Interestingly, for algebraic geometry codes, the analysis of the number of errors our algorithm can correct turns out to provide a slightly better decoding radius compared to the analysis of the power decoding. According to experimental observations, the radius we obtain seems out to be optimal for both algorithms.

In addition to the intrinsic interest of having a unified point of view for decoding beyond half the minimum distance of codes equipped with a power error locating pair, a possible application of such an approach lies in cryptography and in particular in cryptanalysis. Indeed, it has been proved in [5], that an error correcting pair can be recovered from the single knowledge of a generator matrix of an algebraic geometry code. Using the present article’s results, this approach can be extended in order to build a Power Error Locating Pair from the very knowledge of a generator matrix of the code. This shows that any McEliece like scheme based on algebraic geometry codes and using a Sudan-like decoder for the decryption step cannot be secure since it is possible to recover in polynomial time all the necessary data to decode efficiently from the single knowledge of the public key (Fig. 1).

Fig. 1

Existing decoding algorithms for Reed–Solomon and algebraic geometry codes

1.4 Outline of the article

Notation and prerequisites are recalled in Sect. 2. In Sect. 3, we present some well–known decoding algorithms for algebraic codes with a particular focus on Reed–Solomon codes. Namely, a presentation of Welch–Berlekamp algorithm, power decoding and error correcting pairs algorithm is given. Our contribution, the power error locating pairs algorithm is presented in Sect. 4. Next, we explain how this abstract algorithm can be applied to Reed–Solomon codes in Sect. 5 and to algebraic geometry codes in Sect. 6. The latter section is concluded with a discussion on cryptanalytic applications of power error locating pairs. Finally, our algorithm is applied to cyclic codes in Sect. 7.

2 Notation and prerequisites

2.1 Basic notions of coding theory

In this article, we work over a finite field $\mathbb {F}_q$. Given a positive integer n, the Hamming weight on $\mathbb {F}_q^n$ is denoted as

$$\begin{aligned} \forall {\textit{\textbf{x}}}= (x_1, \ldots , x_n) \in \mathbb {F}_q^n,\quad {{\,\mathrm{w}\,}}({\textit{\textbf{x}}}) {\mathop {=}\limits ^{\text {def}}}\left| \{i \in \{1, \ldots , n\} ~|~ x_i \ne 0\} \right| \end{aligned}$$

and the Hamming distance${{\,\mathrm{d}\,}}(\ \! \cdot \ ,\ \! \cdot \ \!)$ as

$$\begin{aligned} \forall {\textit{\textbf{x}}}, {\textit{\textbf{y}}}\in \mathbb {F}_q^n,\quad {{\,\mathrm{d}\,}}({\textit{\textbf{x}}}, {\textit{\textbf{y}}}) {\mathop {=}\limits ^{\text {def}}}{{\,\mathrm{w}\,}}({\textit{\textbf{x}}}- {\textit{\textbf{y}}}). \end{aligned}$$

The support of a vector ${\textit{\textbf{a}}}\in \mathbb {F}_q^n$ is the subset ${{\,\mathrm{supp}\,}}({\textit{\textbf{a}}}) \subseteq \{1, \ldots , n\}$ of indexes i satisfying $a_i \ne 0$.

All along this article, term code denotes a linear code, i.e. a linear subspace of $\mathbb {F}_q^n$. Given a code $C \subseteq \mathbb {F}_q^n$, the minimum distance of C is denoted by ${{\,\mathrm{d}\,}}(C)$ or ${{\,\mathrm{d}\,}}$ when there is no ambiguity on the code. In addition, we recall some classical notions of coding theory and introduce notation for them.

Definition 2.1

Given $J=\{j_1,\dots , j_s\}\subset \{1,\dots , n\}$ and ${\textit{\textbf{x}}}=(x_1,\dots ,x_n)\in ~\mathbb {F}_q^n$, we denote by ${\textit{\textbf{x}}}_J$ the projection of ${\textit{\textbf{x}}}$ on the coordinates in J and by $Z({\textit{\textbf{x}}})$ the complement of the support of ${\textit{\textbf{x}}}$ in $\{1, \dots , n\}$. Namely,

$$\begin{aligned} {\textit{\textbf{x}}}_J{\mathop {=}\limits ^{\text {def}}}(x_{j_1},\dots , x_{j_s}) \qquad \mathrm{and} \qquad Z({\textit{\textbf{x}}}){\mathop {=}\limits ^{\text {def}}}\{i\in \{1,\dots , n\}\mid x_i=0\} \end{aligned}$$

Moreover, for $A\subseteq \mathbb {F}_q^n$, we define

(i):

$A_J{\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{a}}}_J\mid {\textit{\textbf{a}}}\in A\}\subseteq \mathbb {F}_q^{|J|}$ (puncturing);

(ii):

$A(J){\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{a}}}\in A\mid {\textit{\textbf{a}}}_J=\mathbf{0} \}\subseteq \mathbb {F}_q^n$ (shortening);

(iii):

$Z(A){\mathop {=}\limits ^{\text {def}}}\{i\in \{1,\dots , n\}\mid a_i=0\ \ \forall {\textit{\textbf{a}}}\in A\}$ (complementary of the support).

Remark 2.2

In (ii) we made an abuse of language by using the term shortening which classically refers to the operation

$$\begin{aligned} \{{\textit{\textbf{a}}}_{\{1,\dots , n\}\setminus J}\mid {\textit{\textbf{a}}}_J= \mathbf{0} \}. \end{aligned}$$

In comparison to the usual definition we do not remove the prescribed zero positions. We do so because we need to compute some star products (see Sect. 2.5) and for this sake involved vectors should have the same length.

Remark 2.3

Classically in the literature, puncturing a code at a subset J means deleting the entries whose index is in J. Here our notation does the opposite operation by keeping only the positions whose indexes are in J and removing all the other ones.

2.2 Decoding problems

The purpose of the present article is to introduce a new algorithm extending the error correcting pairs algorithm (see Sect. 3.3) and permitting to correct errors beyond half the minimum distance. This is possible at one cost: the algorithm might fail sometimes. First, let us state the main decoding problem one wants to solve.

Problem 1

(Bounded decoding) Let $C \subseteq \mathbb {F}_q^n$, ${\textit{\textbf{y}}}\in \mathbb {F}_q^n$ and $t \in \{0, \ldots , n\}$. Return (if exists) a word ${\textit{\textbf{c}}}\in C$ such that ${{\,\mathrm{d}\,}}({\textit{\textbf{c}}}, {\textit{\textbf{y}}}) \hbox {\,\char 054\,}t$.

Definition 2.4

For an algorithm solving Problem 1, the largest possible t such that the algorithm succeeds is referred to as the decoding radius of the algorithm.

When $t \hbox {\,\char 054\,}\left\lfloor {({{\,\mathrm{d}\,}}(C)-1)}/{2} \right\rfloor$, then the solution, if exists, is unique and the corresponding problem is sometimes referred to as the unambiguous decoding problem. For larger values of t, the set of codewords at distance less than or equal to t from ${\textit{\textbf{y}}}$ might have more than one element. To solve the bounded decoding problem in such a situation, various decoders exist. Some of them return the closest codeword (if unique), while other ones return the whole list of codewords at distance less than or equal to t. The algorithm of the present article, either returns a unique solution or fails.

To conclude this section, let us state an assumption which we suppose to be satisfied for any decoding problems considered in the sequel.

Assumption 1

In the following, given a code C and a positive integer t, when considering Problem 1, we always suppose that the received vector${\textit{\textbf{y}}}\in \mathbb {F}_q^n$ is of the form ${\textit{\textbf{y}}}= {\textit{\textbf{c}}}+ {\textit{\textbf{e}}}$ where ${\textit{\textbf{c}}}\in C$ and ${{\,\mathrm{w}\,}}({\textit{\textbf{e}}}) = t$. Equivalently, we always suppose that the bounded decoding problem has at least one solution.

2.3 Reed–Solomon codes

The space of polynomials with coefficients in $\mathbb {F}_q$ and degree less than k is denoted by $\mathbb {F}_q[X]_{<k}$. Given an integer $n\hbox {\,\char 062\,}k$ and a vector ${\textit{\textbf{x}}}\in \mathbb {F}_q^n$ whose entries are distinct, the Reed–Solomon code of length n and dimension k is the image of the space $\mathbb {F}_q[X]_{<k}$ by the map

$$\begin{aligned} {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}} : \left\{ \begin{array}{llll} {\mathbb {F}_q[X]}\longrightarrow {\mathbb {F}_q^n}\\ {f}\longmapsto {(f(x_1), \ldots , f(x_n)).} \end{array}\right. \end{aligned}$$

(1)

This code is denoted by ${\mathbf {RS}}_{q}[{\textit{\textbf{x}}}, k]$ or ${\mathbf {RS}}_{q}[k]$ when there is no ambiguity on the vector ${\textit{\textbf{x}}}$. That is:

$$\begin{aligned} {\mathbf {RS}}_{q}[k] {\mathop {=}\limits ^{\text {def}}}\left\{ (f(x_1), \ldots , f(x_n)) ~| f \in \mathbb {F}_q[X]_{<k}\right\} = {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}} \left( \mathbb {F}_q[X]_{<k} \right) . \end{aligned}$$

One can actually consider a larger class of codes called generalised Reed–Solomon codes and defined as:

$$\begin{aligned}{\mathbf {GRS}}_{q}[{\textit{\textbf{x}}}, {\textit{\textbf{y}}}, k]{\mathop {=}\limits ^{\text {def}}}\left\{ (y_1f(x_1), \ldots , y_nf(x_n)) ~|~ f \in \mathbb {F}_q[X]_{<k}\right\} ,\end{aligned}$$

where ${\textit{\textbf{y}}}\in {(\mathbb {F}_q^\times )}^n$. Such a code has length n, dimension k and minimum distance ${{\,\mathrm{d}\,}}= n - k + 1$. In this article, for the sake of simplicity, we focus on the case of Reed–Solomon codes (${\textit{\textbf{y}}}=(1,\ldots , 1)$) with $n = q$, i.e. the so-called full–support Reed–Solomon codes. This context is much more comfortable for duality since we can assert that

$$\begin{aligned} {\mathbf {RS}}_{q}[k]^\perp = {\mathbf {RS}}_{q}[n-k]. \end{aligned}$$

In the general case, the above statement remains true by replacing Reed–Solomon codes by generalised Reed–Solomon codes with a specific choice of ${\textit{\textbf{y}}}$. Indeed, it holds ${\mathbf {GRS}}_{q}[{\textit{\textbf{x}}}, {\textit{\textbf{y}}}, k]^{\perp }={\mathbf {GRS}}_{q}[{\textit{\textbf{x}}}, {\textit{\textbf{y}}}', n-k]$, where

$$\begin{aligned}{\textit{\textbf{y}}}'=-\frac{1}{y_i\prod \nolimits _{\begin{array}{c} j=1\\ j\ne i \end{array}}^n(x_j-x_i)}\cdot \end{aligned}$$

See for instance [34, Problem 5.7]. Actually, the results of the present article extend straightforwardly to generalised Reed–Solomon codes at the cost of slightly more technical proofs.

2.4 Algebraic geometry codes

In what follows, by curve we always mean a smooth projective geometrically connected curve defined over $\mathbb {F}_q$. Given such a curve $\mathcal {X}$, a divisor G on $\mathcal {X}$ and a sequence $\mathcal {P}= (P_1, \dots , P_n)$ of rational points of $\mathcal {X}$ avoiding the support of G, one can define the code

$$\begin{aligned} \mathcal {C}_L (\mathcal {X}, \mathcal {P}, G) {\mathop {=}\limits ^{\text {def}}}\left\{ (f(P_1), \dots , f(P_n)) ~|~ f\in L(G) \right\} , \end{aligned}$$

where L(G) denotes the Riemann–Roch space associated to G. When $\deg G < n$, such a code has dimension $k \hbox {\,\char 062\,}\deg G +1 - g$ where g denotes the genus of $\mathcal {X}$ and minimum distance ${{\,\mathrm{d}\,}}> n - \deg G$. We refer the reader to [40, 45] for further details on algebraic geometry, function fields and algebraic geometry codes.

2.5 Star product of words and codes

The space $\mathbb {F}_q^n$ is a product of n fields and hence has a natural structure of ring. We denote by $*$ the component wise product of vectors

$$\begin{aligned}(a_1, \dots , a_n) * (b_1, \dots , b_n) {\mathop {=}\limits ^{\text {def}}}(a_1 b_1, \dots , a_n b_n). \end{aligned}$$

Given a vector ${\textit{\textbf{a}}}\in \mathbb {F}_q^n$, the i–th power ${\textit{\textbf{a}}}^i$ of ${\textit{\textbf{a}}}$ is defined as ${\textit{\textbf{a}}}^i {\mathop {=}\limits ^{\text {def}}}(a_1^i, \dots , a_n^i)$.

Remark 2.5

This product should not be confused with the canonical inner product in $\mathbb {F}_q^n$ defined by $\langle {\textit{\textbf{a}}}, {\textit{\textbf{b}}}\rangle = \sum _{i=1}^n a_i b_i$. Note that these two operations are related by the following adjunction property

$$\begin{aligned} \langle {\textit{\textbf{a}}}*{\textit{\textbf{b}}},{\textit{\textbf{c}}}\rangle =\langle {\textit{\textbf{a}}}, {\textit{\textbf{b}}}*{\textit{\textbf{c}}}\rangle . \end{aligned}$$

(2)

In particular ${\textit{\textbf{a}}}*{\textit{\textbf{b}}}\in {\textit{\textbf{c}}}^{\perp }\iff {\textit{\textbf{a}}}*{\textit{\textbf{c}}}\in {\textit{\textbf{b}}}^{\perp }$.

Definition 2.6

Given two codes $A, B \subseteq \mathbb {F}_q^n$, the star product $A * B$ is the code spanned by all the products ${\textit{\textbf{a}}}* {\textit{\textbf{b}}}$ for ${\textit{\textbf{a}}}\in A$ and ${\textit{\textbf{b}}}\in B$. If $A = B$, the product is denoted by $A^2$. Inductively, one defines $A^i {\mathop {=}\limits ^{\text {def}}}A * A^{i-1}$ for all $i\hbox {\,\char 062\,}2$.

2.5.1 Star products of algebraic codes

Algebraic codes satisfy peculiar properties with respect to the star product.

Proposition 2.7

(Star product of Reed–Solomon codes) Let ${\textit{\textbf{x}}}\in \mathbb {F}_q^n$ be a vector with distinct entries and $k, k'$ be positive integers such that $k+k'-1\hbox {\,\char 054\,}n$. Then,

$$\begin{aligned} {\mathbf {RS}}_{q}[{\textit{\textbf{x}}}, k] * {\mathbf {RS}}_{q}[{\textit{\textbf{x}}}, k'] = {\mathbf {RS}}_{q}[{\textit{\textbf{x}}}, k+k'-1]. \end{aligned}$$

Remark 2.8

Actually Proposition 2.7 holds true even if $k+k'-1> n$ but in this situation the right–hand side becomes $\mathbb {F}_q^n$.

Proposition 2.9

(Star product of AG codes) Let $\mathcal {X}$ be a curve of genus g, $\mathcal {P}= (P_1, \dots , P_n)$ be a sequence of rational points of $\mathcal {X}$ and $G, G'$ be two divisors of $\mathcal {X}$ such that $\deg G \hbox {\,\char 062\,}2g$ and $\deg G' \hbox {\,\char 062\,}2g+1$. Then,

$$\begin{aligned} \mathcal {C}_L (\mathcal {X}, \mathcal {P}, G) * \mathcal {C}_L (\mathcal {X}, \mathcal {P}, G') = \mathcal {C}_L (\mathcal {X}, \mathcal {P}, G+G'). \end{aligned}$$

Proof

This is a consequence of [24, Theorem 6]. For instance, see [5, Corollary 9]. $\square$

2.5.2 A Kneser-like theorem

We conclude this section with a result which will be useful in the sequel and can be regarded as a star product counterpart of the famous Kneser Theorem in additive combinatorics (see [44, Theorem 5.5]). We first have to introduce a notion.

Definition 2.10

Let $H \subseteq \mathbb {F}_q^n$ be a code, the stabiliser of H is defined as

$$\begin{aligned} \text {Stab}(H) {\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{x}}}\in \mathbb {F}_q^n ~|~ {\textit{\textbf{x}}}*H \subseteq H\}. \end{aligned}$$

Theorem 2.11

Let $A, B \subseteq \mathbb {F}_q^n$ be two codes. Then,

$$\begin{aligned} \dim (A *B) \hbox {\,\char 062\,}\dim A + \dim B - \dim \text {Stab}(A *B). \end{aligned}$$

Proof

See [25, Theorem 18] or [4, Theorem 4.1]. $\square$

For any code C, the stabiliser of C has dimension at least 1 since it contains the span of the vector $(1, \ldots , 1)$. On the other hand, it has been proved in [19, Theorem 1.2] that a code C has a stabiliser of dimension $>1$ if and only if it is degenerated, i.e. if and only if either it is a direct sum of subcodes with disjoint supports or any generator matrix of C has a zero column. This leads to the following analog of Cauchy–Davenport Theorem [44, Theorem 5.4].

Corollary 2.12

Let $A, B \subseteq \mathbb {F}_q^n$ be two codes such that $A *B$ is non degenerated, then

$$\begin{aligned} \dim A *B \hbox {\,\char 062\,}\dim A + \dim B - 1. \end{aligned}$$

3 Former decoding algorithms for Reed–Solomon and algebraic geometry codes

It is known that several different decoding algorithms have been designed for Reed–Solomon and algebraic geometry codes. In particular, depending on the algorithm, we are able to solve either Problem 1 up to half the minimum distance, or to the Johnson bound.

In this section, we recall several decoding algorithms for Reed–Solomon codes. For all of them, a natural extension to algebraic geometry codes is known. Recall that, whenever we discuss a decoding problem we suppose Assumption 1 to be satisfied, i.e. we suppose that the decoding problem has at least one solution. Hence, we can write

$$\begin{aligned} {\textit{\textbf{y}}}={\textit{\textbf{c}}}+{\textit{\textbf{e}}}, \end{aligned}$$

(3)

for some ${\textit{\textbf{c}}}\in C$ and ${\textit{\textbf{e}}}\in \mathbb {F}_q^n$ with ${{\,\mathrm{w}\,}}({\textit{\textbf{e}}})=t$. Note that since $C={\mathbf {RS}}_{q}[k]$, the codeword ${\textit{\textbf{c}}}$ can be written as the evaluation of a polynomial f(x) with $\deg (f)<k$. The vector ${\textit{\textbf{e}}}$ is called the error vector. Moreover, we define

$$\begin{aligned}I_{{\textit{\textbf{e}}}}{\mathop {=}\limits ^{\text {def}}}{{\,\mathrm{supp}\,}}({\textit{\textbf{e}}})= \{i\in \{1, \dots , n\}\mid e_i\ne 0\}.\end{aligned}$$

Hence, we have $t={{\,\mathrm{w}\,}}({\textit{\textbf{e}}})=|I_{{\textit{\textbf{e}}}}|$.

3.1 Welch–Berlekamp algorithm

Welch–Berlekamp algorithm boils down to a linear system based on n key equations. In this case the decoding radius is given by a sufficient condition, i.e. if there is a solution, the algorithm will find it.

Definition 3.1

Given ${\textit{\textbf{y}}}, {\textit{\textbf{e}}}$ and $I_{{\textit{\textbf{e}}}}$ as above we define

• the error locator polynomial as $\Lambda (X){\mathop {=}\limits ^{\text {def}}}\prod _{i\in I_{{\textit{\textbf{e}}}}} (X-x_i)$;

• $N(X){\mathop {=}\limits ^{\text {def}}}\Lambda (X)f(X)$.

Hence, for any $i\in \{1,\dots , n\}$, the polynomials $\Lambda$ and N verify

$$\begin{aligned} \Lambda (x_i)y_i=N(x_i). \end{aligned}$$

(4)

The aim of the algorithm is then to solve the following

Key Problem 1

Find a pair of polynomials $(\lambda , \nu )$ such that $\deg (\lambda )\hbox {\,\char 054\,}t$, $\deg (\nu )\hbox {\,\char 054\,}~t+k-1$ and

Remark 3.2

Actually, the degrees of $\Lambda$ and N are related by

$$\begin{aligned} \deg (N)\hbox {\,\char 054\,}\deg (\Lambda )+k-1.\end{aligned}$$

With this constraint the problem can be solved using Berlekamp–Massey algorithm. Though in this paper we chose to consider the simplified constraints of Key Problem 1 in order to have linear constrains, which makes the analysis of the decoding radius easier. By the following lemma it will be clear that making this choice has no consequence on the decoding radius of Welch–Berlekamp algorithm.

The system ($S_{\text {WB}}$) is linear and has n equations in $2t+k+1$ unknowns. We know that the pair $(\Lambda , \Lambda f)$ is in its solutions space. The following result proves that, for certain values of t, actually it is not necessary to find exactly that solution to solve the decoding problem.

Lemma 3.3

Let $t\hbox {\,\char 054\,}\frac{{{\,\mathrm{d}\,}}-1}{2}$. If $(\lambda , \nu )$ is a nonzero solution of ($S_{\text {WB}}$), then $\lambda \ne 0$ and $f=\frac{\nu }{\lambda }$.

For the proof we refer for instance to [15, Theorem 4.2.2]. We can finally write the algorithm (see Algorithm 1). Its correctness is entailed by Lemma 3.3 whenever $t\hbox {\,\char 054\,}\frac{{{\,\mathrm{d}\,}}-1}{2}$, that is, the decoding radius of Welch–Berlekamp algorithm is $t=\lfloor \frac{{{\,\mathrm{d}\,}}-1}{2}\rfloor \cdot$

3.2 Power decoding algorithm

Introduced by Sidorenko, Schmidt and Bossert, [38], power decoding is inspired from a decoding algorithm for interleaved Reed–Solomon codes. It consists in considering several “powers” (with respect to the star product) of the received vector ${\textit{\textbf{y}}}$ in order to have more relations to work on. Given the vector ${\textit{\textbf{y}}}={\textit{\textbf{c}}}+{\textit{\textbf{e}}}$ we want to correct, we consider the i–th powers ${\textit{\textbf{y}}}^i$ of ${\textit{\textbf{y}}}$ for $i=1,\dots , \ell$ (see Sect. 2.5 for the definition of ${\textit{\textbf{y}}}^i$). In this section, we only present the case $\ell =2$ for simplicity. We have

$$\begin{aligned} {\textit{\textbf{y}}}=\&{\textit{\textbf{c}}}+{\textit{\textbf{e}}}\end{aligned}$$

(5)

$$\begin{aligned} {\textit{\textbf{y}}}^2=\&{\textit{\textbf{c}}}^2+2{\textit{\textbf{c}}}*{\textit{\textbf{e}}}+ {\textit{\textbf{e}}}^2. \end{aligned}$$

(6)

We then rename ${\textit{\textbf{e}}}$ by ${\textit{\textbf{e}}}^{(1)}$ and $2{\textit{\textbf{c}}}*{\textit{\textbf{e}}}+ {\textit{\textbf{e}}}^2$ by ${\textit{\textbf{e}}}^{(2)}$ and get

$$\begin{aligned} {\textit{\textbf{y}}}&= {\textit{\textbf{c}}}+{\textit{\textbf{e}}}^{(1)}\end{aligned}$$

(7)

$$\begin{aligned} {\textit{\textbf{y}}}^2&= {\textit{\textbf{c}}}^2+{\textit{\textbf{e}}}^{(2)}. \end{aligned}$$

(8)

One can see ${\textit{\textbf{y}}}^2$ as a perturbation of a word ${\textit{\textbf{c}}}^2\in C^2= {\mathbf {RS}}_{q}[2k-1]$ by the error vector ${\textit{\textbf{e}}}^{(2)}$. Hence ${\textit{\textbf{y}}}^2$ is an instance of another decoding problem. In addition, we have the following elementary result which is the key of power decoding.

Proposition 3.4

It holds ${{\,\mathrm{supp}\,}}({\textit{\textbf{e}}}^{(2)})\subseteq {{\,\mathrm{supp}\,}}({\textit{\textbf{e}}}^{(1)})$.

It asserts that on ${\textit{\textbf{y}}}$ and ${\textit{\textbf{y}}}^2$, the errors are localised at the same positions. More precisely, error positions on ${\textit{\textbf{y}}}^2$ are error positions on ${\textit{\textbf{y}}}$. Hence, we are in the error model of interleaved codes: Eqs. (7) and (8) can be regarded as a decoding problem for the interleaving of two codewords with errors at most at t positions. Therefore, errors can be decoded simultaneously using the same error locator polynomial. To do that, we consider the error locating polynomial $\Lambda (X)=\prod _{i\in I_{{\textit{\textbf{e}}}}}(X-x_i)$ as for Welch–Berlekamp algorithm and the polynomials

$$\begin{aligned} N_1{\mathop {=}\limits ^{\text {def}}}\Lambda f,\quad N_2{\mathop {=}\limits ^{\text {def}}}\Lambda f^2. \end{aligned}$$

Thanks to Proposition 3.4, it is possible to write the key equations

$$\begin{aligned} \left\{ \begin{aligned} \Lambda (x_i)y_i= N_1(x_i)\quad&\forall i\in \{1,\dots , n\}\\ \Lambda (x_i)y_i^2= N_2(x_i)\quad&\forall i\in \{1,\dots , n\} \end{aligned} \right. \end{aligned}$$

(9)

Consequently, the Power decoding algorithm consists in solving the following problem.

Key Problem 2

Given ${\textit{\textbf{y}}}\in \mathbb {F}_q^n$ and $t\in \mathbb {N}$, find $(\lambda , \nu _1, \nu _2)$ which fulfill

with $\deg (\lambda )\hbox {\,\char 054\,}t$ and $\deg (\nu _j)\hbox {\,\char 054\,}t+j(k-1)$ for $j\in \{1, 2\}$.

Remark 3.5

Key Problem 2 is slightly different from the problem faced in the original paper describing Power Decoding [39]. We used a key equation formulation of the problem instead of the syndrome one. The two formulations are equivalent if the right bounds on polynomials’ degrees are taken (see [27]). In particular, one should look for $(\lambda , \nu _1, \nu _2)$ such that $\deg (\nu _j)\hbox {\,\char 054\,}\deg (\lambda )+j(k-1)$ for all $j\in \{1, \dots , \ell \}$. However, similarly as for Welch–Berlekmap algorithm, we consider two weaker constraints which allow to reduce the problem to a linear system to solve. The price is that our Key Problem could get more failure cases than problem in [39]. However, we observed experimentally that these cases are really rare.

The vector $(\Lambda , \Lambda f, \Lambda f^2)$ is a solution of the linear system ($S_{\text {Po}}$). Though, at the moment there is no guaranteed method to recover it among all the solutions. We only know that, if g is a polynomial such that $\deg (g)<k$ and ${{\,\mathrm{d}\,}}({{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(g), {\textit{\textbf{y}}})\hbox {\,\char 054\,}t$, then there exists an error locator polynomial $\Gamma$ of the error with respect to g, such that the vector

$$\begin{aligned}\nonumber (\Gamma , \Gamma g, \Gamma g^2) \end{aligned}$$

is solution of ($S_{\text {Po}}$). Among all solutions like that, we want to pick the one that gives the closest codeword, that is the one such that $\deg (\Gamma )$ is minimal (see pt.1 in Algorithm 2).

Remark 3.6

The 2n equations we obtain in Key Problem 2, consist in the key equations for ${\textit{\textbf{y}}}$ and the key equations for ${\textit{\textbf{y}}}^2$, that is two simultaneous decoding problems. Indeed, the important aspect is that these two decoding problems share the error locator polynomial $\Lambda$. Hence, by adding n relations, we only add $\deg (N_2)+1$ unknowns instead of $\deg (N_2)+t+2$.

Remark 3.7

To compute the decoding radius of the Power Decoding algorithm we look for a condition on the size of the system ($S_{\text {Po}}$). Note that the algorithm gives one solution or none, hence there cannot be a sufficient condition for the correctness of the algorithm as soon as $t>\frac{{{\,\mathrm{d}\,}}-1}{2}$. For this reason, we look for a necessary condition for the system ($S_{\text {Po}}$) to have a solution space of dimension 1.

The general case with an arbitrary $\ell$. For an arbitrary $\ell$, Key Problem 2 is replaced the following system:

with $\deg \lambda \hbox {\,\char 054\,}t$ and $\deg \nu _j \hbox {\,\char 054\,}t + j(k-1)$ for all $j \in \{1, \ldots , \ell \}$.

3.2.1 Decoding radius

Under Assumption 1, we know that $(\Lambda , \Lambda f, \Lambda f^2)$ is a solution for ($S_{\text {Po}}$) and hence, the algorithm returns ${\textit{\textbf{c}}}$ if and only if the solution space of ($S_{\text {Po}}$) has dimension one.

Let us define the polynomial

$$\begin{aligned}\nonumber \pi (X){\mathop {=}\limits ^{\text {def}}}\prod _{i=1}^n (X-x_i) \end{aligned}$$

and consider the bounds in Key Problem 2 on the degrees of $\nu _1$ and $\nu _2$. If $t+2(k-1)\hbox {\,\char 062\,}n$, then we would have $(0, 0, \pi )\in Sol$. For a larger $\ell$ this condition becomes

$$\begin{aligned} t<n-\ell (k-1). \end{aligned}$$

(10)

However, bound (10) is actually much larger than the decoding radius. We look then for a stricter bound on t. Another necessary condition to have a solution space of dimension one for ($S_{\text {Po}}$), is:

$$\begin{aligned}\#unknowns\hbox {\,\char 054\,}\#equations +1,\end{aligned}$$

which gives $t\hbox {\,\char 054\,}\frac{2n-3k+1}{3}\cdot$

Remark 3.8

Actually, starting from ${\textit{\textbf{y}}}= {\textit{\textbf{c}}}+ {\textit{\textbf{e}}}$, Algorithm 2 could return another word ${\textit{\textbf{c}}}' \ne {\textit{\textbf{c}}}$ which would be closer to ${\textit{\textbf{y}}}$. In such a situation, the solution space of ($S_{\text {Po}}$) will not have dimension 1 since it will contain a triple $(\Lambda , \Lambda f, \Lambda f^2)$ associated to ${\textit{\textbf{c}}}$ and a vector $(\Lambda ', \Lambda ' f', \Lambda ' f'^2)$ associated to ${\textit{\textbf{c}}}'$ which can be proved to be linearly independent. Therefore, the algorithm may return the closest codeword even in situations when the dimension of the solutions space of ($S_{\text {Po}}$) has dimension larger than 1. The analysis consists in giving a necessary condition for the algorithm to return ${\textit{\textbf{c}}}$.

Finally, the same process can be used for a general $\ell$ and we obtain the following decoding radius

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n\ell -k\ell (\ell +1)+\ell (\ell -1)}{2(\ell +1)}\cdot \end{aligned}$$

(11)

3.3 The error correcting pairs algorithm

The Error Correcting Pairs (ECP) algorithm has been designed by Pellikaan [30] and independently by Kötter [18]. Its formalism gives an abstract description of a decoding algorithm originally arranged for algebraic geometry codes [42] and whose description required notions of algebraic geometry. In their works, Pellikaan and Kötter, simplified the instruments needed in the original decoding algorithm and made the algorithm applicable to any linear code benefiting from a certain elementary structure called error correcting pair and defined in Definition 3.9 below. Given a code C and a received vector ${\textit{\textbf{y}}}= {\textit{\textbf{c}}}+ {\textit{\textbf{e}}}$ where ${\textit{\textbf{c}}}\in C$ and ${{\,\mathrm{w}\,}}({\textit{\textbf{e}}}) \hbox {\,\char 054\,}t$ for some positive integer t, the ECP algorithm consists in two steps:

• (1) find $J\subseteq \{1, \dots , n\}$ such that $J\supseteq I_{{\textit{\textbf{e}}}}$, where $I_{{\textit{\textbf{e}}}}$ denotes the support of ${\textit{\textbf{e}}}$;

• (2) recover the nonzero entries of ${\textit{\textbf{e}}}$.

As said before, these steps can be solved if the code has a t-error correcting pair where $t={{\,\mathrm{w}\,}}({\textit{\textbf{e}}})$ is small enough.

Definition 3.9

Given a linear code $C\subseteq \mathbb {F}_q^n$, a pair (A, B) of linear codes, with $A, B\subseteq \mathbb {F}_q^n$ is called t-error correcting pair for C if

• (ECP1) $A*B\subseteq C^{\perp }$;

• (ECP2) $\dim (A)>t$;

• (ECP3) ${{\,\mathrm{d}\,}}(B^{\perp })>t$;

• (ECP4) ${{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n$.

Remark 3.10

One can observe that, thanks to Remark 2.5,

$$\begin{aligned}\nonumber A*B\subseteq C^{\perp }\iff A*C\subseteq B^{\perp }. \end{aligned}$$

Since this notion does not look very intuitive, an example of error correcting pair for Reed–Solomon codes is given further in Sect. 3.4 and an interpretation of the various hypotheses above is given in light of this example in Sect. 3.5. For now, we want to explain more precisely how the ECP algorithm works.

3.3.1 First step of the error correcting pair algorithm

In Step (1) of the ECP algorithm, we wish to find a set which contains $I_{{\textit{\textbf{e}}}}$. A good candidate for J could then be $Z(A({I_{{\textit{\textbf{e}}}}}))$, indeed the following result (see [30]), entails that ${I_{{\textit{\textbf{e}}}}}\subseteq Z(A({I_{{\textit{\textbf{e}}}}}))\varsubsetneq \{1,\dots , n\}$ (see Definition 2.1).

Proposition 3.11

If $\dim (A)> t$, then $A({I_{{\textit{\textbf{e}}}}})\ne 0$.

Though, since we do not know ${I_{{\textit{\textbf{e}}}}}$, we do not have any information about $A({I_{{\textit{\textbf{e}}}}})$. That is why a new vector space is introduced:

$$\begin{aligned} M_1{\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}},{\textit{\textbf{b}}}\rangle =0 \ \ \forall {\textit{\textbf{b}}}\in B\}. \end{aligned}$$

(12)

The key of the algorithm is in the following result.

Theorem 3.12

Let ${\textit{\textbf{y}}}= {\textit{\textbf{c}}}+ {\textit{\textbf{e}}}$, ${I_{{\textit{\textbf{e}}}}}={{\,\mathrm{supp}\,}}({\textit{\textbf{e}}})$ and $M_1$ as above. If $A*B\subseteq C^{\perp }$, then

• (1) $A({I_{{\textit{\textbf{e}}}}})\subseteq M_1\subseteq A$;

• (2) if ${{\,\mathrm{d}\,}}(B^{\perp })>t$, then $A({I_{{\textit{\textbf{e}}}}})=M_1$;

Proof

See [30]. $\square$

Therefore, if the pair (A, B) fulfills (ECP1-3) in Definition 3.9, then $Z(M_1)$ is non trivial and contains ${I_{{\textit{\textbf{e}}}}}$. Therefore, Step (1) of the algorithm consists in computing $J = Z(M_1)$.

3.3.2 Second step of the error correcting pair algorithm

Step (2) is nothing but the resolution of a linear system depending on J and the syndrome of ${\textit{\textbf{y}}}$. First, some notation is needed.

Notation

Let H be a matrix having n columns and $J\subseteq \{1, \dots , n\}$. We denote by $H_J$ the submatrix of H whose columns are those with index $j\in J$.

Suppose we have computed $J\supseteq {I_{{\textit{\textbf{e}}}}}$ in Step (1) of the algorithm. Consider a full rank–parity check matrix H for C. The vector ${\textit{\textbf{e}}}_J$ satisfies $H_J\cdot {\textit{\textbf{e}}}_J^T=H\cdot {\textit{\textbf{y}}}^T.$ and we want then to recover ${\textit{\textbf{e}}}_J$ by solving the linear system

$$\begin{aligned} H_J\cdot {\textit{\textbf{u}}}^T=H\cdot {\textit{\textbf{y}}}^T. \end{aligned}$$

(13)

Though, a priori, the solution may not be unique. Condition (ECP4) in Definition 3.9 yields the following result.

Lemma 3.13

If $\ {{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n$, $\dim (A)>t$ and $J=Z(M_1)$, then $|J|<{{\,\mathrm{d}\,}}(C)$.

Proof

By Proposition 3.11, there exists ${\textit{\textbf{a}}}\in A({I_{{\textit{\textbf{e}}}}})\setminus \{0\}$. Now, since ${{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n$, we get

$$\begin{aligned}|J|=|Z(M_1)|\hbox {\,\char 054\,}|Z({\textit{\textbf{a}}})|=n-{{\,\mathrm{w}\,}}({\textit{\textbf{a}}})\hbox {\,\char 054\,}n-{{\,\mathrm{d}\,}}(A)< {{\,\mathrm{d}\,}}(C).\end{aligned}$$

$\square$

Theorem 3.14

Given ${\textit{\textbf{y}}}\in \mathbb {F}_q^n$ and $J\subseteq \{1,\dots , n\}$ with $t=|J|<{{\,\mathrm{d}\,}}(C)$, then there exists at most one solution for (13).

This is a well-known result of coding theory and it is easy to prove. This theorem, together with Lemma 3.13, entail that if J contains the support of the error, ${\textit{\textbf{e}}}_J$ is the unique solution to system (13). Then, the second step of the algorithm consists in finding ${\textit{\textbf{e}}}_J$ by solving system (13) and recovering ${\textit{\textbf{e}}}$ from ${\textit{\textbf{e}}}_J$ imposing $e_i=0$ for all $i\notin J$. The entire algorithm is described in Algorithm 3.

The correctness of the algorithm is proved in [30]. It is straightforward to see that the algorithm returns a unique solution and that a sufficient condition for the algorithm to correct t errors, is the existence of an error correcting pair with parameter t. This consideration, leads to the following result.

Corollary 3.15

[30, Corollary 2.15] If a linear code C has a t-error correcting pair, then

$$\begin{aligned}t\hbox {\,\char 054\,}\Bigl \lfloor \frac{{{\,\mathrm{d}\,}}(C)-1}{2}\Bigr \rfloor .\end{aligned}$$

3.4 Error correcting pairs for Reed–Solomon codes

For an arbitrary code, there is no reason that an error correcting pair exists. Indeed, the existence of an ECP for a given code relies on the existence of a pair (A, B) of codes, both having a sufficiently large dimension and satisfying $A * B \subseteq C^{\perp }$, which is actually a very restrictive condition. Among the codes for which an ECP exists, there are Reed–Solomon codes. Indeed, given $C={\mathbf {RS}}_{q}[k]$, consider the pair (A, B):

$$\begin{aligned} A={\mathbf {RS}}_{q}[t+1],\quad B^{\perp }={\mathbf {RS}}_{q}[t+k]. \end{aligned}$$

(14)

Recall that thanks to Proposition 2.7, we have $A * C = {\mathbf {RS}}_{q}[t+k].$

Lemma 3.16

Given B as above, it holds

$$\begin{aligned} {{\,\mathrm{d}\,}}(B^{\perp })>t \iff t\hbox {\,\char 054\,}\frac{{{\,\mathrm{d}\,}}(C)-1}{2}\cdot \end{aligned}$$

(15)

Proposition 3.17

The pair (A, B) of (14) is a t-error correcting pair for C for any

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{{{\,\mathrm{d}\,}}(C)-1}{2}\cdot \end{aligned}$$

(16)

Proof

We have to prove that (16) is a necessary and sufficient condition for (ECP1–4) in Definition 3.9 to hold. First of all, by Lemma 3.16 we have (ECP3). Moreover $\dim (A)=t+1>t$ by definition of A and this gives (ECP2). By Proposition 2.7, as seen above, the codes A, B, C verify $A*C=B^{\perp }$, then by Remark 2.5 we obtain $A*B\subseteq C^{\perp }$. Finally, it is easy to see that ${{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n\iff t<{{\,\mathrm{d}\,}}(C)$. Hence if $t\hbox {\,\char 054\,}\Bigl \lfloor \frac{{{\,\mathrm{d}\,}}(C)-1}{2}\Bigr \rfloor$, (ECP1–4) hold and conversely. $\square$

Remark 3.18

In Sect. 4, we are going to work with structures which are slightly different from error correcting pairs, that is, we will still require (ECP1, 2) and (ECP4) to hold together with other conditions. Note that, given A and B as in (14) Conditions (ECP1, 2) and (ECP4) hold if and only if $t<{{\,\mathrm{d}\,}}(C)$.

3.5 ECP and Welch–Berlekamp key equations

The example of Reed–Solomon also permits to understand the rationale behind EPC’s in light of Welch–Berlekamp algorithm. Indeed, we now show that the choice of $M_1$ we made in the ECP algorithm, if one looks at the key equations of Welch–Berlekamp algorithm, appears to be really natural. Let us consider $C={\mathbf {RS}}_{q}[k]$ and the pair (A, B) we defined in Sect. 3.4. We can write (4) for any $i\in \{1,\dots , n\}$ using the star product in this way

$$\begin{aligned}(\Lambda (x_1),\dots , \Lambda (x_n))*{\textit{\textbf{y}}}=(N(x_1),\dots , N(x_n)).\end{aligned}$$

From that, we can deduce

• $(N(x_1),\dots , N(x_n))\in {\mathbf {RS}}_{q}[t+k]=B^{\perp }$;

• $(\Lambda (x_1), \dots , \Lambda (x_n))\in {\mathbf {RS}}_{q}[t+1]({I_{{\textit{\textbf{e}}}}})=A({I_{{\textit{\textbf{e}}}}})$;

• Moreover $(\Lambda (x_1), \dots , \Lambda (x_n))\in \underbrace{\{{\textit{\textbf{a}}}\in A\mid \langle a*{\textit{\textbf{y}}}, b\rangle =0\ \ \forall {\textit{\textbf{b}}}\in B\}}_{M_1}$.

In other words, the vector $(\Lambda (x_1), \dots , \Lambda (x_n))$ belongs to the space $A({I_{{\textit{\textbf{e}}}}})$ we are looking for in the ECP algorithm. Moreover it fulfills a property which characterises a space $M_1\supseteq A({I_{{\textit{\textbf{e}}}}})$, that is exactly the space we define in the ECP algorithm and that turns to be equal to $A({I_{{\textit{\textbf{e}}}}})$ under certain conditions.

4 Power error locating pairs algorithm

We now present the Power Error Locating Pairs (PELP) algorithm. As for the error correcting pairs algorithm, we first give a generic description of the algorithm and later some examples of its application. In order to generalise the ECP algorithm to correct more errors, we introduce a new parameter $\ell$ we call power and define a slightly different structure from error correcting pairs. As in the previous paragraphs, we first describe that structure and the algorithm for $\ell =2$ and then explain how to generalise it.

4.1 The case $\ell =2$

In Pellikaan’s paper, a structure called error locating pairs is already defined. It is a pair of codes (A, B) which satisfy (ECP1, 2) and (ECP4). In particular it is shown that, without changing anything in the algorithm, with such a structure it is possible to correct errors if the support of the error vector ${I_{{\textit{\textbf{e}}}}}$ is an independentt-set of error position with respect to the code B (see [30]).

In the present article, in order to correct beyond half the designed distance, we do not consider particular error supports, but we rather choose to work with a more particular structure than error locating pairs and change the first step of the algorithm.

Definition 4.1

(2–Power error locating pairs) Given a linear code $C\subseteq \mathbb {F}_q^n$, a pair of linear codes (A, B) with $A, B\subseteq \mathbb {F}_q^n$ is a 2–powert–error locating pair for C if

• (2–PELP1) $A*B\subseteq C^\perp$;

• (2–PELP2) $\dim (A)>t$;

• (2–PELP3) ${{\,\mathrm{d}\,}}(A^{\perp })>t$;

• (2–PELP4) ${{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n$;

• (2–PELP5) $\dim (B)+\dim (B^{\perp }*C)^{\perp }\hbox {\,\char 062\,}t$.

Compared to the definition of error correcting pairs, we removed (ECP 3) which is too restrictive to correct errors beyond half the minimum distance. Instead, in the same spirit as the power decoding, we look for a necessary condition for the algorithm to succeed. In this context, under Condition (2–PELP3), Condition (2–PELP5) provides this necessary condition together with the key tool for the analysis of the decoding radius of our algorithm.

Remark 4.2

In the transition between ECP algorithm and 2–PELP algorithm, it is very important to get rid of the property ${{\,\mathrm{d}\,}}(B^{\perp })>t$. Indeed, since we want $A*C\subseteq B^{\perp }$, if we had ${{\,\mathrm{d}\,}}(B^{\perp })>t$, then, assuming that $A * C$ is non degenerate (see Sect. 2.5.2) we would get

$$\begin{aligned}t+\dim (C)\hbox {\,\char 054\,}\dim (A)+\dim (C)-1\hbox {\,\char 054\,}\dim (A*C)\hbox {\,\char 054\,}\dim (B^{\perp })\hbox {\,\char 054\,}n-t, \end{aligned}$$

where the second inequality is due to Corollary 2.12. This entails that $t\hbox {\,\char 054\,}\frac{n-\dim (C)}{2}$, which does not represent an improvement of the decoding radius in every situation (see Sect. 5).

Let us consider a code C, a word ${\textit{\textbf{y}}}\in \mathbb {F}_q^n$ such that ${\textit{\textbf{y}}}={\textit{\textbf{c}}}+{\textit{\textbf{e}}}$ with ${\textit{\textbf{c}}}\in C$ and $t={{\,\mathrm{w}\,}}({\textit{\textbf{e}}})$ and let (A, B) be a 2–power t–error locating pair for C.

Definition 4.3

As in the ECP algorithm, let $M_1=\{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}, {\textit{\textbf{b}}}\rangle =0\ \ \forall {\textit{\textbf{b}}}\in B\}$. We then define the spaces

$$\begin{aligned} M_2&{\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}^2, {\textit{\textbf{v}}}\rangle =0\ \ \forall {\textit{\textbf{v}}}\in (B^{\perp }*C)^{\perp }\} \end{aligned}$$

and

$$\begin{aligned}M{\mathop {=}\limits ^{\text {def}}}M_1\cap \ M_2.\end{aligned}$$

Notation

As in the description of the power decoding algorithm, since we work with ${\textit{\textbf{y}}}$ and ${\textit{\textbf{y}}}^2$, we indicate with ${\textit{\textbf{e}}}^{(1)}$ and ${\textit{\textbf{e}}}^{(2)}$ the vectors such that respectively ${\textit{\textbf{y}}}={\textit{\textbf{c}}}+{\textit{\textbf{e}}}^{(1)}$ and ${\textit{\textbf{y}}}^2={\textit{\textbf{c}}}^2+{\textit{\textbf{e}}}^{(2)}$.

As shown in Algorithm 4, the only change from the error correcting pair algorithm consists in computing a new set M, which is smaller than the set $M_1$ considered in the basic algorithm. The reason why we do so, is that since we are now working with a 2–power error locating pair, we are no longer asking for ${{\,\mathrm{d}\,}}(B^{\perp })>t$. Hence, without this property the equality

$$\begin{aligned}\nonumber A({I_{{\textit{\textbf{e}}}}})=M_1 \end{aligned}$$

is not entailed and only the inclusion $A({I_{{\textit{\textbf{e}}}}})\subseteq M_1$ still holds. That is, $M_1$ could be too big with respect to $A({I_{{\textit{\textbf{e}}}}})$ and the algorithm would fail. Indeed, if there was ${\textit{\textbf{a}}}\in M_1\setminus A({I_{{\textit{\textbf{e}}}}})$, that means ${\textit{\textbf{a}}}_{I_{{\textit{\textbf{e}}}}}\ne 0$, we would have $J=Z(M_1)\nsupseteq {I_{{\textit{\textbf{e}}}}}$.

Proposition 4.4

The set M fulfills $A({I_{{\textit{\textbf{e}}}}})\subseteq M\subseteq M_1\subseteq A$.

Proof

We have to prove that $A({I_{{\textit{\textbf{e}}}}})\subseteq M$, that is $A({I_{{\textit{\textbf{e}}}}})\subseteq M_1, M_2$. First, we already know that $A({I_{{\textit{\textbf{e}}}}})\subseteq M_1$ by Theorem 3.12(1). About $M_2$, we adapt the proof of Theorem 3.12(1). First, note that we have

$$\begin{aligned} A*B\subseteq C^{\perp }\iff A*C\subseteq B^{\perp }\implies A*C^2\subseteq B^{\perp }*C. \end{aligned}$$

(17)

Given ${\textit{\textbf{a}}}\in A({I_{{\textit{\textbf{e}}}}})$, for any ${\textit{\textbf{v}}}\in (B^{\perp }*C)^{\perp }$ we obtain

$$\begin{aligned} \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}^2, {\textit{\textbf{v}}}\rangle= & {} \langle {\textit{\textbf{a}}}*{\textit{\textbf{c}}}^2, {\textit{\textbf{v}}}\rangle +\langle {\textit{\textbf{a}}}*{\textit{\textbf{e}}}^{(2)}, {\textit{\textbf{v}}}\rangle \end{aligned}$$

(18)

$$\begin{aligned}= & {} 0. \end{aligned}$$

(19)

In (18) we used the bilinearity, while (19) holds because of (17) and the fact that the supports of ${\textit{\textbf{e}}}^{(2)}$ and ${\textit{\textbf{a}}}$ are complementary (see Proposition 3.4). $\square$

Thanks to this proposition, one can see that if we work with a 2–PELP, there are more chances to have $A({I_{{\textit{\textbf{e}}}}})=M$ than $A({I_{{\textit{\textbf{e}}}}})=M_1$, that is why in 2–PELP algorithm, we look for M instead of $M_1$. Furthermore, we get the following result.

Theorem 4.5

Under Assumption 1, Algorithm 4 returns ${\textit{\textbf{c}}}$ if and only if $A({I_{{\textit{\textbf{e}}}}}) = M$.

Proof

Suppose the algorithm returned ${\textit{\textbf{c}}}$. This entails that we computed a set $J = Z(M)$ which contains $I_{{\textit{\textbf{e}}}}$ and hence $M = M(I_{{\textit{\textbf{e}}}})$. Therefore, from Proposition 4.4, we get $M = A(I_{{{\textit{\textbf{e}}}}})$. Conversely, if $M = A(I_{{\textit{\textbf{e}}}})$, then $J = Z(M) \supseteq I_{{\textit{\textbf{e}}}}$. Next, using Conditions (2–PELP2) and (2–PELP4), one can prove a result very similar to Lemma 3.13 (replacing $M_1$ by M) asserting that the linear system (13) has a unique solution ${\textit{\textbf{e}}}$. Thus, the algorithm returns ${\textit{\textbf{c}}}$. $\square$

We now show how the properties (2–PELP3) and (2–PELP5) are involved in 2–PELP algorithm. To do so, we want to focus on necessary conditions for the algorithm to return ${\textit{\textbf{c}}}$. By Theorem 4.5, this is equivalent to look for a necessary condition to have $A({I_{{\textit{\textbf{e}}}}})=M$, which is the point of the following statement and explains the rationale behind Condition (2–PELP5).

Theorem 4.6

If $A({I_{{\textit{\textbf{e}}}}})=M$, then $\dim (B)+\dim (B^{\perp }*C)^{\perp }\hbox {\,\char 062\,}t$.

Before proving Theorem 4.6, we need to present some other results first.

Lemma 4.7

The following statements are equivalent:

• (i) $M=A({I_{{\textit{\textbf{e}}}}})$;

• (ii) $M({I_{{\textit{\textbf{e}}}}})=M$;

• (iii) $M_{I_{{\textit{\textbf{e}}}}}=\{0\}$.

Proof

First, notice that $A({I_{{\textit{\textbf{e}}}}})=M({I_{{\textit{\textbf{e}}}}})$ by Proposition 4.4. Hence, (i) and (ii) are equivalent. We now prove (ii)$\iff$(iii). It is easy to see that, if $M({I_{{\textit{\textbf{e}}}}})=M$, the projection on ${I_{{\textit{\textbf{e}}}}}$ of every element of M, is the zero vector and conversely. $\square$

Thanks to this lemma, if we find a necessary condition for $M_{I_{{\textit{\textbf{e}}}}}=\{0\}$, then we find a necessary condition for $M=A({I_{{\textit{\textbf{e}}}}})$ and conversely. For this reason, we now study the object $M_{I_{{\textit{\textbf{e}}}}}$.

Theorem 4.8

It holds $M_{I_{{\textit{\textbf{e}}}}}=A_{I_{{\textit{\textbf{e}}}}}\cap ({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }\cap {\left( {\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp }\right) }_{I_{{\textit{\textbf{e}}}}}^{\perp }$.

Remark 4.9

Note that the notation $({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }$ and ${\left( {\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp }\right) }_{I_{{\textit{\textbf{e}}}}}^{\perp }$ could be considered as ambiguous since the operation of puncturing and that consisting in taking the dual code do not commute. Actually, in this situation, there is no ambiguity since the supports of ${\textit{\textbf{e}}}^{(1)}*B$ and ${\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^\perp$ are contained in $I_{{\textit{\textbf{e}}}}$.

Proof of Theorem 4.8

Let us characterise the elements of A that are in $M_1$ and $M_2$. Let ${\textit{\textbf{a}}}\in A$,

$$\begin{aligned} {\textit{\textbf{a}}}\in M_1\iff & {} \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}, {\textit{\textbf{b}}}\rangle =0\quad \forall {\textit{\textbf{b}}}\in B\\\iff & {} \langle {\textit{\textbf{a}}}, {\textit{\textbf{e}}}^{(1)}*{\textit{\textbf{b}}}\rangle =0\quad \forall {\textit{\textbf{b}}}\in B\\\iff & {} {\textit{\textbf{a}}}_{I_{{\textit{\textbf{e}}}}}\in ({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }. \end{aligned}$$

For the second equivalence we used the property $A*B\subseteq C^{\perp }$ which is equivalent to $A*C\subseteq B^{\perp }$ (see Remark 3.10) while in the third, we used ${{\,\mathrm{supp}\,}}({\textit{\textbf{e}}}^{(1)})={I_{{\textit{\textbf{e}}}}}$. In the same way, it is possible to prove that given ${\textit{\textbf{a}}}\in A$,

$$\begin{aligned}\nonumber {\textit{\textbf{a}}}\in M_2\iff {\textit{\textbf{a}}}_{I_{{\textit{\textbf{e}}}}}\in ({\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp })_{I_{{\textit{\textbf{e}}}}}^{\perp }. \end{aligned}$$

The result comes now easily. $\square$

It is actually possible to simplify the form of $M_{I_{{\textit{\textbf{e}}}}}$.

Lemma 4.10

Let $A\subseteq \mathbb {F}_q^n$ be a linear code and $t\in \mathbb {N}$. The following facts are equivalent:

• ${{\,\mathrm{d}\,}}(A^\perp )>t$;

• $A_{J}=\mathbb {F}_q^t$ for any ${J}\subseteq \{1,\dots , n\}$ with $|{J}|=t$.

Corollary 4.11

If (A, B) is a 2–power t–error locating pair for the code C, then

$$\begin{aligned}M_{I_{{\textit{\textbf{e}}}}}=({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }\cap ({\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp })_{I_{{\textit{\textbf{e}}}}}^{\perp }.\end{aligned}$$

It is now possible to prove Theorem 4.6.

Proof Theorem 4.6

Looking for a necessary condition to have $M_{I_{{\textit{\textbf{e}}}}}=\{0\}$, we get

$$\begin{aligned} M_{I_{{\textit{\textbf{e}}}}}=\{0\}\iff & {} ({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }\cap ({\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp })_{I_{{\textit{\textbf{e}}}}}^{\perp }=\{0\} \end{aligned}$$

(20)

$$\begin{aligned}&\implies&\dim (({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }) + \dim (({\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp })_{I_{{\textit{\textbf{e}}}}}^{\perp })\hbox {\,\char 054\,}t \end{aligned}$$

(21)

$$\begin{aligned}&\implies&\dim ({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}} + \dim ({\textit{\textbf{e}}}^{(2)}*(B^{\perp }*C)^{\perp })_{I_{{\textit{\textbf{e}}}}} \hbox {\,\char 062\,}t \end{aligned}$$

(22)

$$\begin{aligned}&\implies&\dim (B)+\dim ((B^{\perp }*C)^{\perp })\hbox {\,\char 062\,}t. \end{aligned}$$

(23)

$\square$

4.2 The general case: $\ell \hbox {\,\char 062\,}2$

It is possible to generalise the algorithm for $\ell \hbox {\,\char 062\,}2$. First we generalise the structure we use.

Definition 4.12

($\ell$–Power error locating pairs) Given a linear code $C\subseteq \mathbb {F}_q^n$, a pair of linear codes (A, B) with $A, B\subseteq \mathbb {F}_q^n$ is an $\ell$–powert–error locating pair for C if

($\ell$–PELP1):

$A*B\subseteq C^\perp$;

($\ell$–PELP2):

$\dim (A)>t$;

($\ell$–PELP3):

${{\,\mathrm{d}\,}}(A^{\perp })>t$;

($\ell$–PELP4):

${{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C)>n$;

($\ell$–PELP5):

$\dim (B)+\sum _{i=2}^{\ell }\dim (B^{\perp }*C^{i-1})^{\perp }\hbox {\,\char 062\,}t$.

A generalisation of the notion of M is needed too, that is, for a generic power $\ell$, M will be the intersection of $\ell$ spaces.

Definition 4.13

As in the ECP algorithm, let $M_1=\{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}, {\textit{\textbf{b}}}\rangle =0\ \ \forall {\textit{\textbf{b}}}\in B\}$. For any $i=2,\dots ,\ell$, we define the space

$$\begin{aligned} M_i&{\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}^i, {\textit{\textbf{v}}}\rangle =0\ \ \forall {\textit{\textbf{v}}}\in (B^{\perp }*C^{i-1})^{\perp }\}. \end{aligned}$$

Finally we define

$$\begin{aligned} M{\mathop {=}\limits ^{\text {def}}}\bigcap _{i=1}^{\ell }M_i. \end{aligned}$$

(24)

Then, the algorithm for a general $\ell$ is the same as Algorithm 4 changing only the definition of M by that given in (24). Let us look for a necessary condition for this generalised algorithm to return ${\textit{\textbf{c}}}$. It can be proven that Theorem 4.5 can be adapted to the generalised notion (24) of M. The following theorem gives the necessary condition we look for.

Theorem 4.14

If $A({I_{{\textit{\textbf{e}}}}})=M$, then $\dim (B)+\sum _{i=2}^{\ell }\dim (B^{\perp }*C^{i-1})^{\perp }\hbox {\,\char 062\,}t.$

Again, in order to prove this Theorem, we study the condition $M_{I_{{\textit{\textbf{e}}}}}=\{0\}$, since it is equivalent to $A({I_{{\textit{\textbf{e}}}}})=M$ by Lemma 4.7.

Theorem 4.15

It holds

$$\begin{aligned}\nonumber M_{I_{{\textit{\textbf{e}}}}}=({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}}^{\perp }\cap \bigcap _{i=2}^{\ell } {\left( {\textit{\textbf{e}}}^{(i)}*(B^{\perp }*C^{i-1})^{\perp }\right) }_{I_{{\textit{\textbf{e}}}}}^{\perp }, \end{aligned}$$

where ${\textit{\textbf{e}}}^{(i)}=\sum _{h=1}^i \left( {\begin{array}{c}i\\ h\end{array}}\right) {\textit{\textbf{c}}}^{i-h}*{\textit{\textbf{e}}}^{h}$ is such that ${\textit{\textbf{y}}}^i={\textit{\textbf{c}}}^i+{\textit{\textbf{e}}}^{(i)}$ for all $i=1,\dots , \ell$.

To prove this result, it is possible to adapt the proof of Theorem 4.8 and observe that it still holds $A_{I_{{\textit{\textbf{e}}}}}=\mathbb {F}_q^t$. We will use the following remark.

Remark 4.16

Given a vector space V with $\dim (V)=t$ and $A_1,\dots , A_n\subseteq V$, we have

$$\begin{aligned}\dim \Big (\bigcap _{i=1}^n A_i^{\perp }\Big )\hbox {\,\char 062\,}t-\sum \dim (A_i);\end{aligned}$$

in addition, it is easy to see that $\dim (({\textit{\textbf{e}}}^{(1)}*B)_{I_{{\textit{\textbf{e}}}}})\hbox {\,\char 054\,}\dim (B)$ and

$$\begin{aligned}\nonumber \forall i\in \{2,\dots , \ell \}, \quad \dim (({\textit{\textbf{e}}}^{(i)}*(B^{\perp }*C^{i-1})^{\perp })_{I_{{\textit{\textbf{e}}}}})\hbox {\,\char 054\,}\dim ((B^{\perp }*C^{i-1})^{\perp }). \end{aligned}$$

Now, it is possible to prove Theorem 4.14.

Proof Theorem 4.14

It holds

(25)

Now, thanks to Remark 4.16, one can easily see that (25) implies

$$\begin{aligned}\dim (B)+\sum _{i=2}^{\ell }\dim (B^{\perp }*C^{i-1})^{\perp }\hbox {\,\char 062\,}t.\end{aligned}$$

$\square$

4.3 Complexity

To conclude this section, let us discuss the complexity of the algorithm. We denote by $\omega$ the exponent of the complexity of matrix multiplications. First, recall that the computation of the star product of two codes of length n costs $O(n^4)$ arithmetic operations in $\mathbb {F}_q$ using a deterministic algorithm and $O(n^\omega )$ using a probabilistic algorithm (see for instance [6, § VI.A and D]).

The evaluation of the complexity of the power error locating pairs algorithm should be divided in two parts:

• the pre-computation phase, that should be done once for good and is independent from the error and the corrupted codeword;

• the online phase, which depends on the corrupted codeword.

4.3.1 The precomputation phase

This phase consists essentially in computing generator matrices for the codes ${(B^\perp *C^{i-1})}^\perp$ for $i \in \{1, \dots , \ell \}$. Each new calculation consists in the computation of a $*$–product and a dual. This yields an overall cost of $O(\ell n^\omega )$ operations in $\mathbb {F}_q$ using a probabilistic algorithm and $O(\ell n^4)$ operations using a deterministic one.

4.3.2 The online phase

• The computation of each space $M_i$ boils down to the resolution of a linear system with $\dim A$ variables and $\dim {(B^\perp * C^{i-1})}^\perp$ equations. Hence a cost of $O(n^\omega )$ operations in $\mathbb {F}_q$.

• The computation of M consists in the calculation of $\ell - 1$ intersections of spaces. Since the cost of the calculation of an intersection is $O(n^\omega )$ operations, the cost of the computation of M from the knowledge of the $M_i$’s is in $O(\ell n^\omega )$

In summary, the overall complexity of the online phase is in $O(\ell n^\omega )$ operations in $\mathbb {F}_q$.

Remark 4.17

Note that the previous complexity analysis is purely generic and does not take into account that codes with an error locating pair such as Reed–Solomon code may be described by structured matrices permitting faster linear algebra.

5 $\ell$–PELP algorithm for Reed–Solomon codes

We now give some applications of the $\ell$–PELP algorithm, starting with Reed–Solomon codes. For these codes, the algorithm is much more intuitive. Indeed, as for the error correcting pairs algorithm, it is possible to deduce the PELP algorithm from a former decoding algorithm for Reed–Solomon codes: the power decoding.

Let us consider the code $C={\mathbf {RS}}_{q}[k]$ and the pair (A, B), where $A={\mathbf {RS}}_{q}[t+1]$ and $B^{\perp }={\mathbf {RS}}_{q}[t+k]$. We look for the values of t for which (A, B) is an $\ell$–power t–error locating pair for C. One can see that, since we no longer ask for ${{\,\mathrm{d}\,}}(B^{\perp })>t$, by Lemma 3.16, t can be larger than $\frac{{{\,\mathrm{d}\,}}(C)-1}{2}$. About the conditions to fulfill, we already have seen that properties ($\ell$–PELP1, 2, 4) hold for any $t<{{\,\mathrm{d}\,}}(C)$ (see Sect. 3.4). Let us find the values of t which verify

($\ell$–PELP3):

${{\,\mathrm{d}\,}}(A^{\perp })>t$;

($\ell$–PELP5):

$\dim (B)+ \sum _{i=2}^\ell \dim (B^{\perp }*C^{i-1})^{\perp }\hbox {\,\char 062\,}t$.

Property ($\ell$–PELP3) holds for any t since Reed–Solomon codes are MDS and A has dimension $t+1$. Let us now focus on property ($\ell$–PELP5). By Proposition 2.7, we know that $B^{\perp }*C^{i-1}={\mathbf {RS}}_{q}[t+i(k-1)+1]$ and these codes are not equal to $\mathbb {F}_q^n$ as soon as

$$\begin{aligned} t< n- \ell (k-1) - 1. \end{aligned}$$

(26)

If (26) is satisfied, then the bound in property ($\ell$–PELP5) becomes

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n\ell -k\ell (\ell +1)+\ell (\ell -1)}{2(\ell +1)}, \end{aligned}$$

(27)

which is the decoding radius for the power decoding algorithm for a general $\ell$ (see (11)).

Remark 5.1

Note that (27) came in power decoding as a necessary condition to have a unique solution for a linear system. Here instead, it comes up as a necessary condition for an intersection of some vector spaces to be $\{0\}$.

5.1 The space M and the key equations of power decoding

In Sect. 3.5, we have seen that it is possible to relate the definition of $M_1$ with the key equations of Welch–Berlekamp algorithm. One can do the same with the definition of M in the power error locating pairs algorithm and the key equations of the $\ell$–power decoding algorithm. Here, we only consider the case $\ell =2$, since it is easy to generalise the idea for a larger $\ell$. It is possible to write (9) in this way

$$\begin{aligned} \left\{ \begin{array}{lcl} {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\Lambda )*{\textit{\textbf{y}}}&{}=&{} {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(N_1)\\ {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\Lambda )*{\textit{\textbf{y}}}^2&{}=&{} {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}} (N_2), \end{array} \right. \end{aligned}$$

where ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}$ is the evaluation map introduced in (1). Hence, we can deduce

• ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(N_1)\in {\mathbf {RS}}_{q}[t+k]=B^{\perp }$;

• ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(N_2)\in {\mathbf {RS}}_{q}[t+2k-1]=B^{\perp }*C$;

• ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\Lambda )\in {\mathbf {RS}}_{q}[t+1]({I_{{\textit{\textbf{e}}}}})=A({I_{{\textit{\textbf{e}}}}})$;

• ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\Lambda )\in M$, where M is the set defined in the 2–power error locating pairs algorithm. Indeed we recall that $M=M_1\cap M_2$, where

  $$\begin{aligned} M_1= & {} \{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}, {\textit{\textbf{b}}}\rangle =0\ \forall {\textit{\textbf{b}}}\in B\},\\ M_2= & {} \{{\textit{\textbf{a}}}\in A\mid \langle {\textit{\textbf{a}}}*{\textit{\textbf{y}}}^2, {\textit{\textbf{v}}}\rangle =0\ \forall {\textit{\textbf{v}}}\in (B^{\perp }*C)^{\perp }\}. \end{aligned}$$

In other words, in the power decoding algorithm one works with polynomials, while in the power error locating pairs algorithm one works with their evaluations.

5.2 Equivalence of the two algorithms for Reed–Solomon codes

Thanks to the link presented in the previous subsection, it is possible to find an isomorphism between the solution space of power decoding and the space M. For the sake of simplicity, we explicit this isomorphism in the case $\ell = 2$. The general case can easily be deduced from the following study.

Theorem 5.2

Let ${\textit{\textbf{y}}}=\mathbb {F}_q^n$ and t a positive integer and suppose we run both the power decoding algorithm and the power error locating pairs algorithm with the same t and $\ell =2$. Denote by Sol the solution space of the linear system ($S_{\text {Po}}$) in the power decoding. Then the linear map

$$\begin{aligned} \varphi {\mathop {=}\limits ^{\text {def}}}\left\{ \begin{array}{lll}{Sol}\longrightarrow {M}\\ {(\lambda , \nu _1, \nu _2)}\longmapsto {{{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\lambda ).}\end{array}\right. \end{aligned}$$

(28)

is bijective.

Proof

For the sake of simplicity, we provide the proof in the case $\ell = 2$. The proof in the general case is easy to deduce at the cost of heavier notation. First, let us show that $\varphi$ is well defined. Let $(\lambda , \nu _1, \nu _2)$ belong to Sol. Then, it holds

$$\begin{aligned} {\left\{ \begin{array}{ll} \lambda (x_i)y_i=\nu _1(x_i) &{} i=1,\dots , n\\ \lambda (x_i)y_i^2=\nu _2(x_i) &{} i=1,\dots , n. \end{array}\right. } \end{aligned}$$

(29)

As we have seen in Sect. 5, these two conditions are equivalent to the statement

$$\begin{aligned}\nonumber {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\lambda )\in M_1\cap M_2=M. \end{aligned}$$

Conversely, given ${\textit{\textbf{a}}}\in M$, there exists $\lambda \in \mathbb {F}_q[X]$ with $\deg (\lambda )<t+1$ such that ${{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\lambda )={\textit{\textbf{a}}}$. Moreover, since ${\textit{\textbf{a}}}\in M$, we have

$$\begin{aligned} {\textit{\textbf{a}}}*{\textit{\textbf{y}}}\in B^{\perp } ={\mathbf {RS}}_{q}[t+k],\ \ \ {\textit{\textbf{a}}}*{\textit{\textbf{y}}}^2\in B^{\perp }*C ={\mathbf {RS}}_{q}[t+2k-1]. \end{aligned}$$

Thus, there exist $\nu _1, \nu _2\in \mathbb {F}_q[X]$ with $\deg (\nu _1)<t+k$, $\deg (\nu _2)<t+2k-1$ and

$$\begin{aligned} {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\nu _1) ={\textit{\textbf{a}}}*{\textit{\textbf{y}}},\ \ \ {{\,\mathrm{ev}\,}}_{{\textit{\textbf{x}}}}(\nu _2) ={\textit{\textbf{a}}}*{\textit{\textbf{y}}}^2. \end{aligned}$$

(30)

We can then define another map

$$\begin{aligned} \psi {\mathop {=}\limits ^{\text {def}}} \left\{ \begin{array}{lll} M &{} \longrightarrow &{} Sol \\ {\textit{\textbf{a}}} &{} \longmapsto &{} (\lambda , \nu _1, \nu _2) \end{array} \right. , \end{aligned}$$

(31)

where $\lambda , \nu _1$ and $\nu _2$ are the polynomials associated to ${\textit{\textbf{a}}}$ as before. It is easy to prove that, under the condition¹

$$\begin{aligned} t<n-2(k-1) \end{aligned}$$

(32)

it holds $\varphi \circ \psi =Id_{M}$ and $\psi \circ \varphi =Id_{Sol}$. $\square$

In summary, for Reed–Solomon codes, power decoding and power error locating pairs algorithms are equivalent. In particular they succeed or fail for the same instances.

6 PELP algorithm for algebraic geometry codes

As said previously, the power error locating pairs algorithm can be run on any code with a PELP. We have seen that Reed–Solomon codes belong to this class of codes. In the sequel, we show that algebraic geometry codes also belong to it. Similarly to the case of Reed–Solomon codes, this algorithm can be compared with the power decoding algorithm. Power decoding extends naturally from Reed–Solomon codes to algebraic geometry codes. However, its use for decoding AG codes in the literature concerns mainly one–point codes from the Hermitian curve (see [26, 31]). For this reason, we give a brief presentation together with an analysis of its decoding radius in Appendix 1.

In the sequel, we show that the analysis of the power decoding provides a decoding radius which is slightly below that of the power error locating pairs algorithm. Moreover, we observed experimentally that the decoding radius given by the analysis of the PELP algorithm is optimal for both the PELP and the power decoding algorithms. Probably, a more detailed analysis of the power decoding would provide a sharper estimate of the decoding radius, but the point is that the analysis of the PELP algorithm provides an optimal radius in a very elementary manner.

6.1 Context

Let $\mathcal {X}$ be a smooth projective geometrically connected curve of genus g over $\mathbb {F}_q$. Let G be a divisor on $\mathcal {X}$ and $\mathcal {P}= (P_1, \dots , P_n)$ be an ordered n–tuple of pairwise distinct rational points of $\mathcal {X}$ avoiding the support of G. We denote by k and ${{\,\mathrm{d}\,}}$ respectively the dimension and the minimum distance of the code $\mathcal {C}_L (\mathcal {X}, \mathcal {P}, G)$. Moreover, we denote by D the divisor $P_1+\dots +P_n$ and by W the divisor $(\omega )$ where $\omega \in \Omega (\mathcal {X})$ is a rational differential form such that $v_{P_i} (\omega )=~-1$ and $res_{P_i}(\omega )=1$ for any $i \in \{1,\dots , n\}$. We now introduce an extra divisor F on $\mathcal {X}$ and the pair (A, B) with

$$\begin{aligned} A=C_L(\mathcal {X}, \mathcal {P}, F)\ \ \ B=C_L(\mathcal {X},\mathcal {P}, D+W-F-G). \end{aligned}$$

(33)

This pair of codes is our candidate to be a power error locating pair for C. We analyse the case $\ell =2$ for simplicity (it is easy to generalise what we are going to see).

6.2 Decoding Radius

In order to find the decoding radius of the 2–power error correcting pairs algorithm for algebraic geometry codes, we follow the same path as for Reed–Solomon codes. That is, we look for the pairs (A, B) that satisfy properties (2–PELP1–5) in Definition 4.1. To do so, we write some additional conditions on the degree of the divisor F and G and on the number of errors t. First, note that Property (2–PELP1) holds by construction of A and B. In order to have properties (2–PELP2, 3) and to know the structure of the code $(B^{\perp }*C)^{\perp }$, we ask for the two following conditions

Additional Condition 1

$\deg (F)\hbox {\,\char 062\,}t+2g$.

Additional Condition 2

$\deg (G)\hbox {\,\char 062\,}2g$.

In particular, it is easy to verify that under these two additional conditions, we have by Proposition 2.9

$$\begin{aligned}(B^{\perp }*C)^{\perp }=C_L(\mathcal {X}, \mathcal {P},D+W-F-2G).\end{aligned}$$

Let us fix then the value of $\deg (F)$ to be $2g+t$. We now consider the bound given by Condition (2–PELP5) for $\ell =2$

$$\begin{aligned} \dim (B)+\dim ((B^{\perp }*C)^{\perp })\hbox {\,\char 062\,}t. \end{aligned}$$

(34)

We need to know the exact dimension of these spaces, hence we impose some more conditions on the degree of the divisor²G. We ask for

Additional Condition 3

$t<n-2\deg (G)-2g$.

Finally, we get the following result.

Proposition 6.1

Let $\deg (F)=t+2g<n-\deg (G)$, $\deg (G)< 2g$ and $t\hbox {\,\char 054\,}n-2\deg (G)-2g$. Then $C=C_L(\mathcal {X}, \mathcal {P}, G)$ admits a 2–PELP as in (33), if

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n-3\deg (G)-2}{3}-\frac{2}{3}g. \end{aligned}$$

(35)

In this case, bound (35) gives the decoding radius of the 2–PELP algorithm.

Proof

Condition (2–PELP1) is obviously satisfied by the codes A, B defined in (33). Moreover, since $\deg (F) = t+2g$, we get $\dim (A) > t$, i.e. Property (2–PELP2). Property (2–PELP4) is a consequence of the condition $\deg (F) < n - \deg (G)$, which indeed entails

$$\begin{aligned}{{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(C) \hbox {\,\char 062\,}2n - \deg (F) - \deg (G) > n.\end{aligned}$$

Thanks to Additional Condition 1, we have (2–PELP3). Finally one notes that bound in (2–PELP5) becomes the bound on t in (35) thanks to the additional conditions and the property $\deg (F)<n-\deg (G)$. $\square$

Remark 6.2

As for Reed–Solomon codes, we want to have $(B^{\perp }*C)\subsetneq \mathbb {F}_q^n$. Indeed in this case if M and $M_1$ are as in Definition 4.3, we get $M\subsetneq M_1$ and the decoding radius in (35) is usually achieved according to our tests. That is why it is important also to ask

$$\begin{aligned}t<n-2\deg (G)-g-1.\end{aligned}$$

Note that this bound is achieved whenever we are in the hypothesis of Proposition 6.1 and $g>1$.

The decoding radius can be computed even for arbitrary values of $\ell$. Indeed, if we impose $t\hbox {\,\char 054\,}n-\ell \deg (G)-2g$, we get

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-g+\frac{g-\ell }{\ell +1}\cdot \end{aligned}$$

(36)

6.3 Comparison with decoding radii of other algorithms for algebraic geometry codes

We can now compare this decoding radius with the decoding radii of Sudan algorithm and the power decoding algorithm for algebraic geometry codes. We have (see [43, Theorem 2.1] and Appendix 1):

$$\begin{aligned}&{} \mathbf{{Sudan}}&t&\hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-g -\frac{1}{\ell +1}\\&{} \mathbf{{Power decoding}}&t&\hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-g -\frac{\ell }{\ell +1}\cdot \end{aligned}$$

First, note that if

$$\begin{aligned} g>\ell -1, \end{aligned}$$

then the decoding radius of the $\ell$–PELP algorithm (36) is even larger than Sudan’s algorithm decoding radius. Furthermore, one can see that for algebraic geometry codes, the power decoding algorithm and the power error locating pairs algorithm no longer have the same decoding radius, but the second one is larger. Actually the implementation of the algorithms put in evidence that power decoding algorithm is actually able to correct more than what expressed by its decoding radius, and up to the recoding radius of the $\ell$–PELP algorithm. It is possible to explain this by considering that in the power decoding algorithm something changes once we pass to algebraic geometry codes from Reed–Solomon codes. Indeed, in both cases, the decoding radius comes as a necessary condition for a vector space to have dimension one. But for Reed–Solomon codes, this is equivalent to have a necessary condition for the algorithm to succeed, while for algebraic geometry codes this is no longer true.

By the tests we made, it seems that the bound (36) is optimal. Though we should precise that we run the algorithms with $\deg (F)=t+2g$. Actually experimentally we have seen that it is possible to run power decoding algorithm with $\deg (F)=t+g$ and obtain an empirical decoding radius

$$\begin{aligned}t \hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-\frac{\ell }{\ell +1}\cdot \end{aligned}$$

which indeed corresponds to the empirical result obtained in [26].

6.4 Cryptanalytic application

In the last fourty years, many attempts for instantiating McEliece encryption scheme [20] using algebraic codes have been proposed in the literature. The use of generalised Reed–Solomon codes is known to be unsecure since Sidelnikov and Shestakov’s attack [37] permitting to recover the whole structure of such a code from the very knowledge of a generator matrix. Note that actually, a procedure to recover the structure of a generalised Reed–Solomon code from the data of a generator matrix was already known by Roth and Seroussi [35]. Sidelnikov–Shestakov attack has been extended to algebraic geometry codes from curves of genus 1 and 2 [9, 23]. For general algebraic geometry codes, an attack has been given [5] that permits to recover an error correcting pair or an error correcting array from the knowledge of a generating matrix. This attack does not permits to recover the curve, the divisor and the evaluation points but is enough to break the system as soon as the decoder corrects at most half the designed distance.

In a nutshell, this attack of [5] consists in computing some filtered sequences of codes from the knowledge of a generator matrix of $\mathcal {C}_L (\mathcal {X}, \mathcal {P}, G)$. Namely, the codes computed are of the form $\mathcal {C}_L (\mathcal {X}, \mathcal {P}, iP)$ and $\mathcal {C}_L (\mathcal {X}, \mathcal {P}, G-iP)$ for a given rational point P and for any integer i. For i large enough, the pair $(\mathcal {C}_L (\mathcal {X}, \mathcal {P}, iP), \mathcal {C}_L (\mathcal {X}, \mathcal {P}, G-iP))$ yields an error correcting pair.

Suppose now that McEliece scheme is instantiated with an algebraic geometry code and whose decryption step requires to correct beyond half the designed distance by using Sudan’s or power decoding algorithm. Stricto sensu, such a scheme is out of reach by the attack [5]. However, the very same approach permits to design a power error locating pair. Then, Algorithm 4 can be run without requiring any further knowledge on the curve and the divisor. This yields an interesting application of this abstract formulation of decoding beyond half the minimum distance. Note that no such cryptographic proposal exists in the literature but [47] which is unfortunately out of reach of power error locating pairs since it requires the use of a Guruswami–Sudan like decoder yielding a decoding radius close to Johnson bound.

7 PELP algorithm for cyclic codes

In this section, we give an application of the PELP algorithm for some cyclic codes. In 1994, Duursma and Kötter showed in [7] that an ECP algorithm can correct up to half the BCH bound and, in particular cases, also half the Roos bound (see Theorem 7.9 for a definition and [33] for details).

First, we recall the main notions and fix some notation (for more details see [7]). Let us consider a field $\mathbb {F}_q$ and an integer n with $\gcd (n, q)=1$. Given a vector ${\textit{\textbf{c}}}=(c_0,\dots ,c_{n-1})\in \mathbb {F}_q^n$, we denote by c(X) the image of ${\textit{\textbf{c}}}$ by the following linear map:

$$\begin{aligned} \left\{ \begin{array}{lll} \mathbb {F}_q^n &{} \longrightarrow &{} \mathbb {F}_q[X]/(X^n-1) \\ (c_0,\dots ,c_{n-1}) &{} \longmapsto &{} \sum _{i=0}^{n-1}c_iX^i. \end{array} \right. \end{aligned}$$

It is known that cyclic codes of length n over $\mathbb {F}_q$ are in correspondence with the factors of the polynomial $X^n-1$. In particular, given $g(X)|X^n-1$ in $\mathbb {F}_q[X]$, the cyclic code $C_g$ associated to g is

$$\begin{aligned}C_g{\mathop {=}\limits ^{\text {def}}}\{{\textit{\textbf{c}}}\in \mathbb {F}_q^n\ \ \text {such\ that}\ \ g(X)|c(X)\}.\end{aligned}$$

In the same way, the roots of g determine in a unique way the code $C_g$. Hence, let us consider an extension $\mathbb {F}\supseteq \mathbb {F}_q$ such that $\mathbb {F}$ contains the n–th roots of unity and let $\gamma$ be a primitive n–th root of unity.

Definition 7.1

Given $R=\{i_1,\dots , i_m\}\subseteq \{1,\dots , n\}$, we define the $m\times n$ matrix

$$\begin{aligned}M(R){\mathop {=}\limits ^{\text {def}}}\begin{pmatrix} 1 &{} \gamma ^{i_1} &{} \cdots &{} \gamma ^{i_1(n-1)}\\ 1 &{} \gamma ^{i_2} &{} \cdots &{} \gamma ^{i_2(n-1)}\\ \vdots &{} \vdots &{} &{} \vdots \\ 1 &{} \gamma ^{i_m} &{} \cdots &{} \gamma ^{i_m(n-1)} \end{pmatrix}.\end{aligned}$$

To any subset $R\subseteq \{1,\dots , n\}$, one can then associate two cyclic codes.

Definition 7.2

R is called defining set for the code C if

$$\begin{aligned} C=\{{\textit{\textbf{c}}}\in \mathbb {F}_q^n\mid M(R){\textit{\textbf{c}}}^T=0\}. \end{aligned}$$

(37)

Remark 7.3

One can see that if C is defined as in (37), then C is a cyclic code. Indeed, we have $C=C_g$, where $g={{\,\mathrm{lcm}\,}}\{m_i(x)\mid i\in R\}$ and $m_i$ is the minimal polynomial of $\gamma ^i$ on $\mathbb {F}_q$. Note that different defining sets can define the same cyclic code C. By applying several times Frobenius morphism to the set $\{\gamma ^i\mid i\in R\}$, one can find the maximal defining set, also called complete. In this paper we will treat a general situation, where a defining set will not necessarily be complete.

Remark 7.4

Note that, if R is a defining set for a code C, then $C=\tilde{C}\cap \mathbb {F}_q^n$, where $\tilde{C}\subseteq \mathbb {F}^n$ is a cyclic code with parity check matrix M(R). If we denote by ${{\,\mathrm{d}\,}}_R$ the minimum distance of the code $\tilde{C}$, we get ${{\,\mathrm{d}\,}}(C)\hbox {\,\char 062\,}{{\,\mathrm{d}\,}}_R$.

Definition 7.5

R is called generating set for the code C if

$$\begin{aligned} C=\{{\textit{\textbf{a}}}M(R) ~|~{\textit{\textbf{a}}}\in \mathbb {F}^m\}. \end{aligned}$$

(38)

We stress that if R is a generating set for a code C, then C is a code with coefficients in the larger alphabet $\mathbb {F}$ and has generating matrix M(R). In particular, $\dim _{\mathbb {F}}(C)=|R|$.

Remark 7.6

Note that a code C as in (38) is a cyclic code. Indeed C is the dual code of the cyclic code $D\subseteq \mathbb {F}^n$ with defining set R and it is known that the dual of a cyclic code is cyclic itself.

7.1 Roos bound

There are cases where it is possible to bound the minimum distance of a cyclic code. Apart from the BCH bound, another and more general bound has been given by Roos ( [33]).

Definition 7.7

Given $R\subseteq \{1,\dots , n\}$, denote by $\overline{R}$ the smallest set made of consecutive indices modulo n that contains R. Moreover, if S is another subset of $\{1,\dots , n\}$, we can define the sum set

$$\begin{aligned}S+R{\mathop {=}\limits ^{\text {def}}}\{s+r\mod n\mid s\in S, r\in R\}.\end{aligned}$$

Finally, given $a < n$, we define the set $aR{\mathop {=}\limits ^{\text {def}}}\{ar\mod n\mid r\in R\}$.

It is possible to relate the star product of two cyclic codes to the sum of their generating sets.

Proposition 7.8

Let A, B and W be three cyclic codes with generating sets respectively S, R and $S+R$. Then,

$$\begin{aligned}A*B= W.\end{aligned}$$

Proof

First, note that for any $j\in S+R$ we get by Definition 7.7

$$\begin{aligned}j=s+r \mod n\end{aligned}$$

for some $s\in S$ and $r\in R$. Hence,

$$\begin{aligned} (1, \gamma ^j, \dots , \gamma ^{j(n-1)})=(1, \gamma ^s, \dots , \gamma ^{s(n-1)})*(1, \gamma ^r, \dots , \gamma ^{r(n-1)}). \end{aligned}$$

(39)

Now, it is easy to see that the set of generators of $A*B$

$$\begin{aligned}G {\mathop {=}\limits ^{\text {def}}}\{(1, \gamma ^{s+r},\dots , \gamma ^{(s+r)(n-1)} )\mid s\in S, r\in R\}\end{aligned}$$

is equal to the set composed by the rows of the matrix $M(S+R)$ (see Definition 7.1). Since, by Definition 7.5, this is a generator matrix for the code W, we get that G is a set of generators for both $A*B$ and W, hence $A*B=W$. $\square$

Theorem 7.9

Let $R, S\subseteq \{1,\dots , n\}$ such that $|\overline{S}|\hbox {\,\char 054\,}|S|+{{\,\mathrm{d}\,}}_R-2$. Then,

$$\begin{aligned}{{\,\mathrm{d}\,}}_{R+S}\hbox {\,\char 062\,}|S|+{{\,\mathrm{d}\,}}_R-1.\end{aligned}$$

Proof

See [33]. $\square$

Remark 7.10

In the hypothesis of Theorem 7.9, if C is the cyclic code with defining set $R+S$, since ${{\,\mathrm{d}\,}}(C)\hbox {\,\char 062\,}{{\,\mathrm{d}\,}}_{R+S}$, then ${{\,\mathrm{d}\,}}(C)\hbox {\,\char 062\,}|S|+{{\,\mathrm{d}\,}}_R-1$ as well.

Remark 7.11

One can note that in the same hypothesis of Theorem 7.9, the proof given in [33] can be adapted to prove that

$$\begin{aligned}{{\,\mathrm{d}\,}}_{aR+bS}\hbox {\,\char 062\,}|S|+{{\,\mathrm{d}\,}}_R-1\end{aligned}$$

for any $a, b\hbox {\,\char 054\,}n$ with $\gcd (a,n)=\gcd (b,n)=1$.

7.2 $\ell$–PELP algorithm and Roos bound

We now focus on cyclic codes with defining set $R+S$ with R and S satisfying the hypothesis of Roos bound (Theorem 7.9). Actually, we will work with the code in $\mathbb {F}^n$ for the sake of simplicity.

Theorem 7.12

Let $a, b\hbox {\,\char 054\,}n$ with $\gcd (a, n)= \gcd (b, n)=1$ and let $A,B\subseteq \mathbb {F}^n$ be cyclic codes with generating sets respectively aS and bR, where

$$\begin{aligned}|\overline{S}|\hbox {\,\char 054\,}|S|+{{\,\mathrm{d}\,}}_R-2,\qquad |S|>t,\qquad {{\,\mathrm{d}\,}}_S>t.\end{aligned}$$

Let $\tilde{C}\subseteq \mathbb {F}^n$ be the cylic code with parity check matrix $M(aS+bR)$ and $k=\dim (\tilde{C})$. Let us suppose that

• (i) for any $i \in \{1, \dots , \ell -1\}$ we have $B^{\perp }*\tilde{C}^i\varsubsetneq \mathbb {F}_q^n$;

• (ii) any nonzero cyclic subcode of B is non degenerated.

Then (A, B) is an $\ell$–power t–error locating pair for the code $\tilde{C}$ with

$$\begin{aligned} t\hbox {\,\char 054\,}\ell n-\Big [\frac{\ell (\ell +1)}{2}(k-1) + \ell (|S|+\delta )+\sum _{i=1}^{\ell -1}\gamma _i\Big ], \end{aligned}$$

(40)

where $\delta$ and $\gamma _1,\dots , \gamma _{\ell -1}$ fulfill

$$\begin{aligned} n-k= & {} |S|+|R|-1 +\delta \nonumber \\ \dim (B)= & {} \dim ((B^{\perp }*\tilde{C}^i)^{\perp })+i\dim (\tilde{C})-i+\gamma _i\ \ \ \forall i=1,\dots , \ell -1. \end{aligned}$$

(41)

Remark 7.13

Note that if (A, B) is an $\ell$–power t–error locating pair for $\tilde{C}$, then it is an $\ell$–power t–error locating pair for the cyclic code C with defining set $aS+bR$ as well. Actually it is a standard procedure for cyclic codes (see for instance [7]). In particular, that is why if $\tilde{C}$ is a Reed–Solomon code, the optimised choice of PELP for $\tilde{C}$ with $|S|=t+1$, will give the decoding radius found in Sect. 5.

Remark 7.14

Condition (ii) on B can be reformulated as follows: for any non empty subset U of R, there does not exist $i \in \mathbb {Z}/n\mathbb {Z}$ such that $U + i \equiv U \mod n$.

Before proving Theorem 7.12, we need the two following lemmas on the notion of degenerated codes (see Sect. 2.5.2).

Lemma 7.15

Let $C \subseteq \mathbb {F}_q^n$ be a degenerated code. Then for any code $D \subseteq \mathbb {F}_q^n$, the code $C *D$ is degenerated too.

Proof

It suffices to observe that $\text {Stab}(C) \subseteq \text {Stab}(C *D)$. $\square$

Lemma 7.16

A code $C \subseteq \mathbb {F}_q^n$ is degenerated if and only if $C^{\perp }$ is degenerated.

Proof

Using the adjunction property (2) of the star product, one proves that $\text {Stab}(C) = \text {Stab}(C^\perp )$. $\square$

Proof of Theorem 7.12

We treat the case $a=b=1$, the general case being an easy generalisation. We have by hypothesis $\dim (A)=|S|>t$. Next, from Proposition 7.8, $A*B=\tilde{C}^{\perp }$. Furthermore, we have ${{\,\mathrm{d}\,}}(A^{\perp })={{\,\mathrm{d}\,}}_S>t$. Hence, properties ($\ell$–PELP1), ($\ell$–PELP2) and ($\ell$–PELP3) are satisfied.

Now, let us focus on property ($\ell$–PELP4). We have that A is contained in the code with generating set $\overline{S}$, whose distance is $n-|\overline{S}|+1$ (note that it is a generalised Reed–Solomon code). Hence, we get ${{\,\mathrm{d}\,}}(A)\hbox {\,\char 062\,}n-|\overline{S}|+1$, which, together with Roos bound, gives

$$\begin{aligned}{{\,\mathrm{d}\,}}(A)+{{\,\mathrm{d}\,}}(\tilde{C})\hbox {\,\char 062\,}n-|\overline{S}|+|S|+{{\,\mathrm{d}\,}}_R\hbox {\,\char 062\,}n+2>n.\end{aligned}$$

In order to check Property ($\ell$–PELP5), we first consider the case $\ell = 2$. Set $W{\mathop {=}\limits ^{\text {def}}}~(B^{\perp }*~\tilde{C})^{\perp }$. Then,

$$\begin{aligned} W\perp B^{\perp }*\tilde{C}\iff W*\tilde{C}\subseteq B. \end{aligned}$$

(42)

From Condition (ii) on B, the code $W *\tilde{C}$ is non degenerated. This last observation, together with inclusion (42) and Corollary 2.12 yield

$$\begin{aligned}\dim (W)+\dim (\tilde{C})-1+\gamma _1= \dim (B)\end{aligned}$$

for some nonnegative integer $\gamma _1$. Next, since $W *\tilde{C}$ is non degenerated, from Lemmas 7.15 and 7.16, the code $W^\perp = B^\perp *C$ is non degenerated too. Thus, we get

$$\begin{aligned} (2\text {--PELP}5):\ \dim (B)+\dim (B^{\perp }*\tilde{C})^{\perp } \hbox {\,\char 062\,}t\iff & {} 2\dim (B)-\dim (\tilde{C})+1-\gamma _1\hbox {\,\char 062\,}t \nonumber \\\iff & {} 2|R|-k+1-\gamma _1\hbox {\,\char 062\,}t. \end{aligned}$$

(43)

Now, since $A*B = \tilde{C}^{\perp }$, using Corollary 2.12 again, we know that there exists $\delta \hbox {\,\char 062\,}0$ such that

$$\begin{aligned} |S|+|R|-1 +\delta = n-k. \end{aligned}$$

(44)

Hence, by (43) and (44), property (2–PELP5) is equivalent to

$$\begin{aligned}t\hbox {\,\char 054\,}2n-3k+3-2\delta -\gamma _1 -2|S|.\end{aligned}$$

It is now easy to generalise the proof for $\ell >2$. Indeed if we consider $i>2$ and $Z{\mathop {=}\limits ^{\text {def}}}(B^{\perp }*\tilde{C}^i)^{\perp }$, we have as before

$$\begin{aligned}Z*\tilde{C}^i\subseteq B.\end{aligned}$$

From Condition (ii) together with Lemma 7.15, we deduce that $\tilde{C}^i$ is non degenerated. Then, by applying Corollary 2.12 iteratively and thanks to Condition (ii) again, we know that there exist two nonnegative integers $\gamma '$ and $\gamma ''$ such that

$$\begin{aligned} \dim (\tilde{C}^i)&=i\dim (\tilde{C})-i+1+\gamma '\\ \dim (B)&=\dim (Z)+\dim (\tilde{C}^i)-1+\gamma ''. \end{aligned}$$

Note that these two equations give (41) with $\gamma _i{\mathop {=}\limits ^{\text {def}}}\gamma '+\gamma ''$. Finally, by combining (41) and (44), we get that Property ($\ell$–PELP5) for $\ell >2$ is equivalent to the bound in (40). $\square$

Remark 7.17

Note that $\delta$ and the ${\gamma _i}'$s do not depend only on the choice of R and S but also on the parameters a, b. Hence, in particular, the decoding radius depends as well on a, b.

7.3 Comparison with Roos bound

We now would like to compare the obtained decoding radius to Roos bound. To do so, we consider a particular case of cyclic code. Let $R,S\subseteq \{1,\dots , n\}$ such that $|R|=|\overline{R}|=r$, $|S|>t$ and $|\overline{S}|\hbox {\,\char 054\,}|S|+{{\,\mathrm{d}\,}}_R-2$. Let us denote by $t_{A,B}$ the decoding radius (40) for $\ell =2$ and by ${{\,\mathrm{d}\,}}_{Roos}$ the amount $|S|+{{\,\mathrm{d}\,}}_R-1$. By the equality $|S|+|R|-1+\delta =n-k$, that is $|S|+r-1+\delta =n-k$, we get

$$\begin{aligned} t_{A,B}\hbox {\,\char 062\,}\frac{{{\,\mathrm{d}\,}}_{Roos}-1}{2}\iff k\hbox {\,\char 054\,}\frac{3n+6-3\delta -2{\gamma _1}' - 4|S|}{5}\cdot \end{aligned}$$

(45)

Remark 7.18

Observe that, if $\gcd (a,n)=\gcd (b,n)=1$, Roos bound holds even for aS and bR. Hence (45) gives an useful information about the behaviour of $t_{A,B}$ for any a, b$\in \mathbb {N}$ with $(a,n)=(b,n)=1$.

Equivalence (45) gives a good information about the parameters to have in order to cross half the Roos bound. Indeed by some tests we made it has been possible to see that the decoding radius $t_{A, B}$ is achieved really often.

Example 7.19

We now give an easy example of a 2–PELP algorithm’s application on a cyclic code (which is not BCH) where $t_{A,B}>\frac{{{\,\mathrm{d}\,}}_{Roos}-1}{2}$. Let us consider $n=51$, $q=5$ and the sets $S=\{0,\dots , 24\}\cup \{30\}$, $R=\{0,\dots ,13\}\cup \{19\}$. According to Remark 7.14, one can check that Condition (ii) of Theorem 7.12 is satisfied by B. We now consider the cyclic code $\tilde{C}$ with parity check matrix $M(S+R)$. Since we are in the hypothesis of Roos bound and ${{\,\mathrm{d}\,}}_R=15$, we obtain $\frac{{{\,\mathrm{d}\,}}_{Roos}-1}{2}=19$, while $t_{A,B}=23$. In fact, the true minimum distance of $\tilde{C}$ can be computed to be 45. Hence we get

$$\begin{aligned}t_{A,B}=23>\frac{{{\,\mathrm{d}\,}}(\tilde{C})-1}{2}=22.\end{aligned}$$

8 Conclusion

We proposed a unified framework for a decoder that can correct beyond half the minimum distance. Exactly as error correcting pairs can be regarded as an abstraction of Welch–Berlekamp algorithm, our approach called power error locating pairs is an abstraction of power decoding for Reed–Solomon and algebraic geometry codes. This algorithm applies to any code equipped with a power error locating pair structure such as some cyclic codes for instance. In addition our results turn out to have interesting consequences on code based cryptography since we proved that a McEliece like system using algebraic geometry codes with a secret decoder correcting up to Sudan’s radius is unsecure.

On the other hand, our algorithm does not decode Reed–Solomon or algebraic geometry codes up to the Johnson radius. In this direction, finding an abstraction of Rosenkilde’s extension of power decoding [28] would represent an interesting challenge. Such a result would for instance yield an attack to any cryptosystem like the one introduced in [47].

A Power decoding for algebraic geometry codes

We show how the power decoding algorithm adapts to arbitrary algebraic geometry codes. Let $C=C_L(\mathcal {X}, \mathcal {P}, G)$ and $\mathbf{y} =\mathbf{c} +\mathbf{e} \in \mathbb {F}_q^n$ the word we want to correct, where $\mathbf{c} \in C$. We have then

$$\begin{aligned} c={{\,\mathrm{ev}\,}}_{\mathcal {P}}(f)\text { with }f\in L(G). \end{aligned}$$

Furthermore, as in the previous sections, we suppose that ${{\,\mathrm{w}\,}}(\mathbf{e} )=t$ and denote the support of $\mathbf{e}$ by ${I_{{\textit{\textbf{e}}}}}$. We keep the same idea we used in the version of the algorithm for Reed–Solomon codes. Indeed, let us suppose to have $\Lambda \in \mathbb {F}_q(\mathcal {X})$ such that $\Lambda (P_i)=0$ for all $i\in {I_{{\textit{\textbf{e}}}}}$. Then, given $\ell \in \mathbb {N}$ we get

$$\begin{aligned} \Lambda (P_i)y_i^j=\Lambda (P_i)f^j(P_i)\ \ \ \ \forall \ i=1,\dots , n,\ \ j=1,\dots \ell . \end{aligned}$$

(46)

We would like then to find $\Lambda$ as above. It is easy to see that such a $\Lambda$ has to be searched in L(F) for a certain F such that $\deg (F)\hbox {\,\char 062\,}t+g$. (we will give a better bound for that soon). It is possible to see $(\Lambda , f)$ as a solution of

$$\begin{aligned} \lambda (P_i)y_i^j=\lambda (P_i)\phi ^j(P_i)\ \ \ \ \forall \ i=1,\dots , n,\ \ j=1,\dots \ell , \end{aligned}$$

(47)

that is, a system of $n\ell$ equations whose unknowns are the coordinates of $\lambda$ and $\phi$ in the basis of respectively L(F) and L(G). System (47) is not linear in the unknowns though, hence we linearise it by considering a new function $\nu _j:=\lambda \phi ^j$ for any equation. For all $j\in \{1, \dots , \ell \}$, we get

$$\begin{aligned} \nu _j\in L(F)L(jG)\subseteq L(F+jG). \end{aligned}$$

In order to use Theorem 2.9, let us fix $\deg (F)= t+2g$ and suppose $\deg (G)\hbox {\,\char 062\,}2g+1$. We get then the following problem.

Key Problem 3

Given $\mathbf{y} \in \mathbb {F}_q^n$ and $t\in \mathbb {N}$, look for $\lambda ,\nu _1, \dots , \nu _{\ell }\in \mathbb {F}_q^n(\mathcal {X})$ such that

• $\lambda \in L(F)$ with $\deg (F)= t+2g$;

• $\nu _j\in L(F+jG)$ for all $j=1,\dots ,\ell$;

• $\lambda (x_i)y_i=\nu _j(x_i)$ for all $i=1,\dots , n$ and $j=1,\dots , \ell$.

Therefore, even this case, the power decoding algorithm consists in solving a linear system and we will just consider a nonzero solution. Decoding Radius. As in the case of Reed–Solomon codes, we would like to have a solution space of dimension one. A necessary condition for that, is

$$\begin{aligned} \# unknowns\hbox {\,\char 054\,}\# equations+1. \end{aligned}$$

(48)

The number of equations is $n\ell$. For the number of unknowns, we need to know the dimension of the spaces $L(F+jG)$ for all $j=1,\dots , \ell$. The bounds we have set in the hypothesis give

$$\begin{aligned}\nonumber \dim (L(F+jG))=t+g+j\deg (G)+1. \end{aligned}$$

Hence by condition (48) we get the following decoding radius

$$\begin{aligned} t\hbox {\,\char 054\,}\frac{2n\ell -\ell (\ell +1)\deg (G)}{2(\ell +1)}-g -\frac{\ell }{\ell +1}\cdot \end{aligned}$$

(49)

Remark A.1

This bound is not a sufficient condition to have a solution, but it is not even a necessary condition. In fact, as for the power decoding algorithm for Reed–Solomon codes, we could find a good solution even for a larger value of t and on the other hand the algorithm could fail even if t fulfills condition (49).