Introduction

Algebraic–Geometric Codes (AG–codes) are a family of linear codes described by Goppa in [Goppa, 1981, Goppa, 1981]. Let \({\cal X}\) be an irreducible projective plane curve of genus \(g\), defined by a (absolutely irreducible) homogeneous polynomial \(H(X,Y,Z)\) over a finite field \(K=\hbox{\bf F}_q\). A place of \({\cal X}\) is the maximal ideal of a discrete valuation subring of \(\overline{K}({\cal X})\). We denote by \(v_P\) the valuation at place \(P\). Its degree is the degree of its residue class field over \(K\). A divisor is an element \(D\) of the free abelian group over the set of places of \({\cal X}\). Namely, such an element can be written additively:

\[D = \sum_{P\in{\rm Pl}({\cal X})}n_P\cdot P\;,\]

where all but finitely many \(n_P\in{\mathbb{Z}}\) are zero. The set of places with nonzero multiplicity is the support of \(D\), denoted by \({\rm Supp}D\). The set of divisors can be equipped with a natural partial order \(\le\) defined by:

\[D = \sum_{P \in {\rm Pl}({\cal X})} n_P \cdot P \le D' = \sum_{P \in {\rm Pl}({\cal X})} n'_P \cdot P \quad \iff \quad n_P \le n'_P \hbox{ for all } P.\]

If \(f\in K({\cal X})\), then one can define the principal divisor:

\[(f) = \sum_{P\in{\rm Pl}({\cal X})}v_P(f)\cdot P\;.\]

A divisor \(D\) is said to be defined over \(K\) if it is stable under the natural action of \({\operatorname{Gal}}(\overline{K}/K)\).

If \((P_1,\ldots,P_n)\) is a tuple of places of degree 1, then for a function \(f\in K({\cal X})\), \(f(P_i)\) can be seen as an element of K. If \(D\) is a divisor defined over \(K\), then the Riemann–Roch space \({\cal L}(D)\) of \(D\) is the \(K\)-vector space of dimension \(k\):

\[{\cal L}(D) = \{ f \in K({\cal X})^*\ |\ (f) + D \ge 0 \} \cup \{ 0 \}.\]

Now provided \(D\) has support disjoint from \(S = \{ P_1,\dots,P_n\}\), we can define the algebraic geometric code to be the \([n,k]_q\)-code:

\[C = C(S,D) = \{ (f(P_1),\dots,f(P_n))\;, f \in {\cal L}(D) \}.\]

If \(\langle f_1,\ldots,f_k\rangle\) is a base of \({\cal L}_K(D)\) as a \(K\)-vector space, then a generator matrix for \(C\) is:

\[\begin{split}G = \begin{pmatrix}f_1(P_1) & \cdots & f_1(P_n)\\ \vdots & \ddots & \vdots\\ f_k(P_1) & \cdots & f_k(P_n)\end{pmatrix}\;.\end{split}\]

Standard references are [Stichtenoth, 1993] and [Tsfasman and Vlăduţ, 1991].

There are two different implementations of the construction of AG–Codes in Magma. The first was implemented by Lancelot Pecquet and is based on the work of Hache [Haché, 1996, Haché and Le Brigand, 1995]. The second approach exploits the divisor machinery for function fields implemented by Florian Hess. In Magma V2.8, only the second implementation is exported. It is intended to rework the Pecquet version to take advantage of the new curve machinery before releasing it.