Fast Fourier transform via automorphism groups of rational function fields

The origin of FFT can be traced back to Gauss’s unpublished work in 1805, which was pointed out by Heideman et al. in [HJB84]. After 160 years, Cooley and Tukey [CT65] independently rediscovered this algorithm and popularized it. Now this FFT is known as the Cooley-Tukey algorithm. Cooley-Tukey’s algorithm is a divide-and-conquer algorithm that implements DFT over the complex numbers $\mathbb{C}$; namely, given a polynomial $f(x)=\sum_{i<n}a_{i}x^{i}\in\mathbb{C}[X]$, evaluate $f(x)$ at the $n$-th roots of unity in $\mathbb{C}$. If $n$ is a $B$-smooth number, i.e., all its prime factors are not greater than $B$, Cooley-Tukey’s algorithm computes DFT in $O(Bn\log n)$ arithmetic operations of $\mathbb{C}$. In the following, we also call $n$ is smooth if $B=O(1)$ is a constant. Using Cooley-Tukey’s algorithm, DFT over $\mathbb{F}_{q}$ can also be done in $O(n\log n)$ field operations of $\mathbb{F}_{q}$ if $\mathbb{F}_{q}$ contains an $n$-th root of unity for smooth integer $n$ [M.71]. For DFTs of polynomials in $\mathbb{F}_{q}[x]_{<n}$, but the evaluation points in an extension field $\mathbb{F}_{q^{d}}$ which has smooth $n$-th roots of unity, van der Hoeven and Larrieu [vDHL17] showed that the Frobenius automorphism $\Phi\in\operatorname{\mathrm{Gal}}(\mathbb{F}_{q^{d}}/\mathbb{F}_{q})$ can be used to accelerate the FFT over $\mathbb{F}_{q^{d}}$. The above class of FFTs is called multiplicative FFT due to the fact that the evaluation set is a multiplicative subgroup of $\mathbb{F}_{q}^{*}$.

However, if $\mathbb{F}_{q}$ does not have the desired $n$-th roots of unity, for example, $\mathbb{F}_{q}=\mathbb{F}_{2^{r}}$ and $2^{r}-1$ is a prime number, then the multiplicative FFT is not efficient. To implement FFT over $\mathbb{F}_{q}$ in this case, a new type of FFT algorithm was discovered by Zhu-Wang [WY88] and Cantor [Can89] independently. To distinguish Cooley-Tukey’s FFT algorithm from the one by Zhu-Wang and Cantor, Mateer, and Gao [GS10] named the latter one as the additive FFT based on the fact that the evaluation set is an additive subgroup of $\mathbb{F}_{q}$. In their work [GS10], Mateer and Gao improved the previous additive FFT algorithm [WY88, Can89] and showed that their additive FFT algorithm requires $O(n\log^{2}n)$ additions and $O(n\log n)$ multiplications in $\mathbb{F}_{q}=\mathbb{F}_{2^{r}}$. Particularly, in case $r$ is a power of two, their improved FFT needs $O(n\log n)$ multiplications and only $O(n\log n\cdot\log\log n)$ additions. Four years later, Lin et al. [LCH14] showed that additive FFT can be run in $O(n\log n)$ operations (including additions and multiplications) over $\mathbb{F}_{2^{r}}$ by taking a novel polynomial basis of $\mathbb{F}_{2^{r}}[x]_{<n}$ (the $\mathbb{F}_{2^{r}}$-vector space consisting of all polynomials over $\mathbb{F}_{2^{r}}$ of degree less than $n$). Moreover, their new FFT algorithm is applicable to finite field $\mathbb{F}_{2^{r}}$ with arbitrary $r$. The same group of authors later gave a new interpretation of their algorithm and presented some applications of FFT in encoding and decoding of Reed-Solomon codes [LANH16, HCLB21]. Note that for the additive FFT given in [LCH14, LANH16], it requires that every polynomial in $\mathbb{F}_{q}[x]_{<n}$ is represented under a certain basis consisting of products of linearized polynomials instead of the standard monomial basis $\{1,x,\dots,x^{n-1}\}$.

