# Fast Decoding of AG Codes

Peter Beelen, Johan Rosenkilde, and Grigory Solomatov

###### Abstract

We present an efficient list decoding algorithm in the style of Guruswami-
Sudan for algebraic geometry codes. Our decoder can decode any such code using
$\tilde{\mathcal{O}}(s\ell^{\omega}\mu^{\omega-1}(n+g))$ operations in the
underlying finite field, where $n$ is the code length, $g$ is the genus of the
function field used to construct the code, $\ell$ is the designed list size
and $\mu$ is the smallest positive element in the Weierstrass semigroup at
some chosen place; the “soft-O” notation $\tilde{\mathcal{O}}(\cdot)$ is
similar to the “big-O” notation $\mathcal{O}(\cdot)$, but ignores logarithmic
factors. For the interpolation step, which constitutes the computational
bottleneck of our approach, we use known algorithms for univariate polynomial
matrices, while the root-finding step is solved using existing algorithms for
root-finding over univariate power series.

##  1 Introduction

Containing some of the best error-correcting codes currently known, algebraic
geometry (AG) codes have received a lot of attention since their introduction
by Goppa in [15]. The celebrated Guruswami-Sudan decoder [16] for these codes
relies on an interpolation step as well as a root-finding step and is capable
of decoding beyond half the designed minimum distance by returning a list of
all codewords within a certain Hamming distance $\tau$ from the received word.
In this article, we present an efficient realization of this decoder,
achieving the best known complexity in the fully general setting of arbitrary
AG codes. Moreover, except for the particularly simple case of Reed-Solomon
codes, our decoder is at least as fast as all existing decoders which are
tailored for specific families of codes. This article is based on a chapter of
the PhD thesis of the third author [42].

Following the common practice, we will measure algorithmic complexity by
asymptotically upper-bounding the number of arithmetic operations in the
underlying finite field $\mathbb{F}_{q}$, relying on the _big-O_ notation
$\mathcal{O}(\cdot)$ as well as the _soft-O_ notation
$\tilde{\mathcal{O}}(\cdot)$, which ignores logarithmic factors. Formally,
$\tilde{\mathcal{O}}(h)=\bigcup_{j=0}^{\infty}\mathcal{O}(h\log(h)^{j})$ for
any function $h:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$, where
$\mathbb{R}_{\geq 0}$ denotes the set of non-negative real numbers.
Analogously to $\mathbb{R}_{\geq 0}$, we will also write $\mathbb{Z}_{\geq 0}$
and $\mathbb{Z}_{>0}$ for the non-negative and the positive integers
respectively. Our complexity estimates will also involve $\omega$, which
denotes some real number such that the product of any two matrices in
$\mathbb{F}_{q}^{m\times m}$ can be computed using $\mathcal{O}(m^{\omega})$
operations in $\mathbb{F}_{q}$. The naive algorithm for matrix multiplication
yields $\omega=3$, and it is clear that $\omega\geq 2$ in general; the current
record with $\omega<2.37286$ is due to [2].

Our decoder has the complexity
$\tilde{\mathcal{O}}(\ell^{\omega+1}\mu^{\omega-1}(n+g))$, however, in a
series of remarks throughout the article we explain how it can be slightly
improved to $\tilde{\mathcal{O}}(s\ell^{\omega}\mu^{\omega-1}(n+g))$; here $n$
is the code length, $g$ is the genus of the function field used to construct
the code, $\ell$ is the designed list size, $s\leq\ell$ is the multiplicity,
and $\mu$ is the smallest element in the Weierstrass semigroup of some
rational place $P_{\infty}$ which is not one of the evaluation places. As we
will see in Section 2.2, the existence of such $P_{\infty}$ can be assumed
without any loss of generality.

###  1.1 Related work

As mentioned earlier, the paradigm of Guruswami-Sudan list decoding revolves
around two main steps: interpolation and root-finding. As former is generally
more computationally demanding, it has historically received the most
attention. Several authors, including [33, 34, 27, 1, 10], formulated the
interpolation step as a problem of finding a polynomial, minimal with respect
to a weighted monomial order, in a certain vanishing ideal. Prompted by this,
Lee and O’Sullivan developed a technique for obtaining such a polynomial from
a Gröbner basis (of $\mathbb{F}_{q}[x]$-modules), that was itself computed
starting from a particular generating set – first for RS codes [25], and then
for one-point Hermitian codes [26]. The complexity of this strategy was
further improved by Beelen and Brander in [4] by utilizing Alekhnovich’s
algorithm for row reduction of polynomial matrices [1]. Furthermore, their
decoder was applicable to the wider family of one-point codes over $C_{ab}$
curves, making it more general. Specializing back to one-point Hermitian
codes, Rosenkilde and Beelen [32] sped up this approach even more by
delegating the row-reduction phase to the algorithm by Giorgi, Jeannerod and
Villard [13], which is more efficient than the one by Alekhnovich. Doing this
required additional improvements to keep up with the new target complexity,
including efficient computation of the initial $\mathbb{F}_{q}[x]$-basis, as
well as a way of handling fractional weights. The result was the first list-
decoder of one-point Hermitian codes having sub-quadratic complexity in the
code length. In the current article, we generalize the tools from [32] to be
applicable to all AG codes, relying on the conceptual framework from [24] to
represent function field elements using _Apéry systems_.

Before shifting our attention to the root-finding step, we ought to mention
the multivariate interpolation algorithm by Chowdhury, Jeannerod, Neiger,
Schost and Villard [9] – it was the first to enable the currently best
complexity in the special case of RS codes, albeit in a probabilistic manner.
A deterministic algorithm with the same complexity was later given in [21].

Some of the earliest root-finding algorithms for Guruswami-Sudan list-decoding
include Roth and Ruckenstein’s [36] as well as Gao and Shokrollahi’s [12].
Alekhnovich described in [1] an efficient approach for computing the
$\mathbb{F}_{q}[\\![x]\\!]$-roots modulo $x^{\beta}$ of a polynomial
$Q\in\mathbb{F}_{q}[\\![x]\\!][z]$; its complexity was shown in [32] to be
$\tilde{\mathcal{O}}(\beta^{2}\ell)$ operations in $\mathbb{F}_{q}$, where
$\ell$ is the $z$-degree of $Q$. Another technique by Berthomieu, Lecerf and
Quintin [7] achieved the cost $\tilde{\mathcal{O}}(\beta\ell^{2})$. In this
article, we rely on the algorithm by Neiger, Rosenkilde and Schost [29], whose
complexity of $\tilde{\mathcal{O}}(\beta\ell)$ operations is provably quasi-
optimal.

The complexity of our decoder is at least as good as, and often faster than,
the complexity of previous decoders based on the Guruswami-Sudan paradigm. As
far as we know, there is only one exception: in the case of RS codes, the
complexity of the algorithms from [9] or [21] is a factor of $\ell/s$ better.
To illustrate the strength and versatility of our results, in Section 6,
examples are given of the list decoding of various families of AG codes. One
further remark should be made, namely the case of bounded distance decoding.
Setting $s=\ell=1$ and assuming that $g\in\mathcal{O}(n)$, the complexity our
decoder simplifies to $\tilde{\mathcal{O}}(\mu^{\omega-1}n)$. In this case,
the decoder can always correct up to $(d^{*}-1-g)/2$ errors, where $d^{*}$
denotes the designed minimum distance of an AG code, also known as the Goppa
bound. The same decoding radius is achieved in [38] with complexity
$\mathcal{O}(\mu n^{2})$. Since $\mu\leq g$ and we assumed
$g\in\mathcal{O}(n)$, our complexity is better. However, Sakata’s extension of
the Berlekamp-Massey decoder [37, 39] yields a decoding algorithm able to
correct up to at least $(d^{*}-1)/2$ errors. In [18], the complexity in the
case of certain so-called one-point AG codes is $\mathcal{O}(\mu
n^{2}+q^{t+1}(a_{1}+\cdots+a_{t})+tnq^{t})$, where $a_{1},\dots,a_{t}$ form a
minimal set of generators of the Weierstrass semigroup at $P_{\infty}$. To
achieve the same decoding radius with our decoder, we could choose $s$ and
$\ell$ in $\mathcal{O}(g)$, but doing so might not be as efficient, since our
complexity would then increase by a factor of
$\mathcal{O}(g^{\omega+1})\subseteq\mathcal{O}(n^{\omega+1})$.

###  1.2 Strategy outline and contributions

With the aim of making the exposition easier in the subsequent sections of the
article, we now present an overview of the main steps in the proposed decoder.
This consists of a way of simplifying the general setting as well as a way of
efficiently carrying out the classical steps of interpolation and root-
finding. The complete decoder is presented in Section 6, where it is also
exemplified for special cases of AG codes.

  * •

Simplified setting: In Section 2.2, we show how extending the constant field
$\mathbb{F}_{q}$ allows us to make certain simplifying assumptions. The
important takeaway here is that no generality is sacrificed in the process,
while only a minor penalty is introduced into the computational complexity. In
return, we may assume existence of certain rational places, as well as
existence of a special function field element $x$ with controlled zeroes and
poles. Having access to additional rational places is useful for a variety of
reasons, among which is efficient multiplication of function field elements in
a pointwise manner; the carefully chosen function $x$ acts as a fundamental
building block in the way we represent function field elements.

  * •

Interpolation step: This is the most involved part of the article and requires
all of the computational tools from Section 5 – except for Section 5.6, which
deals with root-finding. In Section 4.1, it is explained how the interpolation
step can be viewed as a problem of finding a “small” element $Q$ in a certain
interpolation module whose underlying ring consists of all functions that have
no poles except for possibly at a fixed rational place $P_{\infty}$. This
ring, denoted by
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, is itself a
free module over $\mathbb{F}_{q}[x]$, which essentially means that we can
represent everything as tuples of univariate polynomials. The computational
path for obtaining $Q$ boils down to first constructing a generating set of
the interpolation module over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, then
expanding this to a generating set over $\mathbb{F}_{q}[x]$, and finally,
using efficient algorithms for matrices over $\mathbb{F}_{q}[x]$ to reduce
this generating set to a “small” basis that contains a satisfactory $Q$.

  * •

Root-finding step: Structurally, the obtained $Q$ is a univariate polynomial
whose coefficients are function field elements; and according to the
Guruswami-Sudan paradigm, list decoding reduces to finding the roots of this
polynomial. We accomplish this by expressing the coefficients of $Q$ as power
series in $x$, which is always possible in our simplified setting in which $x$
is a local parameter of some appropriate rational place. An existing algorithm
for root-finding over the ring of power-series is then used to obtain the
sought roots, albeit represented as power series; the final step of our
decoder therefore consists of converting these roots back to the original
representation as well as discarding any potential “spurious” solutions. All
of this is detailed in Section 5.6.

Our decoder relies on a mixture of new and existing results; the novel
contributions include:

  * •

reduction of the fully general setting to a simpler one (Section 2.2),

  * •

an algorithm for encoding general AG codes with complexity
$\tilde{\mathcal{O}}(\mu n)$ (Section 5.1),

  * •

an interpolation algorithm with complexity
$\tilde{\mathcal{O}}(\mu^{\omega-1}(n+g))$ (Section 5.2),

  * •

a root-finding algorithm with complexity
$\tilde{\mathcal{O}}(\ell^{2}\mu^{\omega-1}(n+g))$ (Section 5.6),

  * •

an algorithm for computing an $\mathbb{F}_{q}[x]$-basis of $\langle
h\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}$ for
any function $h$ (Section 5.4).

Not counting precomputation, all of the algorithms above are sufficiently
efficient to reach our target cost. Although the cost of precomputation has
not been investigated in detail, it is not expected to be much more expensive
than that of Gaussian elimination. A list of all precomputed objects can be
found in Section 6.

##  2 Preliminaries

###  2.1 AG codes

Let $\mathbb{F}_{q}$ be a finite field with $q$ elements, where $q$ is a power
of a prime number $p$. Further, let $F$ be a function field of genus $g$ and
full constant field $\mathbb{F}_{q}$. As is common, we denote by
$\mathbb{P}_{F}$ the set of places of $F$.

For any divisor $A=\sum_{i}n_{i}Q_{i}$ of $F$, we denote by
$\operatorname{supp}(A)$ the support of $A$, which consists of all places
$Q_{i}$ such that $n_{i}\neq 0$. A divisor $A$ is called effective, denoted by
$A\geq 0$, if for all $i$ it holds $n_{i}\geq 0$. Further, the degree of $A$,
is defined as $\deg(A)=\sum_{i}n_{i}\deg(Q_{i}),$ where $\deg(Q_{i})$ denotes
the degree of the place $Q_{i}$.

The well-known Riemann-Roch space of a divisor $A$ is given by

$\mathcal{L}(A)=\\{f\in F\setminus\\{0\\}\mid(f)+A\geq 0\\}\cup\\{0\\}\ ,$

where $(f)$ denotes the divisor of $f$. The Riemann-Roch space
$\mathcal{L}(A)$ is a vector space over $\mathbb{F}_{q}$, whose dimension will
be denoted by $l(A)$. The theorem of Riemann-Roch [43, Theorem 1.5.15] implies
that $l(A)\geq\deg(A)+1-g$ and that equality holds if $\deg(A)\geq 2g-1$.
Moreover $l(A)=0$ if $\deg(A)<0$ since the degree of a principal divisor is
zero.

######  Definition 2.1.

Assume that $F$ has at least $n$ rational places, say $P_{1},\dots,P_{n}$ and
write $D=P_{1}+\cdots+P_{n}$. Further, let $G$ be a divisor of $F$ such that
$\operatorname{supp}(G)\cap\operatorname{supp}(D)=\emptyset$111The assumption
that $\operatorname{supp}(G)\cap\operatorname{supp}(D)=\emptyset$ can be
removed [43, Remark 2.2.15], but doing so does not give new AG codes up to
monomial equivalence.. Then we define

$\mathcal{C}_{\mathcal{L}}(D,G)=\\{\operatorname{ev}_{D}(f)\mid
f\in\mathcal{L}(G)\\}\subset\mathbb{F}_{q}^{n}\ ,$

where for any $f\in\mathcal{L}(G)$,
$\operatorname{ev}_{D}(f)=(f(P_{1}),\dots,f(P_{n}))\in\mathbb{F}_{q}^{n}$.

For future reference, we state some properties of this code, see [43, Chapter
2] for details. First of all, it is well-known that this code has minimum
distance at least $n-\deg(G).$ Since the kernel of $\operatorname{ev}_{D}$ is
$\mathcal{L}(G-D)$, the dimension of the code equals $l(G)-l(G-D)$. In
particular, $\mathcal{C}_{\mathcal{L}}(D,G)$ is the zero code if $\deg(G)<0$.
Further, using the theorem of Riemann-Roch, we see that
$\dim(\mathcal{C}_{\mathcal{L}}(D,G))=n$, i.e.
$\mathcal{C}_{\mathcal{L}}(D,G)=\mathbb{F}_{q}^{n}$, whenever $\deg(G)\geq
n+2g-1$. Because of this, we may assume

$0\leq\deg(G)\leq n+2g-1.$ (2.1)

######  Remark 2.2.

In his original construction, Goppa considered AG codes
$\mathcal{C}_{\Omega}(D,G)$ defined using residues of certain differentials.
These codes can also be obtained as evaluation codes [43, Proposition 2.2.10].
Hence our decoder can also handle codes of the form
$\mathcal{C}_{\Omega}(D,G)$.

###  2.2 Reduction to a simpler setting

In this subsection, we will show that without significant increase of decoding
complexity, we can assume several things about the function field $F$ and the
AG code $\mathcal{C}_{\mathcal{L}}(D,G)$ that will make the exposition of our
decoding algorithm simpler later on. For example, it will be convenient to
have an additional rational place $P_{\infty}$ of $F$ that is not used in the
evaluation map $\operatorname{ev}_{D}$. In fact, for some of our later
algorithms, it will be convenient to have additional rational places as well.
An easy way out is to increase the constant field $\mathbb{F}_{q}$ to
$\mathbb{F}_{q^{e}}$ for some small value of $e$, thus introducing new
rational places that can be used as additional rational places. We will denote
by $F\mathbb{F}_{q^{e}}$, the function field obtained from $F$ by extending
the constant field to $\mathbb{F}_{q^{e}}$.

As far as decoding is concerned, the AG code $\mathcal{C}_{\mathcal{L}}(D,G)$
is in a trivial way a subcode (not $\mathbb{F}_{q^{e}}$-linear, but
$\mathbb{F}_{q}$-linear) of the AG code obtained from the function field
$F\mathbb{F}_{q^{e}}$ using the divisors $\operatorname{Con}(D)$ and
$\operatorname{Con}(G)$, where $\operatorname{Con}$ denotes the conorm with
respect to $F\mathbb{F}_{q^{e}}/F$, [43, Definition 3.1.8]. Since all places
in $\operatorname{supp}(D)$ are rational, we may with slight abuse of notation
write $\operatorname{Con}(D)=D$. Hence if for a given $\tau$, one has a list
decoding algorithm for $\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G))$
that produces all codewords at distance at most $\tau$ from a received word,
one immediately obtains a list decoding algorithm for
$\mathcal{C}_{\mathcal{L}}(D,G)$. However, since multiplication of two
elements in $\mathbb{F}_{q^{e}}$ can be done in $\tilde{\mathcal{O}}(e)$
operations in $\mathbb{F}_{q}$ [8], the value of $e$ should be small for
complexity reasons. Therefore we now give a series of lemmas, each aiming to
show that for small $e$, simplifying assumptions can be made about the
function field $F$ and the code $\mathcal{C}_{\mathcal{L}}(D,G)$.

######  Lemma 2.3.

Let $F$ be a function field over $\mathbb{F}_{q}$ of genus $g$ and denote by
$N_{e}$ the number of rational places of the function field
$F\mathbb{F}_{q^{e}}$ over $\mathbb{F}_{q^{e}}$. If $N,e\in\mathbb{Z}_{>0}$
are such that $e\geq 2\log_{q}\max\\{N,2g+1\\}$, then $N_{e}>N$.

###### Proof.

The Hasse-Weil bound $|(q^{e}+1)-N_{e}|\leq 2q^{e/2}g$ implies that

$\log_{q}N_{e}>\log_{q}(q^{e}-2q^{e/2}g)=e/2+\log_{q}(q^{e/2}-2g)\geq
e/2\geq\log_{q}N\ .$

∎

Now we show that if the function field $F$ has sufficiently many rational
places, then one of them has particularly simple local parameter. Recall that
a function $f\in F$ is called a local parameter for a place $P$ if
$v_{P}(f)=1$, where $v_{P}$ denotes the valuation at $P$.

######  Lemma 2.4.

Let $F$ be a function field over $\mathbb{F}_{q}$ of genus $g$ having a
rational place $P_{\infty}$. Let $\mu$ be the smallest positive element from
the Weierstrass semigroup of $P_{\infty}$. Any set containing at least $3g+1$
rational places distinct from $P_{\infty}$, contains a place $P_{0}$ with
local parameter from $\mathcal{L}(\mu P_{\infty})$.

###### Proof.

Let $x\in\mathcal{L}(\mu P_{\infty})$ be a function satisfying
$v_{P_{\infty}}(x)=-\mu$. First of all, note that the extension
$F/\mathbb{F}_{q}(x)$ is separable. Indeed, assume that $F/\mathbb{F}_{q}(x)$
is inseparable. Then by the general theory of inseparable extensions, we can
find an intermediate field $E$ such that $E/\mathbb{F}_{q}(x)$ is separable
and $F/E$ is purely inseparable. Then by [43, Proposition 3.10.2],
$\mathbb{F}_{q}(x)\subseteq F^{p}=\\{f^{p}\mid f\in F\\}$, where $p$ is the
characteristic. Hence $x=y^{p}$ for some $y\in F.$ Since $x$ has a pole at
$P_{\infty}$ only of order $\mu$, this would imply that the function $y$ also
has a pole at $P_{\infty}$ only of order $\mu/p$. This gives a contradiction
with the minimality of $\mu$.

The above implies that the Hurwitz genus formula (see for example [43,
Corollary 3.4.14]) applies to the extension $F/\mathbb{F}_{q}(x)$. To prove
the lemma, we estimate the genus of $F$ using this formula. We write
$Q_{\infty}=P_{\infty}\cap\mathbb{F}_{q}(x)$, which is the place at infinity
of the rational function field $\mathbb{F}_{q}(x)$. Since
$v_{P_{\infty}}(x)=-\mu$ and $v_{Q_{\infty}}(x)=-1$, we see that
$e(P_{\infty}|Q_{\infty})=\mu$. Now suppose we have $N>3g$ rational places
distinct from $P_{\infty}$, say $P_{1},\dots,P_{N}$. We write
$Q_{i}=P_{i}\cap\mathbb{F}_{q}(x)$ for their restrictions to
$\mathbb{F}_{q}(x)$. For these rational places, we have

