  Fast encoding and decoding of codes have been always an important topic in
code theory as well as complexity theory. Although encoding is easier than
decoding in general, designing an encoding algorithm of codes of length $N$
with quasi-linear complexity $O(N\log N)$ is not an easy task. Despite the fact
that algebraic geometry codes were discovered in the early of 1980s, encoding
algorithms of algebraic geometry codes with quasi-linear complexity $O(N\log
N)$ have not been found except for the simplest algebraic geometry
codes--Reed-Solomon codes. The best-known encoding algorithm of algebraic
geometry codes based on a class of plane curves has quasi-linear complexity at
least $O(N\log^2 N)$. In this paper, we design an encoding algorithm of
algebraic geometry codes with quasi-linear complexity $O(N\log N)$. Our
algorithm works well for a large class of algebraic geometry codes based on
both plane and non-plane curves.
  The main idea of this paper is to generalize the divide-and-conquer method
from the fast Fourier Transform over finite fields to algebraic curves. Suppose
we consider encoding of algebraic geometry codes based on an algebraic curve
${\mathcal X}$ over $\mathbb{F}_q$. We first consider a tower of Galois
coverings ${\mathcal X}={\mathcal X}_0\rightarrow{\mathcal
X}_1\rightarrow\cdots\rightarrow{\mathcal X}_r$ over a finite field
$\mathbb{F}_q$, i.e., their function field tower $\mathbb{F}_q({\mathcal
X}_0)\supsetneq\mathbb{F}_q({\mathcal X}_{1})\supsetneq\cdots
\supsetneq\mathbb{F}_q({\mathcal X}_r)$ satisfies that each of extension
$\mathbb{F}_q({\mathcal X}_{i-1})/\mathbb{F}_q({\mathcal X}_i)$ is a Galois
extension and the extension degree $[\mathbb{F}_q({\mathcal
X}_{i-1}):\mathbb{F}_q({\mathcal X}_i)]$ {is a constant}. Then encoding of an
algebraic geometry code based on ${\mathcal X}$ is reduced to the encoding of
an algebraic geometry code based on ${\mathcal X}_r$.