As we have seen, both multiplicative and additive FFTs over $\mathbb{F}_{q}$ have constraints. Namely, for multiplicative FFT, one requires that $q-1$ is smooth; while for additive FFT, one requires that the characteristic $p$ of $\mathbb{F}_{q}$ is a small constant. Recently, Ben-Sasson et al. [BSCKL23] made a breakthrough in the FFT-like algorithm over an arbitrary finite field. The new algorithm is based on elliptic curves and isogenies of smooth degree, thus it is called elliptic-curve-based FFT (ECFFT for short). More precisely, assume $n$ is a smooth number. Let $f(x)\in\mathbb{F}_{q}[x]_{<n}$ be a polynomial and $S^{\prime}\subsetneq\mathbb{F}_{q}$ a carefully selected subset of cradinality $n$. Then the multipoint evaluation (MPE for short) of $f$ at $S^{\prime}$ can be done in $O(n\log n)$ operations of $\mathbb{F}_{q}$ under the representation of $f$: $f=(f(s_{1}),\ldots,f(s_{n}))$, where $S\subsetneq\mathbb{F}_{q}$ is another subset of size $n$ and $S\cap S^{\prime}=\emptyset$ (This is different from previous FFTs which take as input the coefficients of $f$ under a certain basis of $\mathbb{F}_{q}[x]_{<n}$). They made use of isogenies between elliptic curves to construct the transform from the MPE of $f$ at $S$ to the MPE of $f$ at $S^{\prime}$. During the transformation, some precomputations are required. The authors did not give the total storage for the precomputations, but at least $\Omega(n)$ is required. This is an additional overhead compared to the multiplicative/additive FFTs. Besides, a constraint for the ECFFT over $\mathbb{F}_{q}$ is that length $n$ is upper bounded by $O(\sqrt{q})$, especially for odd $q$. This restricts many applications such as encoding and decoding of $q$-ary Reed-Solomon codes where code lengths $n$ are usually proportional to $q$.

To compare our results and better understand the FFT algorithm, let us sketch the idea of Cooley-Tukey’s algorithm and Lin-Chung-Han’s algorithm [LCH14], which correspond to the multiplicative and additive cases, respectively. For both cases, let $n=2^{r}$ and $f(x)\in\mathbb{F}_{q}[x]$ be a polynomial of degree less than $n$. Denote the complexity of FFT with respect to the number of additions and multiplications by $A(n)$ and $M(n)$, respectively.

For Cooley-Tukey’s algorithm, the evaluation set is selected to be $\mu_{n}\subseteq\mathbb{F}_{q}^{*}$ which is the set of all $n$-th roots of unity, where $n$ is equal to $2^{r}$ for an integer $r\geq 1$. Then the square map $s(x)=x^{2}$ maps $\mu_{n}$ onto $\mu_{n/2}$. Moreover, the polynomial $f(x)$ can be decomposed as a combination of two lower-degree polynomials meanwhile, i.e., $f(x)=f_{0}(x^{2})+x\cdot f_{1}(x^{2})$, where $f_{0},f_{1}\in\mathbb{F}_{q}[x]$ are polynomials of degree less than $n/2$. Thus, the DFT of $f(x)$ at $\mu_{n}$ can be reduced to DFTs of $f_{0}$ and $f_{1}$ at $\mu_{n/2}$ and then a combination of these two sets of $n/2$ evaluations by using $O(n)$ additions/multiplications in $\mathbb{F}_{q}$. Then the running time $A(n)$ and $M(n)$ both satisfy the recursive formula

$$A(n)=2A(n/2)+O(n),\ M(n)=2M(n/2)+O(n).$$

(1.2.1)

After $r$ steps of recursions, we have $A(n)=M(n)=O(n\log n)$.

Lin-Chung-Han’s additive FFT algorithm inherited the idea of the FFT algorithm [Fid72] through polynomials modular arithmetic. Assume $\mathbb{F}_{q}=\mathbb{F}_{2^{r}}=\{\alpha_{i}\}_{i=0}^{2^{r}-1}$. Then the evaluations of $f(x)\in\mathbb{F}_{2^{r}}[x]_{<2^{r}}$ at $\mathbb{F}_{2^{r}}$ are exactly the $2^{r}$ residues