$v_{P_{i}}(x-x(P_{i}))=e(P_{i}|Q_{i})v_{Q_{i}}(x-x(P_{i}))=e(P_{i}|Q_{i}).$

Suppose that for every rational place $P_{i}$ it holds that
$e(P_{i}|Q_{i})\geq 2$.

Since $\mu=[F:\mathbb{F}_{q}(x)]$ by [43, Theorem 1.4.11], the Hurwitz genus
formula combined with the estimate $d(P_{i}|Q_{i})\geq e(P_{i}|Q_{i})-1$
implies that

$\displaystyle 2g-2$
$\displaystyle\geq-2[F:\mathbb{F}_{q}(x)]+d(P_{\infty}|Q_{\infty})+\sum_{i=1}^{N}d(P_{i}|Q_{i})$
$\displaystyle\geq-2\mu+(\mu-1)+N(2-1)\ .$

Since $\mu\leq g+1$, we conclude that $N\leq 3g$, a contradiction. Hence for
one of the places $P_{1},\dots,P_{N}$ we have $v_{P_{i}}(x-x(P_{i}))=1.$ ∎

To motivate Lemma 2.4, recall from Lemma 2.3 that by extending our base field
$\mathbb{F}_{q}$ to $\mathbb{F}_{q^{e}}$, we can easily “create” as many new
rational places as we need without compromising our target complexity. By
doing this, we can ensure that there exists a function $x\in\mathcal{L}(\mu
P_{\infty})$ which is also a local parameter of some rational place $P_{0}$
not in $\operatorname{supp}(G)$. As we will see in Section 5, membership of
$x\in\mathcal{L}(\mu P_{\infty})$ allows us to impose an
$\mathbb{F}_{q}[x]$-module structure on the interpolation step of Guruswami-
Sudan decoding. In Section 5 we will use the assumption that $x$ is a local
parameter of $P_{0}$ to represent certain functions in $F$ as power series in
$\mathbb{F}_{q}[\\![x]\\!]$, which allows us to solve the root-finding step
efficiently.

Next we consider a lemma showing that we can assume that the divisor $G$ used
to define the AG code $\mathcal{C}_{\mathcal{L}}(D,G)$ is effective unless the
code is degenerate. We call a code $\mathcal{C}$ degenerate if there exists
$i$ such that $c_{i}=0$ for any codeword
$c=(c_{1},\dots,c_{n})\in\mathcal{C}$. In particular the trivial code
containing only the zero codeword is degenerate.

######  Lemma 2.5.

Let the function field $F$ and divisors $G$ and $D$ be as before. Then either,
the AG code $\mathcal{C}_{\mathcal{L}}(D,G)$ is degenerate or
$\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G))$ is monomially equivalent
over $\mathbb{F}_{q^{e}}$ with $e\geq 1+\lceil\log_{q}(n)\rceil$, to an AG
code $\mathcal{C}_{\mathcal{L}}(D,G^{\prime})$, where $G^{\prime}$ is an
effective divisor of $F\mathbb{F}_{q^{e}}$ of degree $\deg(G)$.

###### Proof.

Consider the finite field extension $\mathbb{F}_{q^{e}}/\mathbb{F}_{q}$ and
for convenience, let us write
$\mathcal{C}=\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G))$ as well as
$\mathcal{C}_{i}=\\{c\in\mathcal{C}\mid c_{i}=0\\}.$ If
$\mathcal{C}_{\mathcal{L}}(D,G)$ is nondegenerate, then so is $\mathcal{C}$.
In this case $\mathcal{C}\neq\mathcal{C}_{i}$ for all $i$. If every codeword
in $\mathcal{C}$ has at least one zero coordinate, then
$\mathcal{C}=\bigcup_{i=1}^{n}\mathcal{C}_{i}$, which implies that
$(q^{e})^{k}\leq n(q^{e})^{k-1}$ with $k=\dim\mathcal{C}.$ We see that in this
case $q^{e}\leq n$, implying $e\leq\log_{q}(n).$ This contradiction shows that
$\mathcal{C}$ contains a codeword of full Hamming weight $n$, say
$c=\operatorname{ev}_{D}(\tilde{f})$ for some
$\tilde{f}\in\mathcal{L}(\operatorname{Con}(G))$. Since by construction
$\tilde{f}(P_{i})\neq 0$ for all $i$, we see that the codes $\mathcal{C}$ and
$\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G)+(\tilde{f}))$ are
monomially equivalent using the map
$(c_{1},\dots,c_{n})\mapsto(\tilde{f}(P_{1})c_{1},\dots,\tilde{f}(P_{n})c_{n})$.
Note that the divisor $G^{\prime}=\operatorname{Con}(G)+(\tilde{f})$ is
effective and has support disjoint from $D$. ∎

Degenerate codes are not very interesting from the error-correcting point of
view. Indeed, if the $i$-th coordinate of all codewords is zero, it is trivial
to correct errors in that position. On the other hand that position does not
carry any information, so one might as well consider the punctured code where
such a position has been removed, which will have the same dimension and
minimum distance. Decoding a degenerate code can therefore be reduced using
puncturing to decoding a nondegenerate code. Note that since the codes
$\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G))$ and
$\mathcal{C}_{\mathcal{L}}(D,G^{\prime})$ are monomially equivalent, any
(list) decoding algorithm for $\mathcal{C}_{\mathcal{L}}(D,G^{\prime})$
immediately gives a (list) decoding algorithm for
$\mathcal{C}_{\mathcal{L}}(D,\operatorname{Con}(G))$. The added complexity is
that of dividing and multiplying with the column multipliers
$\tilde{f}(P_{i})$, which only costs $\mathcal{O}(n)$ operations in
$\mathbb{F}_{q^{e}}$ and hence $\tilde{\mathcal{O}}(ne)$ operations in
$\mathbb{F}_{q}$. Moreover, as we will see, we will be able to choose $e$ so
small that it will not affect the decoding complexity at all in the
$\tilde{\mathcal{O}}$ notation.

Now we state the simplifying assumptions and notation that will be used in the
remainder of this article.

  1. 1.

We assume that $G$ is an effective divisor, whose degree satisfies equation
(2.1).

  2. 2.

We assume that apart from the rational places in $D=P_{1}+\cdots+P_{n}$, the
function field $F$ has at least one more rational place $P_{\infty}$. The
place $P_{\infty}$ may or may not be in $\operatorname{supp}(G)$.

  3. 3.

There exists a rational place $P_{0}$ of $F$ which has $x$ as a local
parameter, where $x\in F$ is a function with pole at $P_{\infty}$ only of
minimal pole order $\mu$. The place $P_{0}$ may be in
$\operatorname{supp}(D)$, but is not in $\operatorname{supp}(G)$.

Let us quickly assess the size of the needed extension degree $e$ in order to
satisfy all three item simultaneously. Although one likely can do better, for
our purposes it is sufficient to pick $e=e_{1}e_{2}e_{3}$, where
$e_{1},e_{2},e_{3}$ are given below: to satisfy the first item, we extend
$\mathbb{F}_{q}$ to $\mathbb{F}_{q^{e_{1}}}$, where
$e_{1}=1+\lceil\log_{q}(n)\rceil$, using Lemma 2.5. To satisfy the second
item, we apply Lemma 2.3 with $N=n+1$. Hence we can choose $e_{2}=\lceil
2\log_{q^{e_{1}}}\max\\{n+1,2g+1\\}\rceil$ and extend $\mathbb{F}_{q^{e_{1}}}$
to $\mathbb{F}_{q^{e_{1}e_{2}}}$. For the third item, we need apart from
$P_{\infty}$ and possible rational places in $\operatorname{supp}(G)$, an
additional $3g+1$ rational places. Since $G$ is effective, we can apply Lemma
2.3 with $N=1+\deg(G)+3g+1$, so using equation (2.1), we can choose
$e_{3}=\lceil 2\log_{q^{e_{1}e_{2}}}(5g+1+n)\rceil$ extending
$\mathbb{F}_{q^{e_{1}e_{2}}}$ to $\mathbb{F}_{q^{e}}$. Using that
$\log_{q^{f}}(A)=\log_{q}(A)/f$, it is easy to see that

$\displaystyle e=e_{1}e_{2}e_{3}$ $\displaystyle\leq
2\log_{q}(5g+1+n)+e_{1}e_{2}$ $\displaystyle\leq
2\log_{q}(5g+1+n)+2\log_{q}\max\\{n+1,2g+1\\}+e_{1}$ $\displaystyle\leq
2\log_{q}(5g+1+n)+2\log_{q}\max\\{n+1,2g+1\\}+\log_{q}(n)+2.$

Hence the overall conclusion is that in terms of complexity only a logarithmic
factor in $n+g$ is introduced when reducing from the general case to the
simpler setting. In the remainder of this article, instead of writing
$\mathbb{F}_{q^{e}}$, we will simply write $\mathbb{F}_{q}$ and assume $q$ is
large enough so that all three simplifying assumptions stated above are
satisfied.

###  2.3 Shifted Popov forms of polynomial matrices

Our decoder relies on efficient algorithms for (free)
$\mathbb{F}_{q}[x]$-submodules of $\mathbb{F}_{q}[x]^{m}$; in the current
subsection, we present well known results and definitions that we need needed
for our use cases. For a comprehensive introduction, the reader is referred to
[44] and the references within.

We begin with a definition which, among other things, allows us to measure
“size” of elements in $\mathbb{F}_{q}[x]^{m}$.

######  Definition 2.6.

For any polynomial vector $\bm{v}=(v_{1},\dots,v_{m})\in\mathbb{F}_{q}[x]^{m}$
and any $\bm{s}=(s_{1},\dots,s_{m})\in\mathbb{Z}^{m}$ (which we refer to as a
_shift_), we define the _$\bm{s}$ -degree_ of $\bm{v}$ as

$\deg_{\bm{s}}\bm{v}=\max_{k}\\{\deg v_{k}+s_{k}\\}\ .$

Furthermore, if $k\in\\{1,\dots,m\\}$ is maximal such that $\deg
v_{k}+s_{k}=\deg_{\bm{s}}\bm{v}$, then we say that $v_{k}$ is the _$\bm{s}$
-pivot_ of $\bm{v}$, and $k$ is its _$\bm{s}$ -pivot index_. If $\bm{s}=0$,
then we might omit writing $\bm{s}$ in the above notation, i.e. we might
simply write: _pivot_ , _pivot index_ and _degree_ , denoting the latter by
$\deg\bm{v}:=\deg_{\bm{0}}\bm{v}$.pp

Any $\mathbb{F}_{q}[x]$-basis of a submodule
$\mathcal{V}\subseteq\mathbb{F}_{q}[x]^{m}$ of rank $m$ can be described using
a nonsingular polynomial matrix $\bm{V}\in\mathbb{F}_{q}[x]^{m\times m}$ by
identifying the basis elements with the rows of $\bm{V}$. This way,
$\mathcal{V}$ is viewed as the $\mathbb{F}_{q}[x]$-row space of $\bm{V}$. We
will be interested in obtaining the basis whose elements are “smallest
possible”; the following definition makes this notion precise in the context
of polynomial matrices.

######  Definition 2.7.

Given a shift $\bm{s}\in\mathbb{Z}^{m}$, a nonsingular matrix
$\bm{P}\in\mathbb{F}_{q}[x]^{m\times m}$ is said to be in _$\bm{s}$ -Popov
form_ if all of the $\bm{s}$-pivots of its rows lie on the diagonal, are monic
and have degrees strictly greater than all other entries in their respective
columns. Furthermore, if $\bm{P}$ shares its $\mathbb{F}_{q}[x]$-row space
with some matrix $\bm{V}\in\mathbb{F}_{q}[x]^{r\times m}$, where $m\leq r$,
then $\bm{P}$ is said to be _the $\bm{s}$-Popov form_ of $\bm{V}$.

Below, we summarize a few important structural properties of shifted Popov
forms.

######  Proposition 2.8 ([44, Section 1.1]).

For any nonsingular matrix $\bm{V}\in\mathbb{F}_{q}[x]^{m\times m}$ and any
shift $\bm{s}\in\mathbb{Z}^{m}$, there exists a unique matrix
$\bm{P}\in\mathbb{F}_{q}[x]^{m\times m}$ in $\bm{s}$-Popov form having the
same $\mathbb{F}_{q}[x]$-row space as $\bm{V}$. Furthermore, $\bm{P}$ has
minimal shifted row degrees in the following sense: for any
$\bm{V}\in\mathbb{F}_{q}[x]^{m\times m}$ with the same row space as $\bm{P}$,
there exists a bijection between the rows of the two matrices such that the
$\bm{s}$-degree of any row of $\bm{V}$ is no smaller than that of the
corresponding row of $\bm{P}$. Finally, for any nonzero vector
$\bm{v}\in\mathbb{F}_{q}[x]^{1\times m}$ in the row space of $\bm{P}$ with
$\bm{s}$-pivot index $k$ it holds that
$\deg_{\bm{s}}\bm{v}\geq\deg_{\bm{s}}\bm{p}^{(k)}$, where $\bm{p}^{(k)}$
denotes the $k$-th row of $\bm{P}$.

We conclude this subsection with a few complexity bounds.

######  Proposition 2.9 ([30, Theorem 1.3]).

There is a deterministic algorithm which for any shift
$\bm{s}\in\mathbb{Z}^{m}$ computes the $\bm{s}$-Popov form of any nonsingular
matrix $\bm{V}\in\mathbb{F}_{q}[x]^{m\times m}$ using
$\tilde{\mathcal{O}}(m^{\omega}\deg\bm{M})$ operations in $\mathbb{F}_{q}$,
where $\deg\bm{M}$ denotes the maximal degree among all entries in $\bm{M}$.

######  Proposition 2.10 ([46]).

There is a deterministic algorithm which for any matrix
$\bm{V}\in\mathbb{F}_{q}[x]^{r\times m}$ with $m\leq r$ computes an
$\mathbb{F}_{q}[x]$-basis of the row space of $\bm{V}$ using
$\tilde{\mathcal{O}}(rm^{\omega-1}\deg\bm{V})$ operations in $\mathbb{F}_{q}$.

Combining Proposition 2.10 with Proposition 2.9, we obtain the following:

######  Corollary 2.11.

For any shift $\bm{s}\in\mathbb{Z}^{m}$ and any matrix
$\bm{V}\in\mathbb{F}_{q}[x]^{r\times m}$ with rank $m\leq r$, we can compute
the $\bm{s}$-Popov form of $\bm{V}$ using
$\tilde{\mathcal{O}}(rm^{\omega-1}\deg\bm{V})$ operations in $\mathbb{F}_{q}$.

##  3 Representation of function field elements

For any divisor $A$ of $F$, let
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)=\bigcup_{m=-\infty}^{\infty}\mathcal{L}(mP_{\infty}+A)$
and let
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(0)$.
Note that $\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ is a
ring and $\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ a
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module. In
fact more can be said:
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ is a Dedekind
domain and $\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$
is a fractional ideal of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, [31, Section
1.2].

Modules of the form
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ are
essentially already considered for decoding in [23], also see [5, 24]. As in
[24], for any nonzero
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ we
denote by $\delta_{A}(a)$ the smallest integer $m$ such that
$a\in\mathcal{L}(mP_{\infty}+A)$, i.e.
$\delta_{A}(a)=-v_{P_{\infty}}(a)-v_{P_{\infty}}(A)$ and let
$\delta(a)=\delta_{0}(a)=-v_{P_{\infty}}(a)$. We will take as convention that
$\delta_{A}(0)=-\infty$. Note that for any
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ and
$b\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(B)$, one
has $\delta_{A+B}(ab)=\delta_{A}(a)+\delta_{B}(b).$

It is well known that any fractional ideal of a Dedekind domain can be
generated by at most two elements [11, Corollary 2 to Theorem 4], but for our
purposes we need to know some properties of these generators.

######  Lemma 3.1.

Let $A=\sum_{i=1}^{t}n_{i}Q_{i}$ be a divisor of $F$ and write
$\mathfrak{a}=\sum_{i}\deg Q_{i}$. Then
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ can be
generated as a
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module by two
elements $a_{1}$ and $a_{2}$ satisfying $\delta_{A}(a_{1})\leq
2g-1-\deg(A)+\mathfrak{a}$ and $\delta_{A}(a_{2})\leq
4g-2-\deg(A)+\mathfrak{a}$.

###### Proof.

Prime ideals of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ correspond
exactly to places of $F$ distinct from $P_{\infty}$. Therefore, from the proof
of Corollary 2 to Theorem 4 in [11], we see that two elements
$a_{1},a_{2}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$
generate $\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ as
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module if and
only if for all places $Q_{i}\in\operatorname{supp}(A)$ distinct from
$P_{\infty}$, we have $\min\\{v_{Q_{i}}(a_{1}),v_{Q_{i}}(a_{2})\\}=-n_{i}$ and
for any other place $Q\neq P_{\infty}$ of $F$ we have
$\min\\{v_{Q}(a_{1}),v_{Q}(a_{2})\\}=0.$ We will construct two such elements.

Write $m_{1}=2g-1-\deg(A)+\mathfrak{a}$. For $j=1,\dots,t$, choose
$a_{1}^{(j)}\in\mathcal{L}(A-\sum_{i\neq
j}Q_{i}+m_{1}P_{\infty})\setminus\mathcal{L}(A-\sum_{i}Q_{i}+m_{1}P_{\infty})$.
Note that such $a_{1}^{(j)}$ exist, since by the Riemann-Roch theorem,
$l(A-\sum_{i\neq j}Q_{i}+m_{1}P_{\infty})>l(A-\sum_{i}Q_{i}+m_{1}P_{\infty})$.
Defining $a_{1}=\sum_{j=1}^{t}a_{1}^{(j)}$, we see that
$v_{Q_{i}}(a_{1})=-n_{i}$ for $j=1,\dots,t$, while $v_{Q}(a_{1})\geq 0$ for
any other place $Q$ distinct from $P_{\infty}$. In particular
$a_{1}\in\mathcal{L}(A+m_{1}P_{\infty})$, whence $\delta_{A}(a_{1})\leq
m_{1}.$

Now suppose that $Q_{t+1},\dots,Q_{t+s}$ are the zeroes of $a_{1}$ not in
$\operatorname{supp}(A)\cup\\{P_{\infty}\\}$. Since
$a_{1}\in\mathcal{L}(A+m_{1}P_{\infty})$, we see that
$\sum_{i=t+1}^{t+s}\deg(Q_{i})\leq\deg(A)+m_{1}$. Now define
$m_{2}=2g-1+m_{1}=4g-2-\deg(A)+\mathfrak{a}$. Similarly as above, we can
construct $a_{2}\in\mathcal{L}(A+m_{2}P_{\infty})$, such that
$v_{Q_{i}}(a_{2})=0$ for $i=t+1,\dots,t+s$. By construction
$\delta_{A}(a_{2})\leq m_{2}$. For $i=1,\dots,t$, we have
$v_{Q_{i}}(a_{2})\geq-n_{i}$ and $v_{Q_{i}}(a_{1})=-n_{i}$, whence
$\min\\{v_{Q_{i}}(a_{1}),v_{Q_{i}}(a_{2})\\}=-n_{i}$. If
$Q\not\in\operatorname{supp}(A)\cup\\{P_{\infty}\\}$ is not a zero of $a_{1}$,
then $\min\\{v_{Q}(a_{1}),v_{Q}(a_{2})\\}=0$, since $v_{Q}(a_{2})\geq 0$. If
$Q\not\in\operatorname{supp}(A)\cup\\{P_{\infty}\\}$ is a zero of $a_{1}$,
then $v_{Q}(a_{2})=0$, so that also in this case
$\min\\{v_{Q}(a_{1}),v_{Q}(a_{2})\\}=0$. Hence $a_{1}$ and $a_{2}$ as
constructed above, generated
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ as a
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module. ∎

As
$x\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}\setminus\mathbb{F}_{q}$,
we can also view
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ as a free
$\mathbb{F}_{q}[x]$-module. Following [24], we consider a special set of
generators of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ as
$\mathbb{F}_{q}[x]$-module, which they called the Apéry system of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.

######  Definition 3.2.

For any divisor $A$ let $y^{(A)}_{i}\in\mathcal{A}_{i}$ be such that
$\delta_{A}(y^{(A)}_{i})\leq\delta_{A}(a)$ for all $a\in\mathcal{A}_{i}$,
where $i=0,\dots,\mu-1$ and

$\mathcal{A}_{i}=\\{a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\mid\delta_{A}(a)\equiv
i\mod\mu\\}\ .$

We also define $y_{i}=y^{(0)}_{i}$.

######  Lemma 3.3.

For any divisor $A$ it holds that

  1. 1.

$y^{(A)}_{0},\dots,y^{(A)}_{\mu-1}$ is an $\mathbb{F}_{q}[x]$-basis of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ and

  2. 2.

$-\deg A\leq\delta_{A}(y^{(A)}_{i})\leq 2g-1-\deg(A)+\mu$ for
$i=0,\dots,\mu-1$.

###### Proof.

The first statement is from [24]. For the convenience of the reader we give a
proof. From the strict triangle inequality for $v_{P_{\infty}}$, it is clear
that the elements $y^{(A)}_{0},\dots,y^{(A)}_{\mu-1}$ are linearly independent
over $\mathbb{F}_{q}[x]$. Also, it is clear that
$\mathcal{Y}\subseteq\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
where $\mathcal{Y}=\langle
y^{(A)}_{0},\dots,y^{(A)}_{\mu-1}\rangle_{\mathbb{F}_{q}[x]}$. If
$\mathcal{Y}\neq\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
then there would exist
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\setminus\mathcal{Y}$,
such that $\delta_{A}(a)>-\infty$ is minimal. Write $\delta_{A}(a)=m\mu+r$ and
$\delta_{A}(y^{(A)}_{r})=m^{\prime}\mu+r$, where $m,m^{\prime},r\in\mathbb{Z}$
with $0\leq r<\mu$. Note that $m^{\prime}\leq m$ by definition of
$y^{(A)}_{r}$. Since

$\delta_{A}(x^{m-m^{\prime}}y^{(A)}_{r})=\delta(x^{m-m^{\prime}})+\delta_{A}(y^{(A)}_{r})=(m-m^{\prime})\mu+(m^{\prime}\mu+r)=\delta_{A}(a)\
,$

there exists a constant $\beta\in\mathbb{F}_{q}$ such that
$\delta_{A}(c)<\delta_{A}(a)$, where $c=a-\beta
x^{m-m^{\prime}}y^{(A)}_{r}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.
The minimality of $\delta_{A}(a)$ guarantees that $c\in\mathcal{Y}$, however,
this would imply that $a=c+\beta x^{m-m^{\prime}}y^{(A)}_{r}\in\mathcal{Y}$.
Hence
$\mathcal{Y}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
which is a contradiction.

In the second statement, the lower bound simply follows from the fact that
$y^{(A)}_{i}\in\mathcal{L}(\delta_{A}(y^{(A)}_{i})P_{\infty}+A)\neq\\{0\\}$.
For the upper bound it is sufficient to show that for every integer
$m>2g-1-\deg(A)$ there exists an
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ with
$\delta_{A}(a)=m$. But indeed, if $m>2g-1-\deg(A)$, then
$\deg(mP_{\infty}+A)>2g-1$, and so [43, Theorem 1.5.17] implies that

$\mathcal{L}(mP_{\infty}+A)\neq\mathcal{L}\big{(}(m-1)P_{\infty}+A\big{)}\ ,$

which concludes the proof. ∎

For later use, we also state the following lemma.

######  Lemma 3.4.

If
$a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
where $a_{i}\in\mathbb{F}_{q}[x]$ and $A$ is a divisor, then

$\deg
a_{i}\leq\frac{1}{\mu}(\delta_{A}(a)-\delta_{A}(y^{(A)}_{i}))\leq\frac{1}{\mu}(\delta_{A}(a)+\deg
A)\ .$

###### Proof.

Simply observe that for $i=0,\dots,\mu-1$ it holds that

$\delta_{A}(a)=\max_{j}\delta_{A}(a_{j}y^{(A)}_{j})\geq\delta(a_{i})+\delta_{A}(y^{(A)}_{i})\geq\delta(a_{i})-\deg
A\ ,$

where the equality follows from the strict triangle inequality for
$v_{P_{\infty}}$ and second inequality is given by Lemma 3.3. But then

$\deg
a_{i}=\delta(a_{i})/\mu\leq\frac{1}{\mu}(\delta_{A}(a)-\delta_{A}(y^{(A)}_{i}))\leq\frac{1}{\mu}(\delta_{A}(a)+\deg
A)\ .$

∎

##  4 Guruswami-Sudan Decoding

In this section, we paraphrase the Guruswami-Sudan list decoding algorithm
[17] for $\mathcal{C}_{\mathcal{L}}(D,G)$ and formulate it in terms of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ modules. For
the remainder of this paper fix $s,\ell\in\mathbb{Z}_{>0}$, $s\leq\ell$, where
$s$ is the multiplicity parameter and $\ell$ the designed list size of the
Guruswami-Sudan list decoder. The corresponding list decoding radius will be
denoted by $\tau$.

######  Definition 4.1.

Let $P$ be a rational place of $F$, $r\in\mathbb{F}_{q}$ and $Q\in F[z]$. We
will say that “$Q$ has a root of multiplicity $s$ at $(P,r)$” if for any local
parameter $\phi$ of $P$, there exist $c_{a,b}\in\mathbb{F}_{q}$ such that

$Q=\sum_{\begin{subarray}{c}a,b\geq 0\\\ a+b\geq
s\end{subarray}}c_{a,b}\phi^{a}(z-r)^{b}$

with $c_{a,s-a}\neq 0$ for at least one $0\leq a\leq s$.

A consequence of this definition is the following:

######  Lemma 4.2.

If $Q\in F[z]$ has a root of multiplicity $s$ at $(P,r)$ and $f\in F$ is such
that $f(P)=r$, then $v_{P}(Q(f))\geq s$.

###### Proof.

Writing

$Q(f)=\sum_{\begin{subarray}{c}a,b\geq 0\\\ a+b\geq
s\end{subarray}}c_{a,b}\phi^{a}(f-r)^{b}\ ,$

where $\phi$ is any local parameter of $P$ and $c_{a,b}\in\mathbb{F}_{q}$, the
triangle inequality directly implies that

$v_{P}(Q(f))\geq\min_{\begin{subarray}{c}a,b\geq 0\\\ a+b\geq
s\end{subarray}}\big{(}v_{P}(\phi^{a})+v_{P}((f-r)^{b})\big{)}\geq\min_{\begin{subarray}{c}a,b\geq
0\\\ a+b\geq s\end{subarray}}(a+b)\geq s\ .$

∎

For any $Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}$ with
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
we define $\delta_{G}(Q)=\max_{t}\delta_{-tG}(Q^{(t)})$. Moreover, for a given
received word $\bm{r}=(r_{1},\dots,r_{n})\in\mathbb{F}_{q}^{n}$, we write

$\begin{multlined}\mathcal{M}_{s,\ell}(D,G)=\\{Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\in
F[z]\mid
Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG),\\\
\text{$Q$ has a root of multiplicity at least $s$ at $(P_{j},r_{j})$ for
$j=1,\dots,n$}\\}.\end{multlined}\mathcal{M}_{s,\ell}(D,G)=\\{Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\in
F[z]\mid
Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG),\\\
\text{$Q$ has a root of multiplicity at least $s$ at $(P_{j},r_{j})$ for
$j=1,\dots,n$}\\}.$ (4.1)

######  Theorem 4.3 (Special case of Guruswami–Sudan [17]).

Let $\bm{r}$ be a received word and $Q\in\mathcal{M}_{s,\ell}(D,G)$ with
$\delta_{G}(Q)<s(n-\tau)$. If $f\in\mathcal{L}(G)$ such that the Hamming
weight of $\bm{r}-\operatorname{ev}_{D}(f)$ is at most $\tau$, then $Q(f)=0$.

###### Proof.

Since $f^{t}\in\mathcal{L}(tG)$ and
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$,
then
$f^{t}Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$,
and consequently
$Q(f)\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$.
Furthermore, since $\delta_{tG}(f^{t})\leq 0$, then by the triangle inequality

$\delta(Q(f))\leq\max_{t}\delta_{-tG}(Q^{(t)})=\delta_{G}(Q)\ .$

We write $\mathcal{E}=\\{j\mid r_{j}\neq f(P_{j})\\}$. Note that the
cardinality of $\mathcal{E}$ is at most $\tau$. Since $f(P_{j})=r_{j}$ for
$j\not\in\mathcal{E}$, it follows from Lemma 4.2 that
$Q(f)\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-T)$,
where $T=s\sum_{j\not\in\mathcal{E}}P_{j}$. Since
$\delta_{G}(Q)<s(n-\tau)\leq\deg T$, we may conclude that

$Q(f)\in\mathcal{L}\big{(}\delta_{G}(Q)P_{\infty}-T\big{)}=\\{0\\}\ .$

∎

###  4.1 Structure of $\mathcal{M}_{s,\ell}(D,G)$ as a
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module

The set $\mathcal{M}_{s,\ell}(D,G)$ introduced in equation (4.1) is easily
seen to be a module over the ring
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$. In this
subsection, we determine some of its structural properties. For the remainder
of this article let $G_{t}=-tG-\max\\{0,s-t\\}D$ for $t=0,\dots,\ell$.

######  Theorem 4.4.

Let $\bm{r}=(r_{1},\dots,r_{n})$ be a received word and
$R\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G)$ be such
that $R(P_{j})=r_{j}$ for $j=1,\dots,n$. Then it holds that

$\mathcal{M}_{s,\ell}(D,G)=\bigoplus_{t=0}^{\ell}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})\
.$

###### Proof.

Note that for all $j$ and all
$h\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})$,
$v_{P_{j}}(h)\geq\max\\{0,s-t\\}$. Further $(z-R)^{t}$ has a root of
multiplicity $t$ at $(P_{j},r_{j})$, since $R(P_{j})=r_{j}$. Hence any element
in
$(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})$
has a root of multiplicity at least $s$ at $(P_{j},r_{j})$. Moreover, since
$R\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G)$, we see
that
$(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})=\left(\sum_{u=0}^{t}z^{u}\binom{t}{u}(-R)^{t-u}\right)\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})\subseteq\bigoplus_{u=0}^{t}z^{u}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$.
Hence
$(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})\subseteq\mathcal{M}_{s,\ell}(D,G)$.
Since $\mathcal{M}_{s,\ell}(D,G)$ is a
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module, this
implies that
$\bigoplus_{t=0}^{\ell}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})\subseteq\mathcal{M}_{s,\ell}(D,G).$

We will prove the reverse inclusion
$\mathcal{M}_{s,\ell}(D,G)\subseteq\bigoplus_{t=0}^{\ell}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})$
by induction on $s$. Let
$Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\in\mathcal{M}_{s,\ell}(D,G)$ and write
$Q=\sum_{t=0}^{\ell}(z-R)^{t}\tilde{Q}^{(t)}$ for certain $\tilde{Q}^{(t)}\in
F$. Writing $z^{t}=((z-R)+R)^{t}$ and using Newton’s binomium, we obtain

$\tilde{Q}^{(t)}=\sum_{u=t}^{\ell}\binom{u}{t}R^{u-t}Q^{(u)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG),\text{
for $t=0,\dots,\ell$,}$

since $R\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G).$
Now observe that Lemma 4.2 implies that
$\tilde{Q}^{(0)}=Q(R)\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{0}).$

Now if we assume $s=1$, then
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
for $t>0$ and we can conclude from the above that
$Q\in\bigoplus_{t=0}^{\ell}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})$.

If $s>1$, we proceed as follows: using
$\tilde{Q}^{(0)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{0})\subseteq\mathcal{M}_{s,\ell}(D,G)$,
we conclude

$\mathcal{M}_{s,\ell}(D,G)\ni
Q-\tilde{Q}^{(0)}=(z-R)\cdot\sum_{t=0}^{\ell-1}(z-R)^{t}\tilde{Q}^{(t+1)}\,.$

Since $z-R$ has a root of multiplicity one at $(P_{j},r_{j})$ for all $j$, we
see that $\sum_{t=0}^{\ell-1}(z-R)^{t}\tilde{Q}^{(t+1)}$ has a root of
multiplicity at least $s-1$ at $(P_{j},r_{j})$ for all $j$. Hence
$\sum_{t=0}^{\ell-1}(z-R)^{t}\tilde{Q}^{(t+1)}\in\mathcal{M}_{s-1,\ell}(D,G)$.
Then using the induction hypothesis for $s-1$, we may conclude that
$Q\in\bigoplus_{t=0}^{\ell}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t}).$
∎

######  Corollary 4.5 (of Theorem 4.4 and Lemma 3.1).

It holds that

$\displaystyle\mathcal{M}_{s,\ell}(D,G)$ $\displaystyle=\langle
B_{v}^{(u)}|u=0,\dots,\ell,\
v=1,2\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}\
,\quad\text{where}$ $\displaystyle B_{v}^{(u)}$
$\displaystyle=(z-R)^{u}g^{(u)}_{v}=\sum_{r=0}^{u}\binom{u}{r}z^{r}(-R)^{u-r}g^{(u)}_{v}\in\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)\
,$

with
$g^{(u)}_{1},g^{(u)}_{2}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$
such that $\langle
g^{(u)}_{1},g^{(u)}_{2}\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$,

$\delta_{G_{u}}(g_{1}^{(u)})\leq 2g-1+(u+1)\deg(G)+\max\\{0,s-u+1\\}n,$

and

$\delta_{G_{u}}(g_{2}^{(u)})\leq 4g-2+(u+1)\deg(G)+\max\\{0,s-u+1\\}n.$

###### Proof.

The first part directly follows from Theorem 4.4 and Lemma 3.1. To obtain the
stated upper bounds on $\delta_{G_{u}}(g_{1}^{(u)})$ and
$\delta_{G_{u}}(g_{2}^{(u)})$ from Lemma 3.1, note that
$\sum_{Q\in\operatorname{supp}(G)}\deg(Q)\leq\deg(G)$, since $G$ is an
effective divisor. Hence
$\sum_{Q\in\operatorname{supp}(G_{u})}\deg(Q)\leq\deg(G)+n$ if $u<s$, while
$\sum_{Q\in\operatorname{supp}(G_{u})}\deg(Q)\leq\deg(G)$ if $u\geq s.$ The
stated upper bounds are implied by this. ∎

Note that the proof of the corollary actually implies that for $u=s$, the
stated upper bounds for $\delta_{G_{u}}(g_{1}^{(u)})$ and
$\delta_{G_{u}}(g_{2}^{(u)})$ can be improved by $n$.

For computational purposes, we will later view $\mathcal{M}_{s,\ell}(D,G)$ as
an $\mathbb{F}_{q}[x]$ module. Since any element from
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ is an
$\mathbb{F}_{q}[x]$-linear combination of $y_{0},\dots,y_{\mu-1}$, we obtain
the following.

######  Corollary 4.6.

It holds that $\mathcal{M}_{s,\ell}(D,G)=\langle
y_{i}B_{v}^{(u)}|i=0,\dots,\mu-1,u=0,\dots,\ell,\
v=1,2\rangle_{\mathbb{F}_{q}[x]}$.

######  Remark 4.7.

Since $G_{t}=-tG$ for $s\leq t\leq\ell$, a minor modification of the proof of
Theorem 4.4 shows that
$\mathcal{M}_{s,\ell}(D,G)=\bigoplus_{t=0}^{s}(z-R)^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t})\oplus\bigoplus_{t=s+1}^{\ell}(z-R)^{s}z^{t-s}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{t}).$
This shows that the elements $\tilde{B}_{v}^{(u)}=B_{v}^{(u)}$ if $u\leq s$
together with $\tilde{B}_{v}^{(u)}(z-R)^{s}z^{t-s}g^{(u)}_{v}$ if
$s<u\leq\ell$ form an alternative set of generators over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ for
$\mathcal{M}_{s,\ell}(D,G)$. Likewise the elements in the set
$\\{y_{i}\tilde{B}_{v}^{(u)}|i=0,\dots,\mu-1,u=0,\dots,\ell,\ v=1,2\\}$
generate $\mathcal{M}_{s,\ell}(D,G)$ as an $\mathbb{F}_{q}[x]$-module. If
$s<\ell$, these alternative generators can be computed using fewer operations
and are therefore in general preferable.

######  Remark 4.8.

The $\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$-module
$\mathcal{M}_{s,\ell}(D,G)$ is an example of a torsion free, finitely
generated module of rank $\ell+1$. Though we will not need this in the
following, it interesting to note that any torsion free, finitely generated
module $\mathcal{M}$ of rank $r$ over a Dedekind domain
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, is isomorphic
to a direct product of $r$ fractional ideals of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, say
$\mathcal{M}\cong I_{1}\oplus\cdots\oplus I_{r}$. Moreover, the product
$I=I_{1}\cdots I_{r}$ of these fractional ideals modulo principal fractional
ideals only depends on the isomorphism class of $\mathcal{M}$. Therefore the
element of the ideal class group of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ corresponding
to $I$ is called the Steinitz invariant of $\mathcal{M}$. See [11, Section
II.4] for more details. Theorem 4.4 can be reformulated as
$\mathcal{M}_{s,\ell}(D,G)\cong\bigoplus_{u=0}^{\ell}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$
and in particular the Steinitz invariant of $\mathcal{M}_{s,\ell}(D,G)$ is the
element in the ideal class group of
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ corresponding
to

$\prod_{u=0}^{\ell}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(\sum_{u=0}^{\ell}G_{u})=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-\binom{\ell+1}{2}G-\binom{s+1}{2}D).$

Returning to decoding, given a received word $\bm{r}$, code
$\mathcal{C}_{\mathcal{L}}(D,G)$, and parameters $s,\ell$, the main steps in
our algorithmic approach to Guruswami-Sudan list decoding are the following.

  1. 1.

Compute a generating set over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ of
$\mathcal{M}_{s,\ell}(D,G)$. We will do this in Subsection 5.3

  2. 2.

Compute a generating set over $\mathbb{F}_{q}[x]$ of
$\mathcal{M}_{s,\ell}(D,G)$. We will address this in Subsection 5.4

  3. 3.

Using fast row reduction over $\mathbb{F}_{q}[x]$, find a nonzero
$Q\in\mathcal{M}_{s,\ell}(D,G)$ satisfying $\delta_{G}(Q)<s(n-\tau)$. See
Subsection 5.5

  4. 4.

Find the roots of $Q$ in $\mathcal{L}(G)$. See Subsection 5.6

As we will see, the main result of this paper is that all these steps can be
done in complexity $\tilde{\mathcal{O}}(\mu^{\omega-1}\ell^{\omega+1}(n+g))$
and with a slight variation even in
$\tilde{\mathcal{O}}(\mu^{\omega-1}s\ell^{\omega}(n+g))$.

To simplify the description of the algorithms in the next sections, it will be
convenient to assume that apart from $P_{\infty}$, the function field $F$
contains an additional $Z:=\deg G+\max\\{(\ell+1)\deg G+4g+(s+1)n,\deg
G+(\ell+3)(2g-1)+(s+1)n+2+\mu\\}$ rational places. Even though this will not
be the case in general, the same trick as at the end of Section 2, will allow
us to assume this. More precisely, the function field $F\mathbb{F}_{q^{e}}$
with $e=\lceil 2\log_{q}(\max\\{Z,2g+1\\})\rceil$ will contain at least $1+Z$
rational places by Lemma 2.3. Since using equation (2.1),
$e\in\mathcal{O}(\log_{q}(\ell(n+g)))$, this does not interfere with our
target complexity and hence does not result in any loss of generality. We will
suppress the exponent $e$ from the notation and will from now on write
$\mathbb{F}_{q}$ for the finite field we work over, but assume that $F$
contains all the rational places that we need to run the algorithms we
describe in the next section (specifically: Algorithm 3 and Algorithm 5).

##  5 Algorithms

In this section, we present the algorithms that we will use to execute the
Guruswami-Sudan list decoder. We start with discussing multi-point evaluation
and interpolation algorithms that will form the backbone of the algorithms
discussed later in the section.

###  5.1 Multi-Point Evaluation

When defining $\mathcal{C}_{\mathcal{L}}(D,G)$, we used the evaluation map
$\operatorname{ev}_{D}$. We will later need to be able to compute
$\operatorname{ev}_{D}(f)$ fast, meaning we want to be able to evaluate the
function $f\in\mathcal{L}(G)$ in the multiple points $P_{1},\dots,P_{n}$ fast.
As a matter of fact, since we will need a slightly more general setting later
on, we phrase the results in this and the next subsection in terms of a very
similar evaluation map, but avoid to use the divisors $D$ and $G$.