$$\big{(}f(x)\bmod(x-\alpha_{0}),f(x)\bmod(x-\alpha_{1}),\dots,f(x)\bmod(x-\alpha_{2^{r}-1})\big{)}.$$

Note that $\prod_{i=0}^{2^{r}-1}(x-\alpha_{i})=x^{2^{r}}-x$ and $f(x)=f(x)\bmod(x^{2^{r}}-x)$. To efficiently get these $2^{r}$ residues, Lin et al. introduced linearized polynomials to decompose the modulo $(x^{2^{r}}-x)$ into $2^{r}$ modulus $\{(x-\alpha_{i})\}_{i=0}^{2^{r}-1}$ recursively. Assume

$$\{0\}=W_{0}\subsetneq W_{1}\subsetneq\cdots\subsetneq W_{r-1}\subsetneq W_{r}=\mathbb{F}_{2^{r}}$$

is a subspace chain of $\mathbb{F}_{2^{r}}$ and $W_{i}=W_{i-1}\cup(W_{i-1}+v_{i})$ for some $v_{i}\in\mathbb{F}_{2^{r}}$ and each $i\in[1,r]$. In particular, we have $\dim_{\mathbb{F}_{2}}(W_{i})=i$ and $\{v_{1},\dots,v_{r}\}$ constitutes a basis of $\mathbb{F}_{2^{r}}$ as a vector space over $\mathbb{F}_{2}$. Define the linearized polynomial as $\ell_{i}(x)=\prod_{w\in W_{i}}(x-w)$. Then $\deg(\ell_{i})=2^{i}$ and

$$\ell_{i}(x+\beta)=\ell_{i-1}(x+\beta)\cdot\ell_{i-1}(x+\beta+v_{i})\ \text{for\ any}\ \beta\in\mathbb{F}_{2^{r}}.$$

For any $e\in[0,2^{r}-1]$, assume the $2$-adic expansion of $e$ is $e=\sum_{i=0}^{r-1}e_{i}2^{i}$. Then

$$\deg(\ell_{0}^{e_{0}}(x)\ell_{1}^{e_{1}}(x)\cdots\ell_{r-1}^{e_{r-1}}(x)\})=e.$$

Hence $\mathcal{B}=\{\ell_{0}^{e_{0}}(x)\ell_{1}(x)^{e_{1}}\cdots\ell_{r-1}^{e_{r-1}}(x)\ \mid e\in[0,2^{r}-1]\}$ is a basis of $\mathbb{F}_{2^{r}}[x]_{<2^{r}}$. Under the basis $\mathcal{B}$, write $f(x)=f_{0}(x)+\ell_{r-1}(x)\cdot f_{1}(x)$, where $f_{0},f_{1}\in\mathbb{F}_{2^{r}}[x]$ are polynomials of degree less than $2^{r-1}$. Since $x^{2^{r}}-x=\ell_{r-1}(x)\cdot\ell_{r-1}(x+v_{r})$, by the Chinese Reminder theorem,

$$f(x)\bmod(x^{2^{r}}-x)=\Big{(}f_{0}(x)\bmod\ell_{r-1}(x),\big{(}f_{0}(x)+\ell_{r-1}(v_{r})f_{1}(x)\big{)}\bmod\big{(}\ell_{r-1}(x)+\ell_{r-1}(v_{r})\big{)}\Big{)}.$$

Thus, the computation of $2^{r}$ residues $\{f(x)\bmod(x-\alpha)\}_{\alpha\in W_{r}}$ of $f(x)$ can be reduced to $2^{r-1}$ residues $\{f_{0}\bmod(x-\alpha)\}_{\alpha\in W_{r-1}}$ of $f_{0}(x)$ and $2^{r-1}$ residues $\{\big{(}f_{0}+\ell_{r-1}(v_{r})\cdot f_{1}\big{)}\bmod(x-\alpha)\}_{\alpha\in W_{r-1}+v_{r}}$ of $f_{0}(x)+\ell_{r-1}(v_{r})f_{1}(x)$. Since $f_{0},f_{1}$ both have degree less than $2^{r-1}$, the computation of $f_{0}+\ell_{r-1}(v_{r})f_{1}$ needs $O(n)$ additions and $O(n)$ multiplications in $\mathbb{F}_{2^{r}}$, respectively. Thus the running time $A(n)$ and $M(n)$ also satisfy equation  (1.2.1) leading to $A(n)=M(n)=O(n\log n)$.