######  Lemma 5.1.

Let $A$ be a divisor and $E=E_{1}+\cdots+E_{N}$ for distinct rational places
$E_{1},\dots,E_{N}$ of $F$ such that
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$. Further denote
by $\operatorname{ev}_{E}:\mathcal{L}(A)\to\mathbb{F}_{q}^{N}$ the evaluation
map defined by $\operatorname{ev}_{E}(a)=(a(E_{1}),\dots,a(E_{N})).$ Then

  1. 1.

$\operatorname{ev}_{E}$ is injective when $\deg A<\deg E$,

  2. 2.

$\operatorname{ev}_{E}$ is surjective when $\deg A\geq\deg E+2g-1$.

###### Proof.

For the first item, simply observe that the dimension of the kernel of
$\operatorname{ev}_{E}$ is $l(A-E)=0$, since $\deg(A-E)<0$.

For the second item, observe that the dimension of the image of
$\operatorname{ev}_{E}$ is

$l(A)-l(A-E)=\deg A-g+1-(\deg A-\deg E-g+1)=\deg E\ ,$

since $\deg(A)\geq 2g-1$ and $\deg(A-E)\geq 2g-1$, see [43, Theorem 1.5.17]. ∎

Now we state Algorithm 1, which computes $\operatorname{ev}_{E}(a)$ using the
representation of function field elements as introduced in Section 3.

Algorithm 1 $\mathsf{Evaluate}(a,E,A,\bm{x},\bm{y})$

1:Input:  • Divisors $A$ and $E=E_{1}+\cdots+E_{N}$, where
$E_{1},\dots,E_{N}\in\mathbb{P}_{F}\setminus\\{P_{\infty}\\}$ are distinct
rational places and
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$, • a function
$a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
where $a_{i}\in\mathbb{F}_{q}[x]$, • evaluations
$\bm{x}=(x_{j})_{j=1,\dots,N}$, where $x_{j}=x(E_{j})\in\mathbb{F}_{q}$, •
evaluations $\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$.

2:Output:  • Evaluations $\operatorname{ev}_{E}(a)\in\mathbb{F}_{q}^{N}$.

3:for $i=0,\dots,\mu-1$ do

4:
$(a_{i,1},\dots,a_{i,N})\in\mathbb{F}_{q}^{N}\leftarrow(a_{i}(x_{1}),\dots,a_{i}(x_{N}))$
$\triangleright$ Univariate MPE

5:return
$\sum_{i=0}^{\mu-1}(a_{i,1}y_{i,1},\dots,a_{i,N}y_{i,N})\in\mathbb{F}_{q}^{N}$

######  Lemma 5.2.

Algorithm 1 is correct and costs $\tilde{\mathcal{O}}(\mu N+\delta_{A}(a)+\deg
A)$ operations in $\mathbb{F}_{q}$.

###### Proof.

Correctness simply follows from the fact that for $j=1,\dots,N$

$\sum_{i=0}^{\mu-1}a_{i,j}y_{i,j}=\sum_{i=0}^{\mu-1}a_{i}(x(E_{j}))y^{(A)}_{i}(E_{j})=\sum_{i=0}^{\mu-1}(a_{i}y^{(A)}_{i})(E_{j})=a(E_{j})\
.$

For complexity, notice that the total cost of the for-loop on Line 1 amounts
to that of evaluating each of the univariate polynomials
$a_{0},\dots,a_{\mu-1}\in\mathbb{F}_{q}[x]$ on $N$ points. According to Lemma
3.4,

$\deg a_{i}\leq\frac{1}{\mu}(\delta_{A}(a)+\deg A)\quad\text{for
}i=0,\dots,\mu-1\ ,$

hence the total cost of the for-loop is bounded by

$\tilde{\mathcal{O}}(\mu(N+\max_{i}\deg
a_{i}))\subseteq\tilde{\mathcal{O}}(\mu N+\delta_{A}(a)+\deg A)\ .$

Line $3$ costs $\mathcal{O}(\mu N)$, which is subsumed by the cost of the for-
loop. ∎

###  5.2 Interpolation

In this subsection, we address the interpolation problem. We start with an
existence result.

######  Lemma 5.3.

Let $A$ be a divisor and $E=E_{1}+\cdots+E_{N}$ for distinct rational places
$E_{1},\dots,E_{N}$ of $F$ different from $P_{\infty}$ such that
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$. For any
$(w_{1},\dots,w_{N})\in\mathbb{F}_{q}^{N}$ there exists an
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ with

$\delta_{A}(a)\leq\deg E+2g-1-\deg A$

such that $a(E_{j})=w_{j}$ for $j=1,\dots,N$.

###### Proof.

Letting $A^{\prime}=(\deg E+2g-1-\deg A)P_{\infty}+A$ we get that $\deg
A^{\prime}\geq\deg E+2g-1$, which according to Lemma 5.1 implies that the
evaluation map
$\operatorname{ev}_{E}:\mathcal{L}(A^{\prime})\to\mathbb{F}_{q}^{N}$ is
surjective. ∎

######  Definition 5.4.

If $E=E_{1}+\cdots+E_{N}$, where $E_{1},\dots,E_{N}$ are distinct rational
places different from $P_{\infty}$, and $U_{1},\dots,U_{\mu}$ are effective
divisors satisfying

  1. 1.

$E=U_{1}+\dots+U_{\mu}$,

  2. 2.

$\operatorname{supp}U_{i}\cap\operatorname{supp}U_{j}=\emptyset$ when $i\neq
j$,

  3. 3.

$|\deg U_{i}-\deg U_{j}|\leq 1$ for all $i,j\in\\{1,\dots,\mu\\}$,

  4. 4.

for any $E_{j},E_{k}\in\operatorname{supp}U_{i}$ it holds that
$x(E_{j})=x(E_{k})\iff E_{j}=E_{k}$,

then we will say that $U_{1},\dots,U_{\mu}$ is an _$x$ -partition_ of $E$.

######  Lemma 5.5.

If $\mathcal{S}$ is a set of places such that $x(P)=x(P^{\prime})$ for all
$P,P^{\prime}\in\mathcal{S}$, then $|\mathcal{S}|\leq\mu$.

###### Proof.

If $\alpha=x(P)$ for every $P\in\mathcal{S}$, then it is easy to see that

$0\neq x-\alpha\in\mathcal{L}(\mu P_{\infty}-\sum_{P\in\mathcal{S}}P)\ .$

But if $\mu<|\mathcal{S}|$, then the above Riemann-Roch space has dimension
zero. ∎

######  Lemma 5.6.

There exists an $x$-partition of any divisor of the form
$E=E_{1}+\cdots+E_{N}$, where $E_{1},\dots,E_{N}$ are distinct rational places
different from $P_{\infty}$.

###### Proof.

We use induction on $N$. The base case $N=0$ is trivial, so let us consider
the induction step. Suppose $U_{1},\dots,U_{\mu}$ is an $x$-partition of
$E-E_{N}$, and let $a,b$ be such that $U_{a}$ and $U_{b}$ have minimal degree
among the elements of

$\\{U_{1},\dots,U_{\mu}\\}\\{U_{i}\mid x(E_{j})\neq x(E_{N})\text{ for all
}E_{j}\in\operatorname{supp}U_{i},i=1,\dots,\mu\\}$

respectively ($b$ exists due to Lemma 5.5). If $\deg U_{a}=\deg U_{b}$, then
an $x$-partition of $E$ can be obtained by replacing $U_{b}$ with
$U_{b}+E_{N}$. If on the other hand $\deg U_{a}<\deg U_{b}$, then $U_{a}$
contains a place $\hat{E}_{a}$ with $x(\hat{E}_{a})=x(E_{N})$ and $U_{b}$
contains a place $\hat{E}_{b}$ such that $x(\hat{E}_{b})\neq x(E_{j})$ for all
$E_{j}\in U_{a}$. But then an $x$-partition of $E$ can be obtained by
replacing $U_{a}$ with $U_{a}-\hat{E}_{a}+\hat{E}_{b}+E_{N}$ and $U_{b}$ with
$U_{b}-\hat{E}_{b}+\hat{E}_{a}$. ∎

######  Definition 5.7.

For any polynomial matrix $\bm{A}\in\mathbb{F}_{q}[x]^{\phi\times\theta}$ with
columns $\bm{A}_{1},\dots,\bm{A}_{\theta}$ and any polynomial vector
$\bm{u}=(u_{1},\dots,u_{\theta})\in\mathbb{F}_{q}[x]^{\theta}$ define the
$\mathbb{F}_{q}[x]$-module

$\mathcal{H}_{\bm{u}}(\bm{A})=\\{\bm{v}\in\mathbb{F}_{q}[x]^{\phi}\mid\bm{v}\cdot\bm{A}_{k}\equiv
0\pmod{u_{k}}\quad\text{for }k=1,\dots,\theta\\}\ .$

The following is a direct adaptation of Theorem 1.7 from [35]. We also refer
to [35] for the definition of the Popov form and the $(-\bm{d})$-Popov form of
a matrix. Note that if $u_{1}\cdots u_{\theta}\neq 0,$ the rank of
$\mathcal{H}_{\bm{u}}(\bm{A})$ is $\phi$, as $u_{1}\cdots
u_{\theta}\mathbb{F}_{q}[x]^{\phi}\subseteq\mathcal{H}_{\bm{u}}(\bm{A})\subseteq\mathbb{F}_{q}[x]^{\phi}.$
Note that the problem of computing the shifted Popov basis of
$\mathcal{H}_{\bm{u}}(\bm{A})$ has been studied extensively in the literature.
Earlier references than [35] are for example [21, 20]

######  Theorem 5.8 ([35, Theorem 1.7]).

Assume $\phi,\theta\in\mathbb{Z}_{\geq 1}$ are integers such that
$\phi\geq\theta$. There exists an algorithm which for any
$\bm{A}\in\mathbb{F}_{q}[x]^{\phi\times\theta}$,
$\bm{u}\in(\mathbb{F}_{q}[x]\setminus\\{0\\})^{\theta}$ and
$\bm{d}=(d_{1},\dots,d_{\phi})\in\mathbb{Z}_{\geq 0}^{\phi}$ can compute a
matrix $\bm{V}\in\mathbb{F}_{q}[x]^{\phi\times\phi}$ in $(-\bm{d})$-Popov
form, whose rows form an $\mathbb{F}_{q}[x]$-basis of
$\mathcal{H}_{\bm{u}}(\bm{A})$. Furthermore, if there exists a vector
$\bm{v}=(v_{1},\dots,v_{\phi})\in\mathcal{H}_{\bm{u}}(\bm{A})$ satisfying the
degree constraints $\deg v_{t}<d_{t}$ for $t=1,\dots,\phi$, then at least one
row of $\bm{V}$ will also satisfy these constraints. The complexity of such an
algorithm can be taken to be $\tilde{\mathcal{O}}(\phi^{\omega-1}\theta d)$
operations in $\mathbb{F}_{q}$, where $d=\max_{t}d_{t}+\max_{k}\deg u_{k}$.

For our purposes, we will sometimes need to allow non-integer shifts
$d_{1},\dots,d_{\phi}$. Non-integer, rational shifts were handled in [32]
essentially by permuting columns in a very specific way:

######  Theorem 5.9 (Reformulation of Corollary 12 in [32]).

Let $\bm{V}\in\mathbb{F}_{q}[x]^{\gamma\times\phi}$ and
$\bm{d}=(d_{1}/\mu,\dots,d_{\phi}/\mu)\in(\frac{1}{\mu}\mathbb{Z})^{\phi}\subset(\frac{1}{\mu}\mathbb{Z})^{\phi}$,
where $d_{1},\dots,d_{\phi}\in\mathbb{Z}$. If $\pi$ is the permutation on
$\\{1,\dots,\phi\\}$ defined by

$\displaystyle\pi(i)>\pi(j)\iff\begin{array}[]{c}(d_{i}\operatorname{\
rem\,}\mu)>(d_{j}\operatorname{\ rem\,}\mu)\\\ \text{or}\\\
(d_{i}\operatorname{\ rem\,}\mu)=(d_{j}\operatorname{\
rem\,}\mu)i>j\end{array}\ ,$

and $\Psi:\mathbb{F}_{q}[x]^{\phi}\to\mathbb{F}_{q}[x]^{\phi}$ is the map

$(v_{1},\dots,v_{\phi})\mapsto(x^{\lfloor
d_{\pi(1)}/\mu\rfloor}v_{\pi(1)},\dots,x^{\lfloor
d_{\pi(\phi)}/\mu\rfloor}v_{\pi(\phi)})\ ,$

then $\bm{V}$ is in $\bm{d}$-Popov form if and only if $\Psi(\bm{V})$ is in
Popov form, where $\Psi(\bm{V})\in\mathbb{F}_{q}[x]^{\gamma\times\phi}$ is the
matrix created by applying $\Psi$ to each row of $\bm{V}$.

Using the permutation defined in Theorem 5.9 in combination with Theorem 5.8,
we obtain the following:

######  Corollary 5.10.

In the context of Theorem 5.8 we can allow
$\bm{d}\in(\frac{1}{\mu}\mathbb{Z})^{\phi}$ and find the desired matrix
$\bm{V}\in\mathbb{F}_{q}[x]^{\phi\times\phi}$ in complexity
$\tilde{\mathcal{O}}(\phi^{\omega-1}\theta d)$ operations in $\mathbb{F}_{q}$,
where $d=\max_{t}|d_{t}|+\max_{k}\deg u_{k}$.

###### Proof.

Write $\bm{d}=(\tilde{d}_{1}/\mu,\dots,\tilde{d}_{\phi}/\mu)$ with
$\tilde{d}_{t}\in\mathbb{Z}$ and notice that Theorem 5.9 implies that
$\bm{V}\in\mathbb{F}_{q}[x]^{\phi\times\phi}$ is in $(-\bm{d})$-Popov form if
and only if $\tilde{\bm{V}}\in\mathbb{F}_{q}[x]^{\phi\times\phi}$ is in
$(-\tilde{\bm{d}})$-Popov form, where

$\tilde{\bm{d}}=(\lfloor\tilde{d}_{\pi(1)}/\mu\rfloor,\dots,\lfloor\tilde{d}_{\pi(\phi)}/\mu\rfloor)\in\mathbb{Z}^{\phi}\
,$

and $\tilde{\bm{V}}$ is matrix obtained from $\bm{V}$ by permuting its columns
using $\pi$ from Theorem 5.9. By Theorem 5.8, for any matrix
$\bm{A}\in\mathbb{F}_{q}[x]^{\phi\times\theta}$, we can compute the basis
$\tilde{\bm{V}}\in\mathbb{F}_{q}[x]^{\phi\times\phi}$ of
$\mathcal{H}_{\bm{u}}(\tilde{\bm{A}})$ in $(-\tilde{\bm{d}})$-Popov form,
where $\tilde{\bm{A}}\in\mathbb{F}_{q}[x]^{\phi\times\theta}$ is obtained by
permuting the rows of $\bm{A}$ by $\pi$, as long as the entries of
$\tilde{\bm{d}}$ are non-negative. By simply adding the constant
$\max_{t}\lceil|\tilde{d}_{t}|/\mu\rceil$ to all coordinates of
$\tilde{\bm{d}}$, we can ensure that this is true without breaking the target
complexity. Finally, it is trivial to obtain $\bm{V}$ from $\tilde{\bm{V}}$ by
applying $\pi^{-1}$ to its columns. ∎

With these algorithmic aspects in place, we turn our attention again to the
interpolation problem. We start with a lemma, which will give rise to our
interpolation algorithm directly.

######  Lemma 5.11.

Let $A$ be a divisor and $E=E_{1}+\cdots+E_{N}$ for distinct rational places
$E_{1},\dots,E_{N}$ of $F$ different from $P_{\infty}$ such that
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$. Let
$(w_{1},\dots,w_{N})\in\mathbb{F}_{q}^{N}$ as well as an $x$-partition
$U_{1},\dots,U_{\mu}$ of $E$ be given.

Suppose that $\bm{T}=[T_{k}]\in\mathbb{F}_{q}[x]^{1\times\mu}$ and
$\bm{S}=[S_{i,k}]\in\mathbb{F}_{q}[x]^{\mu\times\mu}$ are such that

$T_{k}(x(E_{j}))=-w_{j}\text{ for all }E_{j}\in\operatorname{supp}(U_{k})$

and

$S_{i,k}(x(E_{j}))=y^{(A)}_{i}(E_{j})\text{ for all
}E_{j}\in\operatorname{supp}(U_{k}).$

If $\bm{u}=(u_{1},\dots,u_{\mu})\in\mathbb{F}_{q}[x]^{\mu}$, where
$u_{k}=\prod_{E_{j}\in\operatorname{supp}(U_{k})}(x-x(E_{j}))$, and
$\bm{d}=(d_{0},\dots,d_{\mu-1},0)\in(\frac{1}{\mu}\mathbb{Z})^{\mu+1}$, where

$d_{i}=\frac{1}{\mu}(\deg E+2g-\deg A-\delta_{A}(y^{(A)}_{i}))\quad\text{for
}i=0,\dots,\mu-1\ ,$

then in the $(-\bm{d})$-Popov basis of $\mathcal{H}_{\bm{u}}(\bm{A})$, where

$\bm{A}=\left[\begin{array}[]{c}\bm{S}\\\
\hline\cr\bm{T}\end{array}\right]\in\mathbb{F}_{q}^{(\mu+1)\times\mu}\ ,$

there exists a vector
$\bm{a}=(a_{0},\dots,a_{\mu-1},1)\in\mathbb{F}_{q}[x]^{\mu+1}$ with $\deg
a_{i}<d_{i}$ for $i=0,\dots,\mu-1$. Moreover, if

$a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}\ ,$

then $\delta_{A}(a)\leq\deg E+2g-1-\deg A$ and $a(E_{j})=w_{j}$ for
$j=1,\dots,N$.

###### Proof.

Observe that according to Lemma 5.3 there exists a
$b\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ with

$\delta_{A}(b)\leq\deg E+2g-1-\deg A$

such that $b(E_{j})=w_{j}$ for $j=1,\dots,N$. If we write
$b=\sum_{i=0}^{\mu-1}b_{i}y^{(A)}_{i}$, where $b_{i}\in\mathbb{F}_{q}[x]$,
then it follows from Lemma 3.4 that

$\deg
b_{i}\leq\frac{1}{\mu}(\delta_{A}(a)-\delta_{A}(y^{(A)}_{i}))=\frac{1}{\mu}(\deg
E+2g-1-\deg A-\delta_{A}(y^{(A)}_{i}))<d_{i}\ .$

We claim that
$\bm{b}:=(b_{0},\dots,b_{\mu-1},1)\in\mathcal{H}_{\bm{u}}(\bm{A})$. To see
this let $c_{k}=\sum_{i=0}^{\mu-1}b_{i}S_{i,k}+T_{k}\in\mathbb{F}_{q}[x]$ for
$k=1,\dots,\mu$ and observe that for any $E_{j}\in U_{k}$ it holds that

$c_{k}(x(E_{j}))=\sum_{i=0}^{\mu-1}b_{i}(x(E_{j}))y^{(A)}_{i}(E_{j})-w_{j}=b(E_{j})-w_{j}=0\
,$

which implies that

$\bm{b}\bm{A}_{k}=c_{k}\equiv 0\pmod{u_{k}}\ ,$

where $\bm{A}_{k}\in\mathbb{F}_{q}[x]^{(\mu+1)\times 1}$ denotes the $k$-th
column of $\bm{A}$. But then indeed $\bm{b}\in\mathcal{H}_{\bm{u}}(\bm{A})$ by
definition.

Note that in the $(-\bm{d})$-degree, the leading position of $\bm{b}$ is the
last position. The $(-\bm{d})$-Popov basis of $\mathcal{H}_{\bm{u}}(\bm{A})$
will contain a vector $\bm{a}=(a_{0},\dots,a_{\mu-1},a_{\mu})$ whose leading
coordinate is the last position as well, and in particular $a_{\mu}\neq 0$.
Since $\bm{a}$ has minimal $(-\bm{d})$-degree among all vectors in
$\mathcal{H}_{\bm{u}}(\bm{A})$ whose leading position is the last position, we
conclude that $\bm{a}$ satisfies the same degree constraints as $\bm{b}$.

To conclude the proof observe that

$\displaystyle\delta_{A}(a)$
$\displaystyle=\max_{i}(\delta(a_{i})+\delta_{A}(y^{(A)}_{i}))$
$\displaystyle=\max_{i}(\mu\deg a_{i}+\delta_{A}(y^{(A)}_{i}))$
$\displaystyle<\max_{i}(\mu d_{i}+\delta_{A}(y^{(A)}_{i}))$
$\displaystyle=\deg E+2g-\deg A\ ,$

and that for any $E_{j}\in U_{k}$, where $k=1,\dots,\mu$, it holds that

$\displaystyle a(E_{j})-w_{j}$
$\displaystyle=\sum_{i=0}^{\mu-1}a_{i}(x(E_{j}))y^{(A)}_{i}(E_{j})-w_{j}$
$\displaystyle=\sum_{i=0}^{\mu-1}a_{i}(x(E_{j}))S_{i,k}(x(E_{j}))+T_{k}(x(E_{j}))$
$\displaystyle=(\bm{a}\bm{A}_{k})(x(E_{j}))=0\ ,$

since $\bm{a}\in\mathcal{H}_{\bm{u}}(\bm{A})$. Consequently, $a(E_{j})=w_{j}$
for $j=1,\dots,N$. ∎

Algorithm 2 $\mathsf{Interpolate}(\bm{w},E,A,\bm{x},\bm{y})$

1:Input:  • Divisors $A$ and $E=E_{1}+\cdots+E_{N}$, where
$E_{1},\dots,E_{N}\in\mathbb{P}_{F}\setminus\\{P_{\infty}\\}$ are distinct
rational places and
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$, • interpolation
values $\bm{w}=(w_{1},\dots,w_{N})\in\mathbb{F}_{q}^{N}$, • evaluations
$\bm{x}=(x_{j})_{j=1,\dots,N}$, where $x_{j}=x(E_{j})\in\mathbb{F}_{q}$, •
evaluations $\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$.

2:Output:  •
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ such
that $\delta_{A}(a)\leq\deg E+2g-1-\deg A$ and $a(E_{j})=w_{j}$ for
$j=1,\dots,N$

3:$U_{1},\dots,U_{\mu}\leftarrow$ an $x$-partition of $E$

4:$\bm{S}=[S_{i,k}]\in\mathbb{F}_{q}[x]^{\mu\times\mu}\leftarrow$ matrix with
$S_{i,k}(x_{j})=y_{i,j}$ for all $E_{j}\in U_{k}$

5:$\bm{T}=[T_{k}]\in\mathbb{F}_{q}[x]^{\mu}\leftarrow$ row vector with
$T_{k}(x_{j})=-w_{j}$ for all $E_{j}\in U_{k}$

6:$\bm{u}=(u_{1},\dots,u_{\mu})\in\mathbb{F}_{q}[x]^{\mu}\leftarrow$ vector
with $u_{k}=\prod_{E_{j}\in U_{k}}(x-x_{j})$

7:$\bm{d}=(d_{0},\dots,d_{\mu-1},1)\in(\frac{1}{\mu}\mathbb{Z})^{\mu+1}\leftarrow$
vector with $d_{i}=\frac{1}{\mu}(\deg E+2g-\deg A-\delta_{A}(y^{(A)}_{i}))$

8:$\bm{P}\in\mathbb{F}_{q}[x]^{(\mu+1)\times(\mu+1)}\leftarrow$
$(-\bm{d})$-Popov basis matrix of $\mathcal{H}_{\bm{u}}(\bm{A})$, where
$\bm{A}=\left[\begin{array}[]{c}\bm{S}\\\
\hline\cr\bm{T}\end{array}\right]\in\mathbb{F}_{q}^{(\mu+1)\times\mu}$

9:$\bm{a}=(a_{0},\dots,a_{\mu-1},1)\in\mathbb{F}_{q}[x]^{\mu+1}\leftarrow$ a
row of $\bm{P}$ having $1$ as its last entry and satisfying $\deg a_{i}<d_{i}$
for $i=0,\dots,\mu-1$

10:return $a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}$

######  Proposition 5.12.

Algorithm 2 is correct and costs $\tilde{\mathcal{O}}(\mu^{\omega-1}(N+g))$
operations in $\mathbb{F}_{q}$.

###### Proof.

Correctness is given by Lemma 5.11. For complexity observe that $\deg
u_{k}=|U_{k}|\leq\lceil N/\mu\rceil$ for all $k$, while for all $i,k$, we can
choose $S_{i,k},T_{k}$ such that

$\deg S_{i,k},\deg T_{k}<\lceil N/\mu\rceil\ .$

Step 2 costs $\tilde{\mathcal{O}}(\mu^{2}N/\mu)=\tilde{\mathcal{O}}(\mu N)$.
Step 3 costs $\tilde{\mathcal{O}}(\mu N/\mu)=\tilde{\mathcal{O}}(N)$ using
fast univariate interpolation [45, Corollary 10.12], and Step 4 can be
executed within the same cost bound using a product tree [45, Lemma 10.4]. The
computational bottleneck lies in step 6, which according to Corollary 5.10
costs

$\tilde{\mathcal{O}}(\mu^{\omega-1}\mu(\max_{i}d_{i}+\max_{k}\deg
u_{k}))\subseteq\tilde{\mathcal{O}}(\mu^{\omega}(\frac{\deg
E+2g}{\mu}+\frac{N}{\mu}))=\tilde{\mathcal{O}}(\mu^{\omega-1}(N+g))\ .$

Here we used that $d_{i}\leq(\deg E+2g)/\mu$, since by Lemma 3.3, $\deg
A+\delta_{A}(y^{(A)}_{i})\geq 0.$ ∎

The output $a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}$ of
$\mathsf{Interpolate}(\bm{w},E,A,\bm{x},\bm{y})$ satisfies
$\delta_{A}(a)\leq\deg E+2g-1-\deg A$ as shown in Lemma 5.11. In general this
is the best one can expect, but in specific cases the existence of an
interpolation function
$b\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ with
$\delta_{A}(b)<\Delta<\deg E+2g-\deg A$ may be known to exist. The following
lemma clarifies a property of the output of Algorithm 2.

######  Lemma 5.13.

In the context of Algorithm 2, the output
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$
satisfies $\delta_{A}(a)\leq\delta_{A}(b)$ for all functions
$b\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ with
$b(E_{j})=w_{j}$ for $j=1,\dots,N$.

###### Proof.

Consider the map $\varphi$ which sends any function
$b=\sum_{i=0}^{\mu-1}b_{i}y_{i}^{(A)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$
to the vector $(b_{0},\dots,b_{\mu-1})\in\mathbb{F}_{q}[x]^{\mu}$, and observe
that if $b(E_{j})=w_{j}$ for all $j$, then $\varphi(a-b)$ is in the row space
of the matrix $\tilde{\bm{P}}\in\mathbb{F}_{q}[x]^{\mu\times\mu}$ obtained
from the first $\mu$ rows and columns of $\bm{P}$. It is clear that
$\tilde{\bm{P}}$ is in $(-\tilde{\bm{d}})$-Popov form, where
$\tilde{\bm{d}}=(d_{0},\dots,d_{\mu-1})$, and that each entry in $\varphi(a)$
has degree strictly smaller than the maximal degree of the corresponding
column in $\tilde{\bm{P}}$: otherwise $\bm{P}$ would not be in
$(-\bm{d})$-Popov form. But if each entry of $\phi(b)$ has degree no greater
than the corresponding entry in $\phi(a)$, then it follows from Proposition
2.8 that $\varphi(a-b)=0$, implying that $a=b$ since $\varphi(a-b)$ is in the
row space of $\tilde{P}$ (see also [22, Theorem 6.3-15] or [44, Lemma 1.24]).
∎

###  5.3 Computing a generating set over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ of
$\mathcal{M}_{s,\ell}(D,G)$

We now return to the Guruswami-Sudan decoding of the code
$\mathcal{C}_{\mathcal{L}}(D,G)$. In this subsection we use the symbolic
expressions from Corollary 4.5 to compute a generating set over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ of
$\mathcal{M}_{s,\ell}(D,G)$. We start with a lemma.

######  Lemma 5.14.

Let $a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ and
$b\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(B)$, where
$A$ and $B$ are divisors, and let $E=E_{1}+\cdots+E_{N}$, where
$E_{1},\dots,E_{N}$ are distinct rational places different from $P_{\infty}$
and not contained in $\operatorname{supp}(A)\cup\operatorname{supp}(B)$. If
$c\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A+B)$
satisfies

  1. 1.

$\delta_{A+B}(c)<N-\deg(A+B)$ and

  2. 2.

$c(E_{j})=a(E_{j})b(E_{j})=(ab)(E_{j})$ for $j=1,\dots,N$,

then $c=ab$.

###### Proof.

Note that $c\in\mathcal{L}(C)$, where $C=\delta_{A+B}(c)P_{\infty}+A+B$. The
second condition simply states that
$\operatorname{ev}_{E}(c)=\operatorname{ev}_{E}(ab)$, but since $\deg C<\deg
E$, it follows from Lemma 5.1 that
$\operatorname{ev}_{E}:\mathcal{L}(C)\to\mathbb{F}_{q}^{N}$ is injective.
Consequently, $c=ab$. ∎

Using Algorithm 1 and Algorithm 2, this lemma allows us to perform efficient
multiplication and hence to compute a generating set over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ of
$\mathcal{M}_{s,\ell}(D,G)$ as in Algorithm 3.

Algorithm 3
$\mathsf{Generators}_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}(\bm{r},D,G,E,\bm{x},\bm{y},\bm{g})$

1:Input:  • Received word $\bm{r}\in\mathbb{F}_{q}^{n}$, • the code divisors
$D$ and $G$,  • a divisor $E=E_{1}+\cdots+E_{N}$, where $E_{1},\dots,E_{N}$
are distinct rational places of $F$, not in
$\\{P_{\infty}\\}\cup\operatorname{supp}G,$ such that $N\geq(\ell+1)\deg
G+4g+(s+1)n$, • evaluations $\bm{x}=(x_{j})_{j=1,\dots,N}$, where
$x_{j}=x(E_{j})\in\mathbb{F}_{q}$, • evaluations
$\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$, • evaluations
$\bm{g}=(g_{v,j}^{(u)})$, where $u=0,\dots,\ell$, $v=1,2$ and $j=1,\dots,N$
such that $g_{v,j}^{(u)}=g_{v}^{(u)}(E_{j})\in\mathbb{F}_{q}$ where $\langle
g_{1}^{(u)},g_{2}^{(u)}\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$,
and $\delta_{G_{u}}(g_{v}^{(u)})\leq 4g-1+(u+1)\deg(G)+(s+1)n$.

2:Output:  • $(B_{v}^{(u)})^{u=0,\dots,\ell}_{v=1,2}$ such that $\langle
B_{v}^{(u)}\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}=\mathcal{M}_{s,\ell}(D,G)$.

3:$R\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G)\leftarrow\mathsf{Interpolate}(\bm{r},D,G,\bm{x},\bm{y})$
$\triangleright$ Algorithm 2

4:$(\hat{r}_{1}^{(0)},\dots,\hat{r}_{N}^{(0)})\in\mathbb{F}_{q}^{N}\leftarrow(1,\dots,1)$

5:$(\hat{r}_{1}^{(1)},\dots,\hat{r}_{N}^{(1)})\in\mathbb{F}_{q}^{N}\leftarrow\mathsf{Evaluate}(-R,E,G,\bm{x},\bm{y})$
$\triangleright$ Algorithm 1

6:for $u=2,\dots,\ell$ do

7:
$(\hat{r}_{1}^{(u)},\dots,\hat{r}_{N}^{(u)})\in\mathbb{F}_{q}^{N}\leftarrow(\hat{r}_{1}^{(1)}\hat{r}_{1}^{(u-1)},\dots,\hat{r}_{N}^{(1)}\hat{r}_{N}^{(u-1)})$

8:for $u=0,\dots,\ell$, $r=0,\dots,u$ and $v=1,2$ do

9:
$\bm{c}_{r,v}^{(u)}\in\mathbb{F}_{q}^{N}\leftarrow(\hat{r}_{1}^{(u-r)}g_{v,1}^{(u)},\dots,\hat{r}_{N}^{(u-r)}g_{v,N}^{(u)})$

10:
$c_{r,v}^{(u)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-rG)\leftarrow\mathsf{Interpolate}(\bm{c}_{r,v}^{(u)},E,-rG,\bm{x},\bm{y})$

11:for $u=0,\dots,\ell$ and $v=1,2$ do

12:
$B_{v}^{(u)}\in\mathcal{M}_{s,\ell}(D,G)\leftarrow\sum_{r=0}^{u}\binom{u}{r}z^{r}c_{r,v}^{(u)}$

13:return $(B_{v}^{(u)})^{u=0,\dots,\ell}_{v=1,2}$

######  Proposition 5.15.

Algorithm 3 is correct and costs
$\tilde{\mathcal{O}}(\ell^{3}\mu^{\omega-1}(n+g))$.

###### Proof.

For correctness first observe that the postulated $g_{v}^{(u)}$ exist by
Corollary 4.5.

Note that $\delta_{G}(R)\leq n+2g-1-\deg G$. Using the given upper bound for
$\delta_{G_{u}}(g_{v}^{(u)})$, we obtain that

$\displaystyle\delta_{-rG}(R^{u-r}g_{v}^{(u)})$
$\displaystyle=\delta_{(u-r)G+G_{u}}(R^{u-r}g_{v}^{(u)})$
$\displaystyle\leq(u-r)(n+2g-1-\deg G)+4g-1+(u+1)\deg G+(s+1)n$
$\displaystyle=(r+1)\deg G+(u-r+2)(2g-1)+1+(s+1)n$ (5.1)
$\displaystyle=(r+1)(\deg G-2g+1)+(u+3)(2g-1)+1+(s+1)n$
$\displaystyle\leq(\ell+1)(\deg G-2g+1)+(\ell+3)(2g-1)+1+(s+1)n$
$\displaystyle=(\ell+1)\deg G+2(2g-1)+1+(s+1)n$ $\displaystyle<(\ell+1)\deg
G+4g+(s+1)n$

Lemma 5.13 then implies that
$\mathsf{Interpolate}(\bm{c}_{r,v}^{(u)},E,-rG,\bm{x},\bm{y})$ will output a
function
$c_{r,v}^{(u)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G)$
satisfying $\delta_{-rG}(c_{r,v}^{(u)})<(\ell+1)\deg G+4g+(s+1)n.$

To complete the correctness proof, we consider Lemma 5.14 for the divisors
$A=(u-r)G$, $B=-uG$ and the function $a=(-R)^{u-r}$, $b=g_{v}^{(u)}$, and
$c=c_{r,v}^{(u)}$. By construction, it is clear that for all
$E_{j}\in\operatorname{supp}E$ we have
$c_{r,v}^{(u)}(E_{j})=(-R)^{u-r}(E_{j})g_{v}^{(u)}(E_{j}).$ Moreover, $\deg
E\geq(\ell+1)\deg G+4g+(s+1)n$, whence $\delta_{-rG}(c_{r,v}^{(u)})<\deg
E\leq\deg E-\deg(-rG)$. Hence Lemma 5.14 implies
$c_{r,v}^{(u)}=(-R)^{u-r}g_{v}^{(u)}.$

The complexity of the algorithm is dominated by the for loop in Lines 6–8. The
$\mathcal{O}(\ell^{2})$ calls of the algorithm
$\mathsf{Interpolate}(\bm{c}_{r,v}^{(u)},E,-rG,\bm{x},\bm{y})$ cost
$\ell^{2}\tilde{\mathcal{O}}(\ell\mu^{\omega-1}(n+g))$ operations. Hence the
total complexity is $\tilde{\mathcal{O}}(\ell^{3}\mu^{\omega-1}(n+g)).$ ∎

######  Remark 5.16.

The generating set consisting of $\tilde{B}_{v}^{(u)}$ as described in Remark
4.7, can be computed slightly faster. Indeed, since in these generators, the
needed powers $(-R)^{u}$ have the range $u=0,\dots,s$, the for loop in Lines
6–9 has $\mathcal{O}(s\ell)$ calls of the algorithm
$\mathsf{Interpolate}(\bm{c}_{r,v}^{(u)},E,-rG,\bm{x},\bm{y})$. Hence to
compute the $\tilde{B}_{v}^{(u)}$ costs
$\tilde{\mathcal{O}}(s\ell^{2}\mu^{\omega-1}(n+g)).$

###  5.4 Computing a generating set over $\mathbb{F}_{q}[x]$ of
$\mathcal{M}_{s,\ell}(D,G)$.

In the previous subsection, we saw how to efficiently compute the generating
set $\\{B_{v}^{(u)}\\}$ of $\mathcal{M}_{s,\ell}(D,G)$ over
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$, as in
Corollary 4.5. The next logical step is to compute the set of products
$\\{y_{i}B_{v}^{(u)}\\}$, which generates $\mathcal{M}_{s,\ell}(D,G)$ over
$\mathbb{F}_{q}[x]$ according to Corollary 4.6. Consequently, we now consider
the following problem: given a function
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$ for
some divisor $A$, compute
$y_{0}a,\dots,y_{\mu-1}a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.
Computing the $y_{i}a$ individually using Algorithm 3 would be too slow for
our purposes. Indeed, obtaining each $y_{i}B_{v}^{(u)}$ this way would cost
$\tilde{\mathcal{O}}(\ell^{2}\mu^{\omega-1}(n+g))$ operations, and we need to
compute $2\mu(\ell+1)$ such terms in total. Therefore, we introduce in this
subsection a more efficient approach, which will allow us to compute
$y_{0}a,\dots,y_{\mu-1}a$ simultaneously.

######  Definition 5.17.

For any $H(z)\in F[z]$ and any rational place $P\in\mathbb{P}_{F}$ that is not
a pole of any of the coefficients of $H(z)$, and $\alpha\in\mathbb{F}_{q}$ we
denote by $H(P,\alpha)$ the evaluation of $H(\alpha)\in F$ at $P$.

######  Definition 5.18.

Let $A$ be a divisor and $E=E_{1}+\cdots+E_{N}$ for distinct rational places
$E_{1},\dots,E_{N}$ of $F$ different from $P_{\infty}$ such that
$\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$. For
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$, we
define the $\mathbb{F}_{q}[x]$-module

$\mathcal{N}_{A,E}(a)=\\{H=H_{0}+H_{1}z\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\oplus
z\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}\mid
H(P,a(P))=0\text{ for all }P\in\operatorname{supp}(E)\\}\ .$

In the following lemmas, we use the same notation $A$, $E$ as in Definition
5.18.

######  Lemma 5.19.

Let $a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$. If
$H=H_{0}+zH_{1}\in\mathcal{N}_{A,E}(a)$ with

$\max\\{\delta_{A}(H_{0}),\delta(H_{1})+\delta_{A}(a)\\}<\deg E-\deg A\ ,$

then $H(a)=0$, i.e. $H\in\langle
z-a\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}$.

###### Proof.

Since $H\in\mathcal{N}_{A,E}(a)$, we have
$H(a)\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.
Hence by definition of $\delta_{A}$, we have
$H(a)\in\mathcal{L}(A+\delta_{A}(H(a))P_{\infty}).$ Since for all
$E_{j}\in\operatorname{supp}E$, we have $H(a)(E_{j})=0$ and
$\operatorname{supp}E\cap(\operatorname{supp}A\cup\\{P_{\infty}\\})=\emptyset$,
we may conclude that $H(a)\in\mathcal{L}(A+\delta_{A}(H(a))P_{\infty}-E).$
Moreover,

$\displaystyle\delta_{A}(H(a))\leq\max\\{\delta_{A}(H_{0}),\delta(H_{1})+\delta_{A}(a)\\}<\deg
E-\deg A\ ,$

which ensures that the aforementioned Riemann-Roch space is trivial. ∎

######  Lemma 5.20.

Let $a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.
Furthermore, let $U_{1},\dots,U_{\mu}$ be an $x$-partition of $E$, and let
$\bm{S}=[S_{i,k}],\bm{T}=[T_{i,k}]$ be matrices in
$\mathbb{F}_{q}[x]^{\mu\times\mu}$ such that

$\displaystyle
S_{i,k}(x(E_{j}))=y^{(A)}_{i}(E_{j})T_{i,k}(x(E_{j}))=a(E_{j})y_{i}(E_{j})\quad\text{for
}E_{j}\in U_{k}\ .$

If $\bm{u}=(u_{1},\dots,u_{\mu})\in\mathbb{F}_{q}[x]^{\mu}$, where
$u_{k}=\prod_{E_{j}\in\operatorname{supp}U_{k}}(x-x(E_{j}))$, then the map

$\psi:\sum_{i=0}^{\mu-1}(s_{i}y^{(A)}_{i}+t_{i}zy_{i})\mapsto(s_{0},\dots,s_{\mu-1},t_{0},\dots,t_{\mu-1})$