So far, we have briefly described the ideas of multiplicative FFT and additive FFT. Although there are similarities between multiplicative and additive FFTs, the methods used are different. This makes great inconvenience for the generalization of these FFT algorithms and their applications.

In this work, we provide a unified framework for FFT in $\mathbb{F}_{q}$ that includes both multiplicative and additive FFT. More importantly, our framework works well when either $q-1$, $q$, or $q+1$ is smooth. In other words, we give a new FFT algorithm that includes both the multiplicative DFT and the additive DFT as two special cases. Besides, we discuss a new case that has never been considered: if $n$ is a divisor of $q+1$ that is $B$-smooth for a real number $B>0$; namely, $n$ can be factored into the product of $\prod_{i=1}^{r}p_{i}$ satisfying $p_{i}\leq B$ for every $1\leq i\leq r$, then our FFT algorithm runs in $O(B\cdot n\cdot\log n)$ operations in $\mathbb{F}_{q}$.

We compare our result with known results in Subsection 1.1, see Table 1.

Let $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$ be the automorphism group consisting of all automorphisms of $\mathbb{F}_{q}(x)$ keeping elements of $\mathbb{F}_{q}$ invariant. Let $G$ be a subgroup of $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$ and let $\mathbb{F}_{q}(x)^{G}$ be the subfield of $\mathbb{F}_{q}(x)$ fixed by $G$. If $G$ satisfies the following conditions (see Section 2.1 for precise definitions):

1. (i)

   $G$ is an abelian group with smooth order $n=|G|$, i.e., $n=\prod_{i=1}^{r}p_{i}$, where all prime divisors $p_{i}$ are small constant.

2. (ii)

   There is a place $\mathcal{Q}$ of $\mathbb{F}_{q}(x)^{G}$ that is totally ramified in $\mathbb{F}_{q}(x)/\mathbb{F}_{q}(x)^{G}$.

3. (iii)

   $\mathbb{F}_{q}(x)^{G}$ has a rational place $\mathfrak{P}$ that splits completely in $\mathbb{F}_{q}(x)$. Let $\mathcal{P}$ denote the set of places of $\mathbb{F}_{q}(x)$ lying over $\mathfrak{P}$.

then we can construct an FFT for any polynomial in $\mathbb{F}_{q}[x]_{<n}$ at $\mathcal{P}$ with complexity $O(n\log n)$ (since every rational place $P\in\mathcal{P}$ is the zero of $x-\alpha$ for $\alpha\in\mathbb{F}_{q}$ and $f(P)=f(\alpha)$ for any $f\in\mathbb{F}_{q}[x]$, we identify $\mathcal{P}$ as a subset of $\mathbb{F}_{q}$). Our FFT is based on the Galois theory, in order to differentiate it from the classical FFT, we name it G-FFT.

By condition (i) and the structure of finite abelian groups, $G$ has an ascending chain of subgroups

$$\{1\}=G_{0}\subsetneq G_{1}\subsetneq\cdots G_{r-1}\subsetneq G_{r}=G,$$

where $|G_{i}|/|G_{i-1}|=p_{i}$ for $i=1,\cdots,r$. By the Galois theory [HKTO08], each group $G_{i}$ determines a fixed subfield $\mathbb{F}_{q}(x)^{G_{i}}$ of $\mathbb{F}_{q}(x)$. As any subfield of $\mathbb{F}_{q}(x)$ is again a rational function field [Sti09, Proposition 3.5.9], we assume $\mathbb{F}_{q}(x)^{G_{i}}=\mathbb{F}_{q}(x_{i})$ for some $x_{i}\in\mathbb{F}_{q}(x)$. Thus the subgroups chain leads to a tower of fields

$$\mathbb{F}_{q}(x)=\mathbb{F}_{q}(x_{0})\supsetneq\mathbb{F}_{q}(x_{1})\supsetneq\cdots\supsetneq\mathbb{F}_{q}(x_{r})=\mathbb{F}_{q}(x)^{G}.$$