is an $\mathbb{F}_{q}[x]$-isomorphism between $\mathcal{N}_{A,E}(a)$ and
$\mathcal{H}_{\bm{u}}(\bm{A})$, where

$\bm{A}=\left[\begin{array}[]{c}\bm{S}\\\
\hline\cr\bm{T}\end{array}\right]\in\mathbb{F}_{q}^{2\mu\times\mu}\ .$

###### Proof.

Clearly $\psi$ is an $\mathbb{F}_{q}[x]$-isomorphism between
$\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\oplus
z\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ and
$\mathbb{F}_{q}[x]^{2\mu}$, therefore it suffices to show that for any
$H\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\oplus
z\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ it holds that
$H\in\mathcal{N}_{A,E}(a)$ if and only if
$\psi(H)\in\mathcal{H}_{\bm{q}}(\bm{A})$, i.e. that $H(E_{j},a(E_{j}))=0$ for
all $E_{j}\in\operatorname{supp}U_{k}$ and all $k=1,\dots,\mu$ if and only if
$\psi(H)\cdot\bm{A}_{k}\equiv 0\mod u_{k}$, for $k=1,\dots,\mu$, where
$\bm{A}_{k}$ denotes the $k$-th column of $\bm{A}$. But this is necessarily
true, since for every $E_{j}\in U_{k}$ the following identity holds, where
$\alpha=x(E_{j})$:

$\displaystyle H(E_{j},a(E_{j}))$
$\displaystyle=\sum_{i=0}^{\mu-1}\big{(}s_{i}(\alpha)y^{(A)}_{i}(E_{j})+a(E_{j})t_{i}(\alpha)y_{i}(E_{j})\big{)}$
$\displaystyle=\sum_{i=0}^{\mu-1}\big{(}s_{i}(\alpha)S_{i,k}(\alpha)+t_{i}(\alpha)T_{i,k}(\alpha)\big{)}=(\psi(H)\cdot\bm{A}_{k})(\alpha)\
.$

∎

######  Lemma 5.21.

In the context of Lemma 5.20, if $\bm{P}\in\mathbb{F}_{q}[x]^{2\mu\times
2\mu}$ is the $\bm{d}$-Popov basis of
$\mathcal{H}_{\bm{u}}(\bm{A})=\psi(\mathcal{N}_{A,E}(a))$, where $\deg E\geq
2g+\mu+\delta_{A}(a)+\deg A$ and

$\bm{d}=\frac{1}{\mu}(\delta_{A}(y^{(A)}_{0}),\dots,\delta_{A}(y^{(A)}_{\mu-1}),\delta(y_{0})+\delta_{A}(a),\dots,\delta(y_{\mu-1})+\delta_{A}(a))\in(\frac{1}{\mu}\mathbb{Z})^{2\mu}\
,$

then exactly $\mu$ rows of $\bm{P}$ have $\bm{d}$-degree less than
$\frac{1}{\mu}(\deg E-\deg A)$. Furthermore, if
$\tilde{\bm{P}}\in\mathbb{F}_{q}[x]^{\mu\times 2\mu}$ is the submatrix of
$\bm{P}$ consisting of these rows, then the $k$-th row of $\tilde{\bm{P}}$ is
$\psi(Y_{k})$ for $k=1,\dots,\mu$, where $Y_{k}=-ay_{k-1}+zy_{k-1}\in\langle
z-a\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}\subset\mathcal{N}_{A,E}(a)$.
Consequently, if $\tilde{\bm{P}}=[\tilde{\bm{P}}_{1}|\tilde{\bm{P}}_{2}]$,
where
$\tilde{\bm{P}}_{1},\tilde{\bm{P}}_{2}\in\mathbb{F}_{q}[x]^{\mu\times\mu}$,
then $ay_{k-1}=-\sum_{i=0}^{\mu-1}p_{k,i}y^{(A)}_{i}$, where
$(p_{k,0},\dots,p_{k,\mu-1})$ is the $k$-th row of $\tilde{\bm{P}}_{1}$.

###### Proof.

For any

$H=H_{0}+zH_{1}\in\mathcal{N}_{A,E}(a)\ ,$

where
$H_{0}=\sum_{i=0}^{\mu-1}s_{i}y^{(A)}_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$
and
$H_{1}=\sum_{i=0}^{\mu-1}t_{i}y_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$
with $s_{i},t_{i}\in\mathbb{F}_{q}[x]$, it holds that

$\displaystyle\deg_{\bm{d}}\psi(H)$ $\displaystyle=\max\\{\max_{i}(\deg
s_{i}+\frac{\delta_{A}(y^{(A)}_{i})}{\mu}),\max_{i}(\deg
t_{i}+\frac{\delta(y_{i})+\delta_{A}(a)}{\mu})\\}$
$\displaystyle=\frac{1}{\mu}\max\\{\delta_{A}(H_{0}),\delta(H_{1})+\delta_{A}(a)\\}\
.$

It then follows from Lemma 5.19 that

$\deg_{\bm{d}}\psi(H)<\frac{1}{\mu}(\deg E-\deg A)\implies H\in\langle
z-a\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}\ ,$

which means that at most $\mu$ rows of $\bm{P}$ can have $\bm{d}$-degree less
than $\frac{1}{\mu}(\deg E-\deg A)$, because $\langle
z-a\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}$
has rank $\mu$ as an $\mathbb{F}_{q}[x]$-module. On the other hand, since
$Y_{1},\dots,Y_{\mu}$ are linearly independent over $\mathbb{F}_{q}[x]$, and
since

$\deg_{\bm{d}}\psi(Y_{k})=\frac{1}{\mu}(\delta(y_{k-1})+\delta_{A}(a))<\frac{1}{\mu}(\delta_{A}(a)+2g+\mu)\leq\frac{1}{\mu}(\deg
E-\deg A)$

for $k=1,\dots,\mu$, where the strict inequality is due to Lemma 3.3, then at
least $\mu$ rows of $\bm{P}$ have $\bm{d}$-degree less than
$\frac{1}{\mu}(\deg E-\deg A)$, because $\bm{P}$ is $\bm{d}$-row reduced. This
proves the first claim of the lemma.

For the second claim it is sufficient to show that the $\bm{d}$-pivot index of
$\psi(Y_{k})$ is $\mu+k$, since this would imply that the matrix whose rows
are $\psi(Y_{k})$ is in $\bm{d}$-Popov form. To see this, write
$Y_{k}=-\sum_{i=0}^{\mu-1}w_{i}y^{(A)}_{i}+zy_{k-1}$, where
$w_{i}\in\mathbb{F}_{q}[x]$, and note that $Y_{k}(a)=0$ implies that

$\max_{i}\delta_{A}(w_{i}y^{(A)}_{i})=\delta_{A}(\sum_{i=0}^{\mu-1}w_{i}y^{(A)}_{i})=\delta_{A}(ay_{k-1})=\delta(y_{k-1})+\delta_{A}(a)\
.$

Consequently,
$\deg_{\bm{d}}\psi(Y_{k})=\frac{1}{\mu}(\delta(y_{k-1})+\delta_{A}(a))$, which
shows that $\mu+k$ is indeed the $\bm{d}$-pivot index of $\psi(Y_{k})$. ∎

Algorithm 4 $\mathsf{BasisProducts}_{\mathbb{F}_{q}[x]}(a,E,A,\bm{x},\bm{y})$

1:Input:  • A divisor $A$, • a function
$a\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$, • a
divisor $E=E_{1}+\cdots+E_{N}$, where
$E_{1},\dots,E_{N}\in\mathbb{P}_{F}\setminus\\{P_{\infty}\\}$ are distinct
rational places, $\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$
and $\deg E\geq\deg A+\delta_{A}(a)+2g+\mu$, • evaluations
$\bm{x}=(x_{j})_{j=1,\dots,N}$, where $x_{j}=x(E_{j})\in\mathbb{F}_{q}$, •
evaluations $\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$.

2:Output:  • Products $(ay_{0},\cdots,ay_{\mu-1})$, where each
$ay_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$.

3:if $a=0$ then

4: return $(0,\dots,0)$

5:$U_{1},\dots,U_{\mu}\leftarrow$ an $x$-partition of $E$

6:$\bm{S}=[S_{i,k}]\in\mathbb{F}_{q}[x]^{\mu\times\mu}\leftarrow$ matrix with
$S_{i,k}(x_{j})=y_{i,j}\text{ for }E_{j}\in U_{k}$

7:$\bm{T}=[T_{i,k}]\in\mathbb{F}_{q}[x]^{\mu\times\mu}\leftarrow$ matrix with
$T_{i,k}(x_{j})=a(E_{j})y_{i,j}\text{ for }E_{j}\in U_{k}$

8:$\bm{u}=(u_{1},\dots,u_{\mu})\in\mathbb{F}_{q}[x]^{\mu}\leftarrow$ vector
with $u_{k}=\prod_{E_{j}\in U_{k}}(x-x_{j})$

9:$\bm{d}\in(\frac{1}{\mu}\mathbb{Z})^{2\mu}\leftarrow\frac{1}{\mu}\big{(}\delta_{A}(y^{(A)}_{0}),\dots,\delta_{A}(y^{(A)}_{\mu-1}),\delta(y_{0})+\delta_{A}(a),\dots,\delta(y_{\mu-1})+\delta_{A}(a)\big{)}$

10:$\bm{P}\in\mathbb{F}_{q}[x]^{2\mu\times 2\mu}\leftarrow$ $\bm{d}$-Popov
basis of $\mathcal{H}_{\bm{u}}(\bm{A})$, where
$\bm{A}=\left[\begin{array}[]{c}\bm{S}\\\
\hline\cr\bm{T}\end{array}\right]\in\mathbb{F}_{q}[x]^{2\mu\times\mu}$

11:$[\tilde{\bm{P}}_{1}|\tilde{\bm{P}}_{2}]\in\mathbb{F}_{q}[x]^{\mu\times
2\mu}\leftarrow$ the submatrix of $\bm{P}$ consisting of all rows with

12:$\bm{d}$-degree less than $\frac{1}{\mu}(\deg E-\deg A)$, where
$\tilde{\bm{P}}_{1},\tilde{\bm{P}}_{2}\in\mathbb{F}_{q}[x]^{\mu\times\mu}$

13:for $k=1,\dots,\mu$ do

14: $(p_{k,0},\dots,p_{k,\mu-1})\in\mathbb{F}_{q}[x]^{\mu}\leftarrow$ $k$-th
row of $\bm{P}_{1}$

15:
$a_{k}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)\leftarrow-\sum_{i=0}^{\mu-1}p_{k,i}y^{(A)}_{i}$

16:return $(a_{1},\dots,a_{\mu})$

######  Lemma 5.22.

Algorithm 4 is correct and costs $\tilde{\mathcal{O}}(\mu^{\omega-1}(N+|\deg
A|))$ operations in $\mathbb{F}_{q}$.

###### Proof.

Correctness is given by Lemma 5.21. For complexity, simply note that the
computational bottleneck lies in Step 8, in which case $\delta_{A}(a)\geq-\deg
A$ because $a$ is nonzero and $a\in\mathcal{L}(\delta_{A}(a)P_{\infty}+A)$. By
assumption, we have that $N=\deg E\geq\deg A+\delta_{A}(a)+2g+\mu$, hence by
Lemma 3.3

$\displaystyle-\deg A$ $\displaystyle\leq\delta_{A}(y_{i}^{(A)})\leq 2g-1-\deg
A+\mu$ $\displaystyle<\deg E-2\deg A-\delta_{A}(a)\leq\deg E-\deg A\ .$

Since $\deg u_{k}\leq N/\mu$ for $k=1,\dots,\mu$, then the total complexity of
the algorithm is given by Corollary 5.10 as

$\tilde{\mathcal{O}}\big{(}\mu^{\omega-1}\max\\{|\deg E|,|\deg E-\deg A|,|\deg
A|\\}\big{)}\subseteq\tilde{\mathcal{O}}(\mu^{\omega-1}(N+|\deg A|))$

operations in $\mathbb{F}_{q}$. ∎

Now we are ready to state Algorithm 5, which computes a generating set over
$\mathbb{F}_{q}[x]$ of $\mathcal{M}_{s,\ell}(D,G)$.

Algorithm 5
$\mathsf{Generators}_{\mathbb{F}_{q}[x]}(\bm{r},D,G,E,\bm{x},\bm{y},\bm{g})$

1:Input:  • Received word $\bm{r}\in\mathbb{F}_{q}^{n}$, • divisors $D$ and
$G$ for the code $\mathcal{C}_{\mathcal{L}}(D,G)$,  • a divisor
$E=E_{1}+\cdots+E_{N}$, where
$E_{1},\dots,E_{N}\in\mathbb{P}_{F}\setminus\\{P_{\infty}\\}$ are distinct
rational places, $\operatorname{supp}(A)\cap\operatorname{supp}(E)=\emptyset$
and $N\geq\max\\{\deg G+(\ell+3)(2g-1)+(s+1)n+2+\mu,\newline
\hphantom{N\geq\max\\{}(\ell+1)\deg G+4g+(s+1)n\\}$, • evaluations
$\bm{x}=(x_{j})_{j=1,\dots,N}$, where $x_{j}=x(E_{j})\in\mathbb{F}_{q}$, •
evaluations $\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$, • evaluations
$\bm{g}=(g_{v,j}^{(u)})^{u=0,\dots,\ell}_{v=1,2,\ j=1,\dots,N}$, where
$g_{v,j}^{(u)}=g_{v}^{(u)}(E_{j})\in\mathbb{F}_{q}$, $\langle
g_{1}^{(u)},g_{2}^{(u)}\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$
and $\delta_{G_{u}}(g_{v}^{(u)})\leq 4g-1+(u+1)\deg(G)+(s+1)n$, as in
Corollary 4.5.

2:Output:  • $(y_{i}B_{v}^{(u)})^{u=0,\dots,\ell}_{i=0,\dots,\mu-1,\ v=1,2}$,
where the $B_{v}^{(u)}\in\mathcal{M}_{s,\ell}(D,G)$ are as in
Corollary 4.5, i.e. $\langle
y_{i}B_{v}^{(u)}\rangle_{\mathbb{F}_{q}[x]}=\mathcal{M}_{s,\ell}(D,G)$.

3:$(B_{v}^{(u)})^{u=0,\dots,\ell}_{v=1,2}\leftarrow\mathsf{Generators}_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}(\bm{r},D,G,E,\bm{x},\bm{y},\bm{g})$
$\triangleright$ Algorithm 3

4:for $u=0,\dots,\ell$, $v=1,2$ and $t=0,\dots,u$ do

5:
$b_{v,t}^{(u)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)\leftarrow$
the $z^{t}$-coefficient of $B_{v}^{(u)}$

6:
$(y_{i}b_{v,t}^{(u)})_{i=0,\dots,\mu-1}\leftarrow\mathsf{BasisProducts}_{\mathbb{F}_{q}[x]}(b_{v,t}^{(u)},E,-tG,\bm{x},\bm{y})$
$\triangleright$ Algorithm 4

7:for $u=0,\dots,\ell$, $v=1,2$ and $i=0,\dots,\mu-1$ do

8:
$B_{v,i}^{(u)}\in\mathcal{M}_{s,\ell}(D,G)\leftarrow\sum_{t=0}^{u}z^{t}y_{i}b_{v,t}^{(u)}$

9:return $(B_{v,i}^{(u)})^{u=0,\dots,\ell}_{v=1,2,\ i=0,\dots,\mu-1}$

######  Proposition 5.23.

Algorithm 5 is correct and costs
$\tilde{\mathcal{O}}(\ell^{3}\mu^{\omega-1}(n+g))$ operations in
$\mathbb{F}_{q}$.

###### Proof.

Correctness follows immediately from Corollary 4.6 and Lemma 5.22 once we show
that the calls
$\mathsf{BasisProducts}_{\mathbb{F}_{q}[x]}(b_{v,t}^{(u)},E,-tG,\bm{x},\bm{y})$
in Line 4 are valid. In particular, we need to verify that

$N\geq\deg(-tG)+\delta_{-tG}(b_{v,t}^{(u)})+2g+\mu$ (5.2)

for all appropriate values of $u,v$ and $t$. Using the notation from Corollary
4.5 and Algorithm 3, we know that
$b_{v,t}^{(u)}=\binom{u}{t}(-R)^{u-t}g_{v}^{(u)}$, hence by (5.3)

$\delta_{-tG}(b_{r,v}^{(u)})\leq(t+1)\deg G+(u-t+2)(2g-1)+(s+1)n+1\ .$ (5.3)

The sought bound (5.2) on $N$ then follows from

$-t\deg G+\delta_{-tG}(b_{v,t}^{(u)})\leq\deg G+(\ell+2)(2g-1)+(s+1)n+1\ .$

For the complexity, we note that Line 1 costs
$\tilde{\mathcal{O}}(\ell^{3}\mu^{\omega-1}(n+g))$ operations by Proposition
5.15, while each call
$\mathsf{BasisProducts}_{\mathbb{F}_{q}[x]}(b_{v,t}^{(u)},E,-tG,\bm{x},\bm{y})$
in Line 4 costs
$\tilde{\mathcal{O}}(\mu^{\omega-1}(N+|\deg(-tG)|))\subseteq\tilde{\mathcal{O}}(\ell\mu^{\omega-1}(n+g))$
operations by Lemma 5.22. Since the for-loop in Line 2 has
$\mathcal{O}(\ell^{2})$ iterations, the stated complexity follows – the rest
of the algorithm is memory management and is therefore “free”. ∎

######  Remark 5.24.

Computing the generating set $\\{y_{i}\tilde{B}_{v}^{(u)}\\}$ over
$\mathbb{F}_{q}[x]$ of $\mathcal{M}_{s,\ell}(D,G)$ can be done in
$\tilde{\mathcal{O}}(s\ell^{2}\mu^{\omega-1}(n+g))$, since in that case only
$\mathcal{O}(s\ell)$ coefficients of the $\tilde{B}_{v}^{(u)}$ are nonzero.

###  5.5 Finding a nonzero $Q\in\mathcal{M}_{s,\ell}(D,G)$ satisfying
$\delta_{G}(Q)<s(n-\tau)$

The following lemma introduces notation that may be needed to describe the
decoding algorithm.

######  Lemma 5.25.

For any divisor $A$ and any
$a=\sum_{i=0}^{\mu-1}a_{i}y^{(A)}_{i}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(A)$,
where $a_{i}\in\mathbb{F}_{q}[x]$, let

$\curlyvee^{(A)}(a)=(a_{0},\dots,a_{\mu-1})\in\mathbb{F}_{q}[x]^{\mu}\ ,$

and for any
$Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\in\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
let

$\curlyvee_{z}(Q)=(\curlyvee^{(0)}(Q^{(0)})|\curlyvee^{(-G)}(Q^{(1)})|\cdots|\curlyvee^{(-\ell
G)}(Q^{(\ell)}))\in\mathbb{F}_{q}[x]^{\mu(\ell+1)}\ .$

If
$B_{v}^{(u)}\in\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
for $u=0,\dots,\ell$ and $v=1,2$ are as in Corollary 4.5 and

$\bm{M}_{s,\ell}=\left[\begin{array}[]{c}\bm{M}_{s,\ell}^{(1)}\\\
\hline\cr\bm{M}_{s,\ell}^{(2)}\end{array}\right]\in\mathbb{F}_{q}[x]^{2\mu(\ell+1)\times\mu(\ell+1)}\
,$

where for $v=1,2$

$\bm{M}_{s,\ell}^{(v)}=\begin{pmatrix}\left[\begin{array}[]{c}\curlyvee_{z}(y_{0}B_{v}^{(0)})\\\
\hline\cr\vdots\\\
\hline\cr\curlyvee_{z}(y_{\mu-1}B_{v}^{(0)})\end{array}\right]^{\top}\ \vline\
&\cdots&\vline\
\;\left[\begin{array}[]{c}\curlyvee_{z}(y_{0}B_{v}^{(\ell)})\\\
\hline\cr\vdots\\\
\hline\cr\curlyvee_{z}(y_{\mu-1}B_{v}^{(\ell)})\end{array}\right]^{\top}\end{pmatrix}^{\top}\
,$