Furthermore, if the pole place $P_{\infty}$ of $x$ totally ramifies in the extension $\mathbb{F}_{q}(x)/\mathbb{F}_{q}(x)^{G}$, then we can choose the $x_{i}$ such that each $x_{i+1}$ is a polynomial of $x_{i}$ of degree $p_{i+1}$ for $0\leq i\leq r-1$. As a result, we have $\nu_{P_{\infty}}(x_{i})=-|G_{i}|$ for each $0\leq i\leq r$. Based on these facts, we can construct an $\mathbb{F}_{q}$-basis of the polynomial space $\mathbb{F}_{q}[x]_{<n}$ as following

$$\mathcal{B}=\{x_{0}^{e_{0}}x_{1}^{e_{1}}\cdots x_{r-1}^{e_{r-1}}\mid\operatorname{\textbf{e}}=(e_{0},e_{1},\ldots,e_{r-1})\in\mathbb{Z}_{p_{1}}\times\mathbb{Z}_{p_{2}}\times\cdots\times\mathbb{Z}_{p_{r}}\}.$$

(1.4.1)

Thus, any $f(x)\in\mathbb{F}_{q}[x]_{<n}$ can be represented as

$$\begin{split}f(x)&=\sum_{e_{0}=0}^{p_{1}-1}\sum_{e_{1}=0}^{p_{2}-1}\ldots\sum_{e_{r-1}=0}^{p_{r}-1}a_{\operatorname{\textbf{e}}}\cdot x_{0}^{e_{0}}x_{1}^{e_{1}}\cdots x_{r-1}^{e_{r-1}}\\ &=f_{0}(x_{1})+x\cdot f_{1}(x_{1})+\dots+x^{p_{1}-1}\cdot f_{p_{1}-1}(x_{1}),\end{split}$$

(1.4.2)

where the second “=” is the result of combining all terms with the same $x^{e_{0}}$ for $e_{0}=0,1,\ldots,p_{1}-1$. Then $f_{0}(x_{1}),\ldots,f_{p_{1}-1}(x_{1})\in\mathbb{F}_{q}[x_{1}]$ are polynomials of degree less than $n/p_{1}$ with respect to variable $x_{1}$. Thus, the evaluations of $f(x)$ at $\mathcal{P}$ can be reduced to the evaluations of $f_{0},f_{1},\dots,f_{p_{1}-1}$ at $\mathcal{P}$ and then a combination of these $p_{1}$ sets of values by using $p_{1}O(n)$ additions/multiplications in $\mathbb{F}_{q}$. However, for every $f_{j}\in\mathbb{F}_{q}(x_{1})$, its evaluation at every $P\in\mathcal{P}$ satisfying $f_{j}(P)=f\big{(}P\cap\mathbb{F}_{q}(x_{1})\big{)}$. According to (iii), let $\mathcal{P}_{1}=\mathcal{P}\cap\mathbb{F}_{q}(x_{1})$ be the set of places of $\mathbb{F}_{q}(x_{1})$ lying over $\mathfrak{P}$. Then $|\mathcal{P}_{1}|=n/p_{1}$. Denote the complexity of FFT with respect to the number of additions and multiplications by $A(n)$ and $M(n)$, respectively. Then $A(n)$ and $M(n)$ both satisfy the recursive formula

$$A(n)=p_{1}\cdot A(n/p_{1})+p_{1}\cdot O(n),\ M(n)=p_{1}\cdot M(n/p_{1})+p_{1}\cdot O(n).$$

(1.4.3)

Similarly, the DFTs of $f_{0},\dots,f_{p_{1}-1}$ at $\mathcal{P}_{1}$ can be reduced to DFTs of polynomials of lower-degree with respect to the variable $x_{2}$ at $\mathcal{P}_{2}=\mathcal{P}_{0}\cap\mathbb{F}_{q}(x_{2})$. Then, after $r$ steps of recursions, we obtain $A(n)=M(n)=O(B\cdot n\log n)$, where $B=\max_{1\leq i\leq r}\{p_{i}\}$.