then $\curlyvee_{z}$ is an $\mathbb{F}_{q}[x]$-isomorphism between
$\mathcal{M}_{s,\ell}(D,G)$ and the row space of ${\bm{M}}_{s,\ell}$.
Moreover, for any $Q$ as before, it holds that
$\delta_{G}(Q)=\mu\deg_{\bm{d}}\curlyvee_{z}(Q)$, where
$\bm{d}=(\bm{d}^{(0)}|\cdots|\bm{d}^{(\ell)})\in(\frac{1}{\mu}\mathbb{Z})^{\mu(\ell+1)}$
with
$\bm{d}^{(t)}=\frac{1}{\mu}\big{(}\delta_{-tG}(y^{(-tG)}_{0}),\dots,\delta_{-tG}(y^{(-tG)}_{\mu-1})\big{)}\in(\frac{1}{\mu}\mathbb{Z})^{\mu}$
for $t=0,\dots,\ell$.

###### Proof.

Corollary 4.6 immediately implies that $\curlyvee_{z}$ is an
$\mathbb{F}_{q}[x]$-isomorphism between $\mathcal{M}_{s,\ell}(D,G)$ and the
row space of ${\bm{M}}_{s,\ell}$. Further, writing
$Q^{(t)}=\sum_{i=0}^{\mu-1}Q_{i}^{(t)}y^{(-tG)}_{i}$ for $t=0,\dots,\ell$,
where $Q_{i}^{(t)}\in\mathbb{F}_{q}[x]$, gives that

$\displaystyle\delta_{G}(Q)$ $\displaystyle=\max_{t}\delta_{-tG}(Q^{(t)})$
$\displaystyle=\max_{t,i}\\{\delta_{-tG}(Q_{i}^{(t)}y^{(-tG)}_{i})\\}$
$\displaystyle=\max_{t,i}\\{\delta(Q_{i}^{(t)})+\delta_{-tG}(y^{(-tG)}_{i})\\}$
$\displaystyle=\max_{t,i}\\{\mu\deg
Q_{i}^{(t)}+\delta_{-tG}(y^{(-tG)}_{i})\\}$
$\displaystyle=\mu\deg_{\bm{d}}\curlyvee_{z}(Q)\ .$

∎

Lemma 5.25 implies that we can find a nonzero $Q\in\mathcal{M}_{s,\ell}(D,G)$
satisfying $\delta_{G}(Q)<s(n-\tau)$, if it exists, by computing the
$\bm{d}$-Popov form of the matrix
$\bm{M}_{s,\ell}\in\mathbb{F}_{q}[x]^{2\mu(\ell+1)\times\mu(\ell+1)}$.
According to Corollary 2.11, this can be achieved with cost
$\tilde{\mathcal{O}}(\ell^{\omega}\mu^{\omega}\deg\bm{M}_{s,\ell})$. To
estimate $\deg\bm{M}_{s,\ell}$, observe that Lemma 3.4 implies that

$\deg{\bm{M}}_{s,\ell}\leq\frac{1}{\mu}\max_{i,r,v,u}\\{-r\deg
G+\delta(y_{i})+\delta_{-rG}(b_{r,v}^{(u)})\\}\ .$

Then Lemma 3.3 and inequality (5.3) imply that

$\deg{\bm{M}}_{s,\ell}\leq\max_{r,u}\frac{6g-2+\mu+(u-r)(n+2g-1)+(s+1)n+\deg
G}{\mu}\in\mathcal{O}(\mu^{-1}\ell(n+g))\ ,$ (5.4)

which means that we can compute the $\bm{d}$-Popov form of $\bm{M}_{s,\ell}$
within our target complexity
$\tilde{\mathcal{O}}(l^{\omega+1}\mu^{\omega-1}(n+g))$.

######  Remark 5.26.

Using the alternative generating set from Remark 4.7, we again get an
improvement on the running time. In equation (5.4), the expression $u-r$
corresponded to the exponent of $-R$ in the expression
$\binom{u}{r}(-R)^{u-r}g_{v}^{(u)}$, which was the coefficient of $z^{r}$ in
$B_{v}^{(u)}$. Since the exponent of $-R$ in a coefficient of
$\tilde{B}_{v}^{(u)}$ never exceeds $s$, we therefore obtain from equation
(5.4) the improved complexity
$\tilde{\mathcal{O}}(s\ell^{\omega}\mu^{\omega-1}(n+g)).$

###  5.6 Root-finding

In this subsection, we consider the final computational ingredient that we
will need for Guruswami-Sudan list-decoding: given a polynomial
$Q(z)\in\mathcal{M}_{s,\ell}(D,G)$, compute the set
$L=\\{f\in\mathcal{L}(G)\mid Q(f)=0\\}$ of all roots of $Q$. We accomplish
this by changing the representation of $Q$ from
$\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
to $\bigoplus_{t=0}^{\ell}z^{t}\mathbb{F}_{q}[\\![x]\\!]$, which will allow us
to use the root-finding algorithm from [29].

Let $P_{0}\not\in\operatorname{supp}G\cup\\{P_{\infty}\\}$ be the fixed
rational place of $F$ for which $x$ is a local parameter. For any nonzero
$h\in F$ let $\widehat{h}\in x^{v_{P_{0}}(h)}\mathbb{F}_{q}[\\![x]\\!]$ denote
the $P_{0}$-adic power series expansion of $h$ in $x$ and define
$\widehat{0}=0$. Furthermore, for any $Q=\sum_{t}z^{t}Q^{(t)}\in F[z]$ let
$\widehat{Q}=\sum_{t}z^{t}\widehat{Q}^{(t)}$. Recall that if
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
for all $t$, then $\delta_{G}(Q)=\max_{t}\delta_{-tG}Q^{(t)}$. The following
definition is from [29], and it describes the output of their root-finding
algorithm:

######  Definition 5.27.

If $\widehat{Q}\in\mathbb{F}_{q}[\\![x]\\!][z]$ and $\beta\in\mathbb{Z}_{\geq
0}$, then a _basic root set_ of $\widehat{Q}$ to precision $\beta$ is a set
$\\{(\widehat{f}_{r},\alpha_{r})\\}_{r=1}^{m}\subset\mathbb{F}_{q}[x]\times\mathbb{Z}_{\geq
0}$ with $m\leq\deg\widehat{Q}$ such that

  1. 1)

$\widehat{Q}(\widehat{f}_{r}+x^{\alpha_{r}}z)\equiv 0\pmod{x^{\beta}}$ for
$r=1,\dots,m$, and

  2. 2)

$\widehat{Q}(\widehat{f})\equiv
0\pmod{x^{\beta}}\iff\widehat{f}\in\bigcup_{r=1}^{m}(\widehat{f}_{r}+x^{\alpha_{r}}\mathbb{F}_{q}[\\![x]\\!])$
for every $\widehat{f}\in\mathbb{F}_{q}[\\![x]\\!]$.

Our algorithm for computing the sought roots of
$Q\in\mathcal{M}_{s,\ell}(D,G)$ will fundamentally rely on the following
result:

######  Theorem 5.28 ([29, Theorem 1.2]).

There is an algorithm which for any
$\widehat{Q}\in\mathbb{F}_{q}[\\![x]\\!][z]$ and any precision
$\beta\in\mathbb{Z}_{\geq 0}$ computes a basic root set of $\widehat{Q}$ to
precision $\beta$ using $\tilde{\mathcal{O}}(\ell\beta)$ deterministic
operations in $\mathbb{F}_{q}$, together with an extra
$\tilde{\mathcal{O}}(\mathsf{R}_{\mathbb{F}_{q}}(\ell)\beta)$ operations,
where $\mathsf{R}_{\mathbb{F}_{q}}(\ell)$ is the cost of finding all
$\mathbb{F}_{q}$-roots of a degree $\ell$ polynomial in $\mathbb{F}_{q}[z]$.
Here, we can choose to use a Las Vegas algorithm with
$\mathsf{R}_{\mathbb{F}_{q}}(\ell)\in\tilde{\mathcal{O}}(\ell)$, e.g. [45,
Corollary 14.16], or a deterministic one from [41] with
$\mathsf{R}_{\mathbb{F}_{q}}(\ell)\in\tilde{\mathcal{O}}(\ell\kappa^{2}\sqrt{p})$,
where $|\mathbb{F}_{q}|=p^{\kappa}$ for some prime $p$.

In order to use Theorem 5.28 in our setting, we will need to address the
following:

  1. 1)

how to choose the precision $\beta$,

  2. 2)

how to convert
$Q\in\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$
to $\widehat{Q}\in\bigoplus_{t=0}^{\ell}z^{t}\mathbb{F}_{q}[\\![x]\\!]$ and

  3. 3)

how to obtain the roots $f\in\mathcal{L}(G)$ of $Q$ from a basic root set of
$\widehat{Q}$.

The second item in the above list is the simplest – writing
$Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}$ with
$Q^{(t)}=\sum_{i=0}^{\mu-1}Q^{(t)}_{i}y^{(-tG)}_{i}$, where
$Q^{(t)}_{i}\in\mathbb{F}_{q}[x]$, we can compute
$\widehat{Q}=\sum_{t=0}^{\ell}z^{t}\widehat{Q}^{(t)}$ by simply relying on the
identity
$\widehat{Q}^{(t)}=\sum_{i=0}^{\mu-1}Q^{(t)}_{i}\widehat{y}^{(-tG)}_{i}$.
Assuming that we have precomputed the
$\widehat{y}^{(-tG)}_{i}\in\mathbb{F}_{q}[\\![x]\\!]$ to sufficiently high
precision, this is just basic arithmetic in $\mathbb{F}_{q}[x]$.

When it comes to the choice of the precision $\beta$, then there are two
restrictions that ought to be considered. The first one comes from making sure
that we don’t return “spurious” roots, i.e. those $f\in\mathcal{L}(G)$ such
that $\widehat{Q}(\widehat{f})\equiv 0\pmod{x^{\beta}}$ while $Q(f)\neq 0$. As
we are about to see in the following lemma, this issue is easily avoided by
choosing $\beta>\delta_{G}(Q)$.

######  Lemma 5.29.

Let $Q(z)=\sum_{t=0}^{\ell}z^{t}Q^{(t)}$ with
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$,
and let $f\in\mathcal{L}(G)$. If $\beta>\delta_{G}(Q)$ and
$\widehat{Q}(\widehat{f})\equiv 0\pmod{x^{\beta}}$, then $Q(f)=0$.

###### Proof.

Notice that since
$f^{t}Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$
for all $t$, then
$Q(f)\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$.
Furthermore, since

$\delta(f^{t}Q^{(t)})=\delta_{tG}(f^{t})+\delta_{-tG}(Q^{(t)})\leq\delta_{-tG}(Q^{(t)})\leq\delta_{G}(Q)\
,$

where the first inequality is due to $f\in\mathcal{L}(G)$, then
$\delta(Q(f))\leq\delta_{G}(Q)$. Combining this with the assumption that
$\widehat{Q}(\widehat{f})=\widehat{Q(f)}\equiv 0\pmod{x^{\beta}}$, we may
conclude that $Q(f)\in\mathcal{L}(\delta_{G}(Q)P_{\infty}-\beta P_{0})$, and
if $\beta>\delta_{G}(Q)$, then this Riemann-Roch space is trivial. ∎

The second restriction on the precision $\beta$ is posed by the task of
converting the truncated power series roots of $\widehat{Q}$ back to
$\mathcal{L}(G)$. Indeed, a basic root set
$\\{(\widehat{f}_{r},\alpha_{r})\\}_{r=1}^{m}$ describes each root
$\widehat{f}_{r}\in\mathbb{F}_{q}[x]$ of $\widehat{Q}$ only to precision
$\alpha_{r}$, and if this $\alpha_{r}$ is too small, then there could exist
two distinct functions $h_{1},h_{2}\in\mathcal{L}(G)$ satisfying
$\widehat{h}_{1}\equiv\widehat{h}_{2}\equiv\widehat{f_{r}}\pmod{x^{\alpha_{r}}}$.
In Lemma 5.31, we will see how we can indirectly control $\alpha_{r}$ by
increasing $\beta$; but first, let us show that conversion from truncated
power series to $\mathcal{L}(G)$ is guaranteed to be unambiguous as long as
$\alpha_{r}>\deg G$.

######  Lemma 5.30.

If $\alpha>\deg G$, then for any $h\in\mathbb{F}_{q}[x]$ it holds that
$|\mathcal{L}(G)\cap(h+x^{\alpha}\mathbb{F}_{q}[\\![x]\\!])|\leq 1$.

###### Proof.

If $h_{1},h_{2}\in\mathcal{L}(G)\cap(h+x^{\alpha}\mathbb{F}_{q}[\\![x]\\!])$,
then $\widehat{h_{1}}\equiv\widehat{h_{2}}\equiv h\pmod{x^{\alpha}}$, which
means that $h_{1}-h_{2}\in\mathcal{L}(G-\alpha P_{0})=\\{0\\}$. ∎

Now we proceed by showing that the $\alpha_{r}$ from Definition 5.27 can be
made arbitrarily large by choosing the precision $\beta$ appropriately.

######  Lemma 5.31.

If $Q(z)=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\neq 0$ with
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$,
and if $f\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G)$
satisfies $\widehat{Q}(\widehat{f}+x^{\alpha}z)\equiv 0\pmod{x^{\beta}}$ for
some $\alpha\in\mathbb{Z}$, then
$\alpha\geq\frac{1}{\ell}(\beta-\delta_{G}(Q))-\delta_{G}(f)$.

###### Proof.

We begin by defining

$T=Q(z+f)=\sum_{t=0}^{\ell}(z+f)^{t}Q^{(t)}=\sum_{t=0}^{\ell}\sum_{u=0}^{t}\binom{t}{u}z^{u}f^{t-u}Q^{(t)}=\sum_{u=0}^{\ell}z^{u}T_{u}\
,$

where $T_{u}=\sum_{t=u}^{\ell}\binom{t}{u}f^{t-u}Q^{(t)}$. Since
$f^{t-u}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}((t-u)G)$
and
$Q^{(t)}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)$,
then
$T_{u}\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-uG)$.
Furthermore, $x^{\alpha u}\widehat{T}_{u}\equiv 0\pmod{x^{\beta}}$ for all $u$
because

$\widehat{Q}(\widehat{f}+x^{\alpha}z)=\widehat{T}(x^{\alpha}z)=\sum_{u=0}^{\ell}z^{u}x^{\alpha
u}\widehat{T}_{u}\equiv 0\pmod{x^{\beta}}\ .$

Letting $r\in\\{0,\dots,\ell\\}$ be such that $v_{P_{0}}(T_{r})<\infty$ is
maximal, observe that

$\displaystyle\alpha\ell+v_{P_{0}}(T_{r})\geq\alpha
r+v_{P_{0}}(T_{r})=v_{P_{0}}(x^{\alpha r}T_{r})\geq\beta\ ,$

which implies that $\alpha\geq\frac{1}{\ell}(\beta-v_{P_{0}}(T_{r}))$.
Finally, noting that

$0\neq T_{r}\in\mathcal{L}(\delta_{-rG}(T_{r})P_{\infty}-rG-
v_{P_{0}}(T_{r})P_{0})\ ,$

then the sought conclusion follows from

$\displaystyle v_{P_{0}}(T_{r})$ $\displaystyle\leq\delta_{-rG}(T_{r})-r\deg
G\leq\delta_{-rG}(T_{r})$
$\displaystyle=\delta_{-rG}\big{(}\sum_{t=r}^{\ell}\binom{t}{r}f^{t-r}Q^{(t)}\big{)}$
$\displaystyle\leq\max_{t}\\{\delta_{-rG}(f^{t-r}Q^{(t)})\\}$
$\displaystyle\leq\max_{t}\\{(t-r)\delta_{G}(f)+\delta_{-tG}(Q^{(t)})\\}$
$\displaystyle=\ell\delta_{G}(f)+\delta_{G}(Q)\ .$

∎

Combining Lemma 5.31 and Lemma 5.30, we obtain the final restriction

$\beta\geq 2\ell\deg G+s(n-\tau)\ ,$

which ensures that unambiguous conversion from the truncated power series
roots of $\widehat{Q}$ to $\mathcal{L}(G)$ is always possible. Indeed, this
bound follows immediately from the fact that $\delta_{G}(f)\leq\deg G$ for all
$f\in\mathcal{L}(G)$ and the assumption that $\delta_{G}(Q)<s(n-\tau)$.
Knowing that such conversion is possible, however, is not enough – we also
need to know how to actually carry it out. In the following simple lemma, we
show how to do this.

######  Lemma 5.32.

If $f\in\mathcal{L}(G)$ and
$\sum_{i=0}^{\mu-1}f_{i}\widehat{y}_{i}^{(G)}\equiv\hat{f}\pmod{x^{\alpha}}$
for some $f_{i}\in\mathbb{F}_{q}[x]$ with $\deg
f_{i}\leq-\frac{1}{\mu}\delta_{G}(y_{i}^{(G)})$ and $\alpha>\deg G$, then
$\sum_{i=0}^{\mu-1}f_{i}y_{i}^{(G)}=f$.

###### Proof.

Since $\delta(f_{i})=\mu\deg f_{i}$, then
$\delta_{G}(f_{i}y_{i}^{(G)})\leq\mu\deg f_{i}+\delta_{G}(y_{i}^{(G)})\leq 0$.
But then $\sum_{i=0}^{\mu-1}f_{i}y_{i}^{(G)}\in\mathcal{L}(G)$, and the
conclusion follows from Lemma 5.30. ∎

Using the notation from Definition 5.7 in the context of Lemma 5.32, we see
that $(f_{0},\dots,f_{\mu-1},1)\in\mathcal{H}_{x^{\alpha}}(\bm{A})$, where
$\bm{A}=[\widehat{y}_{0}^{(G)},\cdots,\widehat{y}_{\mu-1}^{(G)},-\widehat{f}]\in\mathbb{F}_{q}[x]^{1\times(\mu+1)}$.
Recovering $f\in\mathcal{L}(G)$ from $\widehat{f}\operatorname{\
rem\,}x^{\alpha}$ thus translates to finding a polynomial vector
$\bm{f}\in\mathcal{H}_{x^{\alpha}}(\bm{A})$ whose rightmost entry is $1$ and
$\deg_{\bm{d}}\bm{f}=0$, where

$\bm{d}=\frac{1}{\mu}(\delta_{G}(y_{0}^{(G)}),\dots,\delta_{G}(y_{\mu-1}^{(G)}),0)\in(\tfrac{1}{\mu}\mathbb{Z})^{\mu+1}\
.$

But this is easily accomplished by relying on Theorem 5.8 and Corollary 5.10.
We conclude this subsection by presenting our root-finding approach in its
entirety in Algorithm 6.

Algorithm 6 $\mathsf{RootFinding}(D,G,Q,\widehat{\bm{y}})$

1:Input:  • Divisors $D$ and $G$ for the code
$\mathcal{C}_{\mathcal{L}}(D,G)$, • a nonzero
$Q=\sum_{t=0}^{\ell}z^{t}Q^{(t)}\in\mathcal{M}_{s,\ell}(D,G)$ with
$\delta_{G}(Q)<s(n-\tau)$, where
$Q^{(t)}=\sum_{i=0}^{\mu-1}Q_{i}^{(t)}y_{i}^{(-tG)}$ for some
$Q_{i}^{(t)}\in\mathbb{F}_{q}[x]$, •
$\widehat{\bm{y}}=(\widehat{y}_{i}^{(-tG)})_{i=0,\dots,\mu-1}^{t=0,\dots,\ell}$
with $\widehat{y}_{i}^{(-tG)}\in\mathbb{F}_{q}[x]$ such that
$v_{P_{0}}(y_{i}^{(-tG)}-\widehat{y}_{i}^{(-tG)})\geq\beta:=2\ell\deg
G+s(n-\tau)$.

2:Output:  • $L=\\{f\in\mathcal{L}(G)\mid Q(f)=0\\}$ with $|L|\leq\ell$.

3:$\widehat{Q}^{(t)}\in\mathbb{F}_{q}[x]\leftarrow\sum_{i=0}^{\mu-1}Q_{i}^{(t)}\widehat{y}_{i}^{(-tG)}$
for $t=0,\dots,\ell$

4:$\widehat{Q}\in\mathbb{F}_{q}[x]\leftarrow\sum_{t=0}^{\ell}z^{t}\widehat{Q}^{(t)}$

5:$\widehat{L}\subset\mathbb{F}_{q}[x]\leftarrow$ all polynomials from a basic
root set of $\widehat{Q}$ to precision $\beta$

6:$L\leftarrow\emptyset$

7:$\bm{d}\in(\tfrac{1}{\mu}\mathbb{Z})^{\mu+1}\leftarrow\frac{1}{\mu}(\delta_{G}(y_{0}^{(G)}),\dots,\delta_{G}(y_{\mu-1}^{(G)}),0)$