The above idea works well for a subgroup $G$ of the affine linear group $\mathrm{AGL}_{2}(q)$ as the pole place $P_{\infty}$ of $x$ totally ramifies in $\mathbb{F}_{q}(x)/\mathbb{F}_{q}(x)^{G}$. However, if we choose a subgroup that is not contained in $\mathrm{AGL}_{2}(q)$, then there are no rational places that totally ramify in $\mathbb{F}_{q}(x)/\mathbb{F}_{q}(x)^{G}$. In this paper, we consider a cyclic subgroup $G$ of $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$ of order $q+1$. There is a place $Q$ of degree $2$ that totally ramifies in the extension $\mathbb{F}_{q}(x)/\mathbb{F}_{q}(x)^{G}$, and the rational place $P_{\infty}$ is splitting completely. Assume $n=q+1=2^{r}$. By some elementary analysis, we first construct a basis $\mathcal{B}$ of the Riemann-Roch space $\mathcal{L}\left(nQ\right)=\frac{1}{Q^{n}}\mathbb{F}_{q}[x]_{\leq 2n}$ (here we identify the place $Q$ with a quadratic irreducible polynomial $Q$). Then we show that a subset $\tilde{\mathcal{B}}$ of $\mathcal{B}$ spans the $\mathbb{F}_{q}$ vector space $\frac{u_{r,0}(x)}{Q^{n}}\mathbb{F}_{q}[x]_{<n}$, where $u_{r,0}(x)$ is a polynomial of degree $n$ with no roots in $\mathbb{F}_{q}$ (see Lemma 4.5). In other words, we get a basis of $\mathbb{F}_{q}[x]_{<n}$, namely, $\frac{Q^{n}}{u_{r,0}(x)}\tilde{\mathcal{B}}$.

For a polynomial $f\in\mathbb{F}_{q}[x]$ which is represented under the basis $\frac{Q^{n}}{u_{r,0}(x)}\tilde{\mathcal{B}}$, let $\tilde{f}=\frac{u_{r,0}(x)}{Q^{n}}f\in\mathcal{L}(nQ)$. By the same recursive reduction, we first show that the multipoint evaluation $\{\tilde{f}(\alpha)\mid\alpha\in\mathbb{F}_{q}\}$ of $\tilde{f}$ can be computed via G-FFT in time $O(n\log n)$. Next, by precomputing $\frac{Q^{n}(\alpha)}{u_{r,0}(\alpha)}$ for all $\alpha\in\mathbb{F}_{q}$, we get $f(\alpha)=\frac{Q^{n}(\alpha)}{u_{r,0}(\alpha)}\tilde{(}\alpha)$ for every $\alpha\in\mathbb{F}_{q}$.

In the process, we need $n$ precomputations of $\{\frac{Q^{n}(\alpha)}{u_{r,0}(\alpha)}\mid\alpha\in\mathbb{F}_{q}\}$. Moreover, in the recursive reduction, we also need some precomputations to get around the pole places of elements in the basis $\tilde{\mathcal{B}}$, which will cost $O(\log n)$ storage space. Therefore, the total storage in the G-FFT algorithm is $O(n)$.

The paper is organized as follows. In Section 2, we present some preliminaries on algebraic function fields, in particular rational function fields. In Section 3, we construct the G-FFT via affine linear subgroups $G$ of $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$ and instantiate $G$ by the multiplicative group $\mathbb{F}_{q}^{*}$ and additive group $\mathbb{F}_{q}$ as two examples. Moreover, in the case $q$ is smooth, we show that G-FFT under the standard basis of $\mathbb{F}_{q}[x]_{<n}$ can be done in $O(n\log^{2}n)$. In Section 4, we construct a new basis of $\mathbb{F}_{q}[x]_{<n}$ via a non-affine cyclic subgroup of $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$ of order $n$. Then we show that the G-FFT of smooth length $n\mid q+1$ can be done in $O(n\log n)$ and give the G-FFT algorithm for the case $q+1=2^{r}$. Finally, Section 5 concludes our work.

We briefly introduce the theory of rational function fields in this subsection. The reader may refer to [Sti09] for details.

For a prime power $q$, let $\mathbb{F}_{q}$ denote the finite field of $q$ elements. An algebraic function field over $\mathbb{F}_{q}$ in one variable is a field extension $F\supset\mathbb{F}_{q}$ such that $F$ is an algebraic extension of $\mathbb{F}_{q}(x)$ for some transcendental element $x$ over $\mathbb{F}_{q}$. In particular, the rational function field $\mathbb{F}_{q}(x)$ is an algebraic function field of one variable. In the following, we say $F/\mathbb{F}_{q}$ is an algebraic function field with the assumption that $\mathbb{F}_{q}$ is the full constant field of $F$, i.e., every algebraic element of $F$ over $\mathbb{F}_{q}$ belongs to $\mathbb{F}_{q}$ as well.

Now let $F$ be the rational function field $\mathbb{F}_{q}(x)$ over $\mathbb{F}_{q}$. For every irreducible polynomial $P(x)\in\mathbb{F}_{q}[x]$, we define a discrete valuation $\nu_{P}$ which is a map from $\mathbb{F}_{q}[x]$ to $\mathbb{Z}\cup\{\infty\}$ given by $\nu_{P}(0)=\infty$ and $\nu_{P}(f)=a$, where $f$ is a nonzero polynomial and $a$ is the unique nonnegative integer satisfying $P^{a}|f$ and $P^{a+1}\nmid f$. This map can be extended to $\mathbb{F}_{q}(x)$ by defining $\nu_{P}(f/g)=\nu_{P}(f)-\nu_{P}(g)$ for any two polynomials $f,g\in\mathbb{F}_{q}[x]$ with $g\neq 0$. Apart from the above finite discrete valuation $\nu_{P}$, we have an infinite valuation $\nu_{\infty}$ defined by $\nu_{\infty}(f/g)=\deg(g)-\deg(f)$ for any two polynomials $f,g\in\mathbb{F}_{q}[x]$ with $g\neq 0$. Note that we define $\deg(0)=\infty$. The set of places of $F$ is denoted by $\mathbb{P}_{F}$.

For each discrete valuation $\nu_{P}$ ($P$ is either a polynomial or $\infty$), by abuse of notion we still denote by $P$ the set $\{y\in F:\;\nu_{P}(y)>0\}$. Then the set $P$ is called a place of $F$. If $P=x-\alpha$, then we denote $P$ by $P_{\alpha}$. The degree of the place $P$ is defined to be the degree of the corresponding polynomial $P(x)$. If $P$ is the infinite place $\infty$, then the degree of $\infty$ is defined to be $1$. A place of degree $1$ is called rational. In fact, there are exactly $q+1$ rational places for the rational function field $F$ over $\mathbb{F}_{q}$.

Let $\mathbb{P}_{F}$ be the set of all places of $F/{\mathbb{F}_{q}}$ and let $\mathbb{P}_{F}^{(1)}$ be the subset of $\mathbb{P}_{F}$ consisting of all rational places, i.e., places of degree one. Assume $F^{\prime}/F$ is a finite algebraic extension of degree $n$ with the constant field $\mathbb{F}_{q}$. A place $P^{\prime}\in\mathbb{P}_{F^{\prime}}$ is said to be lying over $P$, written as $P^{\prime}\mid P$, if $P\subseteq P^{\prime}$. The ramification index of $P^{\prime}$ over $P$ is denoted by $e(P^{\prime}\mid P)$. Let $P_{1},\dots,P_{m}$ be all the places of $F^{\prime}$ lying over $P$. If $e(P_{i}\mid P)=[F^{\prime}:F]$ for a place $P_{i}\mid P$, then $m=1$ and $P$ is said to be totally ramified in $F^{\prime}$; if $e(P_{i}\mid P)=1$ for every $P_{i}$, $i=1,\dots,m$, $P$ is said to be unramified in $F^{\prime}$; furthermore, if $e(P_{i}\mid P)=1$ and $m=[F^{\prime}:F]$, then $P$ is said to split completely in $F^{\prime}$. An important fact that is used in the design of our G-FFT is that for every place $P$ of $F$ and a function $f\in F$ with $\nu_{P}(f)\geq 0$, the value $f(P^{\prime})$ is constant for all places $P^{\prime}$ of $F^{\prime}$ lying over $P$.

Let $F=\mathbb{F}_{q}(x)$ be a rational function field. For a place $Q$ of $F$ and an integer $m$, we define the Riemann-Roch space associated with $Q$ as