8:$\alpha\in\mathbb{Z}_{>0}\leftarrow\deg G+1$

9:for $\widehat{f}\in\widehat{L}$ do

10: $\bm{F}\in\mathbb{F}_{q}^{(\mu+1)\times(\mu+1)}\leftarrow$ $\bm{d}$-Popov
basis of
$\mathcal{H}_{x^{\alpha}}([\widehat{y}_{0}^{(G)},\dots,\widehat{y}_{\mu-1}^{(G)},-\widehat{f}])$

11: if $\bm{F}$ contains a row $\bm{f}=(f_{0},\dots,f_{\mu-1},1)$ with
$\deg_{\bm{d}}\bm{f}=0$ then

12: $L\leftarrow L\cup\\{\sum_{i=0}^{\mu-1}f_{i}y_{i}^{(G)}\\}$

13:return $L$

######  Proposition 5.33.

Algorithm 6 is correct and costs
$\tilde{\mathcal{O}}(\ell^{2}\mu^{\omega-1}(n+g))$ operations in
$\mathbb{F}_{q}$.

###### Proof.

For correctness, our goal is to prove that $L=K$, where $L$ is the output of
the algorithm and $K=\\{f\in\mathcal{L}(G)\mid Q(f)=0\\}$. If
$\\{(\widehat{f}_{r},\alpha_{r})\\}_{r=1}^{m}\subset\mathbb{F}_{q}[x]\times\mathbb{Z}_{\geq
0}$ denotes the basic root set used in Line 3, i.e.
$\widehat{L}=\\{\widehat{f}_{r}\\}_{r=1}^{m}$, then it is clear that
$K\subseteq\bigcup_{r=1}^{m}K_{r}$, where
$K_{r}=\mathcal{L}(G)\cap(\widehat{f}_{r}+x^{\alpha_{r}}\mathbb{F}_{q}[\\![x]\\!])$
and $m\leq\ell$. Since $\delta_{G}(Q)<s(n-\tau)$,
$\delta_{G}(\widehat{h}_{r})\leq\deg G$ and $\beta=2\ell\deg G+s(n-\tau)$,
then Lemma 5.31 guarantees that
$\alpha_{r}\geq\frac{1}{\ell}\big{(}\beta-\delta_{G}(Q)\big{)}-\delta_{G}(\widehat{h})\geq\deg
G+1$, hence $|K_{r}|\leq 1$ by Lemma 5.30. Combining this with the fact that
each non-empty $K_{r}$ necessarily contains an $\mathcal{L}(G)$-root of $Q$,
as implied by Lemma 5.29 because $\beta>\delta_{G}(Q)$, we may conclude that
$K=\bigcup_{r=1}^{m}K_{r}$. But due to Lemma 5.32

$\displaystyle\bigcup_{r=1}^{m}K_{r}=L=\Big{\\{}\sum_{i=0}^{\mu-1}f_{i}^{(r)}y_{i}^{(G)}\mid$
$\displaystyle\sum_{i=0}^{\mu-1}f_{i}^{(r)}\widehat{y}_{i}^{(G)}\equiv\widehat{f}_{r}$,
r=1,…,m } .

For the complexity, computing the $(\ell+1)\mu$ products
$Q_{i}^{(t)}\widehat{y}_{i}^{(-tG)}$ in Line 1 costs
$\tilde{\mathcal{O}}(\mu\ell\beta)\subseteq\tilde{\mathcal{O}}(\ell^{2}\mu(n+g))$.
The basic root set of $\widehat{Q}$ in Line 3 can be computed with cost
$\tilde{\mathcal{O}}(\beta\deg_{z}(\hat{Q}))\subseteq\tilde{\mathcal{O}}(\ell^{2}(n+g))$
due to [29] (see Theorem 5.28). Finally, the total cost of computing the
$\bm{d}$-Popov bases in line 8 across all of the $\mathcal{O}(\ell)$
iterations in the surrounding for-loop is
$\tilde{\mathcal{O}}(\ell\mu^{\omega-1}(n+g))$ by Corollary 5.10. The claimed
complexity of the algorithm follows. ∎

##  6 Decoding $\mathcal{C}_{\mathcal{L}}(D,G)$

We are now ready to state our Guruswami-Sudan list decoding algorithm for the
code $\mathcal{C}_{\mathcal{L}}(D,G)$. We will assume that the decoding
algorithm has access to the following data, which may be precomputed:

  1. 1.

divisor $E=E_{1}+\cdots+E_{N}$, where $E_{1},\dots,E_{N}$ are distinct
rational places different from $P_{\infty}$ not occurring in
$\operatorname{supp}G$ and $N\geq\max\\{\deg
G+(\ell+3)(2g-1)+(s+1)n+2+\mu,(\ell+1)\deg G+4g+(s+1)n\\}$,

  2. 2.

evaluations $\bm{g}=(g_{v,j}^{(u)})$, where $u=0,\dots,\ell$, $v=1,2$ and
$j=1,\dots,N$, such that $g_{v,j}^{(u)}=g_{v}^{(u)}(E_{j})\in\mathbb{F}_{q}$
where $\langle
g_{1}^{(u)},g_{2}^{(u)}\rangle_{\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}}=\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(G_{u})$,
as in Corollary 4.5

  3. 3.

evaluations $\bm{x}=(x_{j})_{j=1,\dots,N}$, where
$x_{j}=x(E_{j})\in\mathbb{F}_{q}$,

  4. 4.

evaluations $\bm{y}=(y_{i,j})^{i=0,\dots,\mu-1}_{j=1,\dots,N}$, where
$y_{i,j}=y^{(A)}_{i}(E_{j})\in\mathbb{F}_{q}$

  5. 5.

polynomials
$\widehat{\bm{y}}=(\widehat{y}_{i}^{(-tG)})_{i,t}\in\mathbb{F}_{q}[x]^{\mu\times(\ell+1)}$,
with $i=0,\dots,\mu-1$ and $t=-1,\dots,\ell$, polynomials in
$\mathbb{F}_{q}[x]$ such that
$v_{P_{0}}(y_{i}^{(-tG)}-\widehat{y}_{i}^{(-tG)})\geq 2\ell\deg G+s(n-\tau)$
for all $i$ and $t$,

Then the decoding algorithm becomes the following:

Algorithm 7 $\mathsf{Decode}(\bm{r},s,\ell,D,G)$

1:Input:  • Received word $\bm{r}\in\mathbb{F}_{q}^{n}$, • divisors $D$ and
$G$ for the code $\mathcal{C}_{\mathcal{L}}(D,G)$, • decoding parameters
$s,\ell\in\mathbb{Z}_{>0}$ with $s\leq\ell$, • corresponding list-decoding
radius $\tau\in\mathbb{Z}_{>0}$,

2:Output:  • $L=\\{f\in\mathcal{L}(G)\mid d(\bm{r},\bm{c})\leq\tau\\}$ or
$\mathsf{FAIL}$

3:$(B_{v,i}^{(u)})^{u=0,\dots,\ell}_{v=1,2,\
i=0,\dots,\mu-1}\leftarrow\mathsf{Generators}_{\mathbb{F}_{q}[x]}(\bm{r},D,G,E,\bm{x},\bm{y},\bm{g})$

4:${\bm{M}}_{s,\ell}\in\mathbb{F}_{q}[x]^{2\mu(\ell+1)\times\mu(\ell+1)}\leftarrow$
matrix based on the $B_{v,i}^{(u)}$ as in Lemma 5.25

5:$\bm{B}_{s,\ell}\in\mathbb{F}_{q}[x]^{\mu(\ell+1)\times\mu(\ell+1)}\leftarrow$
basis matrix in (unshifted) Popov form of ${\bm{M}}_{s,\ell}$

6:$\bm{d}\in(\tfrac{1}{\mu}\mathbb{Z})^{\mu(\ell+1)}\leftarrow(\bm{d}^{(0)}|\cdots|\bm{d}^{(\ell)})$
with
$\bm{d}^{(t)}=\frac{1}{\mu}(\delta_{-tG}(y_{i}^{(-tG)}))_{i=0}^{\mu-1}\in(\tfrac{1}{\mu}\mathbb{Z})^{\mu}$

7:$\bm{V}_{s,\ell}\in\mathbb{F}_{q}[x]^{\mu(\ell+1)\times\mu(\ell+1)}\leftarrow$
$\bm{d}$-Popov form of $\bm{B}_{s,\ell}$

8:$\bm{Q}=\big{(}(Q_{i}^{(0)})_{i=0}^{\mu}|\dots|(Q_{i}^{(\ell)})_{i=0}^{\mu}\big{)}\in\mathbb{F}_{q}[x]^{\mu(\ell+1)}\leftarrow$
$\deg_{\bm{d}}$-minimal row of $\bm{V}_{s,\ell}$

9:if $\deg_{\bm{d}}\bm{Q}\geq s(n-\tau)$ then

10: return $\mathsf{FAIL}$

11:$Q\in\bigoplus_{t=0}^{\ell}z^{t}\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}(-tG)\leftarrow\sum_{t=0}^{\ell}z^{t}\sum_{i=0}^{\mu-1}Q_{i}^{(t)}y_{i}^{(-tG)}$

12:$L\leftarrow\mathsf{RootFinding}(D,G,Q,\widehat{\bm{y}})$

13:for $f\in L$ do

14:
$\bm{c}\in\mathbb{F}_{q}^{n}\leftarrow\mathsf{Evaluate}(f,D,G,\bm{x},\bm{y})$

15: if $d(\bm{r},\bm{c})>\tau$ then $L\leftarrow L\setminus\\{f\\}$

16:return $L$

Note that the decoding algorithm returns the functions from $\mathcal{L}(G)$
giving rise to all codewords within radius $\tau$ of the received word. Since
in Line 12, the codeword corresponding to these function have been calculated,
it is trivial to modify the algorithm to return these codewords instead.
Combining all results from the previous section, we immediately obtain the
following:

######  Theorem 6.1.

The Guruswami-Sudan algorithm for the AG code $\mathcal{C}_{\mathcal{L}}(D,G)$
can be carried out in complexity
$\tilde{\mathcal{O}}(\ell^{\omega+1}\mu^{\omega-1}(n+g))$. Using the
alternative generating set from Remark 4.7, we obtain the complexity
$\tilde{\mathcal{O}}(s\ell^{\omega}\mu^{\omega-1}(n+g))$.

We now give several examples comparing this result with previously known
results.

###  6.1 Examples

######  Example 6.2.

AG codes obtained from the rational function field $\mathbb{F}_{q}(x)$ are
known as _generalized Reed-Solomon (GRS) codes_. In this case $g=0$ and
$\mu=1$, which specializes the complexity of Algorithm 7 to
$\tilde{\mathcal{O}}(s\ell^{\omega}n)$ operations in $\mathbb{F}_{q}$. The
same complexity is achieved for families of function fields having fixed small
genus, e.g. those arising from elliptic curves. The best known complexity for
Guruswami-Sudan list-decoding of GRS codes is
$\tilde{\mathcal{O}}(s^{2}\ell^{\omega-1}n)$ [9].

######  Example 6.3.

By definition, any maximal function field $F$ over $\mathbb{F}_{q}$ attains
the Hasse-Weil bound – it has exactly $N_{1}=q+1+2g\sqrt{q}$ rational places,
where $q$ is necessarily a square. If $F$ is such a function field, then any
place $P$ of $F\widebar{\mathbb{F}}_{q}$, where $\widebar{\mathbb{F}}_{q}$
denotes the algebraic closure of $\mathbb{F}_{q}$, necessarily contains a
positive element no larger than $\sqrt{q}$ in its Weierstrass semigroup [19,
Theorem 10.6], i.e. we are guaranteed that $\mu\leq\sqrt{q}$ in the complexity
of Algorithm 7. Furthermore, it is well known that all maximal function fields
satisfy $g\leq\sqrt{q}(\sqrt{q}-1)/2\in\mathcal{O}(q)$. This implies that any
code of length $n\in\Omega(q)$ over such a function field can be decoded using
no more that
$\tilde{\mathcal{O}}(s\ell^{\omega}q^{(\omega-1)/2}n)\subseteq\tilde{\mathcal{O}}(s\ell^{\omega}n^{(\omega+1)/2})$
operations in $\mathbb{F}_{q}$, which is sub-quadratic in the code length.
Here, and in the rest of the examples, $u\in\Omega(v)$ if and only if
$v\in\mathcal{O}(u)$ for any functions $u,v:\mathbb{R}_{\geq
0}\to\mathbb{R}_{\geq 0}$.

We obtain even better results for long codes over specific maximal function
fields:

######  Example 6.4.

In the case of Hermitian function field $F=\mathbb{F}_{q^{2}}(x_{1},x_{2})$,
where $x_{2}^{q}+x_{2}=x_{1}^{q+1}$, we have $N_{1}=q^{3}+1$ rational places
and genus $g=q(q-1)/2$. The usual choice of $P_{\infty}$ in one-point codes of
$F$ gives $\mu=q$. Consequently, we can decode any such code of length
$n\in\Omega(q^{3})$ using

$\tilde{\mathcal{O}}(s\ell^{\omega}q^{\omega-1}q^{3})=\tilde{\mathcal{O}}(s\ell^{\omega}q^{\omega+2})=\tilde{\mathcal{O}}(s\ell^{\omega}n^{(\omega+2)/3})$

operations in $\mathbb{F}_{q}$. For $n=q^{3}$, our approach specializes to the
one from [32].

######  Example 6.5.

The Giulietti-Korchmaros function field
$\mathbb{F}_{q^{6}}(x_{1},x_{2},x_{3})$ from [14], where
$x_{2}^{q}+x_{2}=x_{1}^{q+1}$ and $x_{3}^{q^{2}-q+1}=x_{1}^{q^{2}}-x_{1}$, is
also maximal – it has $\mu\leq q^{3}$, $g=(q^{5}-2q^{3}+q^{2})/2$ and
$N_{1}=q^{8}-q^{6}+q^{5}+1$. In this case, we can decode any code of length
$n\in\Omega(q^{8})$ with cost
$\tilde{\mathcal{O}}(s\ell^{\omega}n^{(3\omega+5)/8})$.

######  Example 6.6.

The Suzuki function field $F=\mathbb{F}_{q}(x_{1},x_{2})$, where $q=2^{2e+1}$
is an odd power of two and $x_{2}^{q}+x_{2}=x_{1}^{2^{e}}(x_{1}^{q}+x_{1})$,
has genus $g=2^{e}(q-1)$ and $N_{1}=q^{2}+1$ rational places. Although it is
not maximal in the sense of the Hasse-Weil bound, no other function field with
the same genus and constant field can surpass its number of rational places
[40, Section 5.4]. From [3], it immediately follows that the Weierstrass
semigroup of any place $P$ contains a positive element no greater than $q$,
i.e. $\mu\leq q$. This means that for any code over $F$ of length
$n\in\Omega(q^{2})$, the complexity of Algorithm 7 specializes to
$\tilde{\mathcal{O}}(s\ell^{\omega}n^{(\omega+1)/2})$.

######  Example 6.7.

Let $F$ be a function field over $\mathbb{F}_{q}$ having a rational place
$P_{\infty}$ whose Weierstrass semigroup can be generated by two positive
integers, say $a$ and $b$, where $a<b$. Note that necessarily $\gcd(a,b)=1$,
since otherwise the semigroup generated by $a$ and $b$ has infinitely many
gaps. The genus of such a function field is $(a-1)(b-1)/2$, since this is the
number of gaps of the semigroup generated by $a$ and $b$. Now let
$x,y\in\mathord{\mathchoice{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}{\mbox{Я}}}$ be such
that $\delta(x)=a$ and $\delta(y)=b$. Then $F=\mathbb{F}_{q}(x,y)$ and
$x^{b}+\alpha y^{a}+g(x,y)=0$, where $\alpha\in\mathbb{F}_{q}\setminus\\{0\\}$
and $g(X,Y)\in\mathbb{F}_{q}[X,Y]$ has $(a,b)$-weighted degree strictly less
then $ab$. The curve defined by the equation $X^{b}+\alpha Y^{a}+g(X,Y)=0$ is
sometimes called a $C_{ab}$-curve or a Miura-Kayima curve [28]; codes defined
over such curves are of particular interest for practical applications, as
they can be encoded efficiently [6]. When it comes to decoding, the additional
assumptions that $G=mP_{\infty}$ and that $D-nP_{\infty}$ is a principal
divisor were used in [4] to decode the code $\mathcal{C}_{\mathcal{L}}(D,G)$
in complexity $\tilde{\mathcal{O}}(\ell^{5}a^{3}(n+g))$.

Let us compare this to our results. Knowing that $F$ has a rational point
$P_{\infty}$ whose Weierstrass semigroup contains two positive, relatively
prime integers $a$ and $b$, implies that $g\leq(a-1)(b-1)/2$ and $\mu\leq a$.
Using this weaker assumption and not needing the additional requirement that
$G=mP_{\infty}$ and that $D-nP_{\infty}$ is a principal divisor, we can decode
$\mathcal{C}_{\mathcal{L}}(D,G)$ in complexity
$\tilde{\mathcal{O}}(s\ell^{\omega}a^{\omega-1}(n+g))$. Hence, our results can
both handle more general settings and decode faster.

## Acknowledgments

The authors would like to acknowledge the support from The Danish Council for
Independent Research (DFF-FNU) for the project _Correcting on a Curve_ , Grant
No. 8021-00030B.

## References

  * [1] M. Alekhnovich.  Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes.  IEEE Transactions on Information Theory, 51(7):2257–2265, July 2005\.
  * [2] J. Alman and V. V. Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
  * [3] D. Bartoli, M. Montanucci, and G. Zini.  Weierstrass semigroups at every point of the Suzuki curve.  Acta Arith., 197(1):1–20, 2021.
  * [4] P. Beelen and K. Brander.  Efficient list decoding of a class of algebraic-geometry codes.  Advances in Mathematics of Communications, 4(4):485–518, Nov. 2010\.
  * [5] P. Beelen and T. Høholdt.  The Decoding of Algebraic Geometry Codes.  In E. Martínez-Moro, editor, Advances in Algebraic Geometry Codes, volume 5. World Scientific Publishing Company, 2008.
  * [6] P. Beelen, J. Rosenkilde, and G. Solomatov.  Fast encoding of ag codes over cab curves.  IEEE Transactions on Information Theory, 67(3):1641–1655, 2020\.
  * [7] J. Berthomieu, G. Lecerf, and G. Quintin.  Polynomial root finding over local rings and application to error correcting codes.  Applicable Algebra in Engineering, Communication and Computing, 24(6):413–443, July 2013.
  * [8] D. G. Cantor and E. Kaltofen.  On fast multiplication of polynomials over arbitrary algebras.  Acta Informatica, 28(7):693–701, July 1991.
  * [9] M. Chowdhury, C.-P. Jeannerod, V. Neiger, E. Schost, and G. Villard.  Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations.  IEEE Transactions on Information Theory, 61(5):2370–2387, May 2015\.
  * [10] J. Farr and S. Gao.  Grobner bases, pade approximation, and decoding of linear codes.  Contemporary Mathematics, 381:3, 2005.
  * [11] A. Fröhlich, M. J. Taylor, and M. J. Taylor.  Algebraic number theory.  Number 27. Cambridge University Press, 1991.
  * [12] S. Gao and M. A. Shokrollahi.  Computing roots of polynomials over function fields of curves.  In Coding Theory and Cryptography, pages 214–228. Springer, 2000\.
  * [13] P. Giorgi, C. Jeannerod, and G. Villard.  On the Complexity of Polynomial Matrix Computations.  In International Symposium on Symbolic and Algebraic Computation, pages 135–142, 2003.
  * [14] M. Giulietti and G. Korchmáros.  A new family of maximal curves over a finite field.  Math. Ann., 343(1):229–245, 2009.
  * [15] V. D. Goppa.  Algebraico-Geometric Codes.  Mathematics of the USSR-Izvestiya, 21(1):75, 1983.
  * [16] V. Guruswami and M. Sudan.  Improved Decoding of Reed–Solomon and Algebraic-Geometric Codes.  In IEEE Annual Symposium on Foundations of Computer Science, pages 28–37, 1998.
  * [17] V. Guruswami and M. Sudan.  Improved Decoding of Reed–Solomon Codes and Algebraic-Geometric Codes.  IEEE Transactions on Information Theory, 45(6):1757–1767, 1999\.
  * [18] T. Høholdt, J. H. van Lint, and R. Pellikaan.  Algebraic geometry codes.  In W. C. Huffman and V. S. Pless, editors, Handbook of Coding Theory. Elsevier Science Inc., 1998.