$$\mathcal{L}(mQ):=\{f\in F^{*}:\;\nu_{P}(f)\geq 0\;\mbox{if $P\neq Q$};\;\nu_{Q}(f)\geq-m\}\cup\{0\}.$$

Then $\mathcal{L}(mQ)$ is a finite-dimensional vector space over $\mathbb{F}_{q}$. If $Q$ is the pole of $x$, then $\mathcal{L}(mQ)$ is the polynomial space $\mathbb{F}_{q}[x]_{\leq m}$. The dimension $\dim_{\mathbb{F}_{q}}\mathcal{L}(mQ)$ is usually denoted by $\ell(mQ)$. Then we have

$$\ell(mQ)=m\deg(Q)+1$$

for $m\geq 0$; and $\ell(mQ)=0$, otherwise.

Let $F=\mathbb{F}_{q}(x)$ be the rational function field for some transcendental element $x\in F$ over the finite field $\mathbb{F}_{q}$. We denote by $\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})$ the automorphism group of $F$ over $\mathbb{F}_{q}$, i.e.,

$$\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})=\{\sigma:F\rightarrow F:\;\sigma\mbox{ is an }\mathbb{F}_{q}\mbox{-automorphism of }F\}.$$

(2.3.1)

It is clear that an automorphism $\sigma\in\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})$ is uniquely determined by $\sigma(x)$. It is well known that every automorphism $\sigma\in\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})$ is given by

$$\sigma(x)=\frac{ax+b}{cx+d}$$

(2.3.2)

for some constant $a,b,c,d\in\mathbb{F}_{q}$ with $ad-bc\neq 0$ (see [HKTO08]). Denote by $\mathrm{GL}_{2}(q)$ the general linear group of $2\times 2$ invertible matrices over $\mathbb{F}_{q}$. Thus, every matrix $A=\left(\begin{array}[]{cc}a&b\\ c&d\end{array}\right)\in\mathrm{GL}_{2}(q)$ induces an automorphism of $F$ given by (2.3.2). Two matrices of $\mathrm{GL}_{2}(q)$ induce the same automorphism of $F$ if and only if they belong to the same coset of $Z(\mathrm{GL}_{2}(q))$, where $Z(\mathrm{GL}_{2}(q))$ stands for the center $\{aI_{2}:\;a\in\mathbb{F}_{q}^{*}\}$ of $\mathrm{GL}_{2}(q)$. This implies that $\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})$ is isomorphic to the projective linear group $\mathrm{PGL}_{2}(q):=\mathrm{GL}_{2}(q)/Z(\mathrm{GL}_{2}(q))$. Thus, we can idenitify $\operatorname{\mathrm{Aut}}(F/\mathbb{F}_{q})$ with $\mathrm{PGL}_{2}(q)$.

Consider the subgroup of $\mathrm{PGL}_{2}(q)$

$$\mathrm{AGL}_{2}(q):=\left\{\left(\begin{array}[]{cc}a&b\\ 0&1\end{array}\right):\;a\in\mathbb{F}_{q}^{*},b\in\mathbb{F}_{q}\right\}.$$

(2.3.3)

$\mathrm{AGL}_{2}(q)$ is called the affine linear group. Every element $A=\left(\begin{array}[]{cc}a&b\\ 0&1\end{array}\right)\in\mathrm{AGL}_{2}(q)$ defines an affine automorphism $\sigma(x)=ax+b.$

In addition to the subgroup $\mathrm{AGL}_{2}(q)$, $\mathrm{PGL}_{2}(q)$ has a cyclic subgroup with order $q+1$. Let $P(x)=x^{2}+ax+b$ be a primitive polynomial over $\mathbb{F}_{q}[x]$. Consider the element $\sigma=\left(\begin{array}[]{cc}0&1\\ -b&-a\end{array}\right)\in\mathrm{PGL}_{2}(q)$. Then the order of $\sigma$ is $q+1$ (one can refer to [JMX19, Lemma V.1]). Thus $\langle\sigma\rangle$ induces a $q+1$-cyclic subgroup of $\operatorname{\mathrm{Aut}}(\mathbb{F}_{q}(x)/\mathbb{F}_{q})$.