On the \(q\)th power algorithm (Q958619)

The \(q\)th power algorithm is due to \textit{D. A. Leonard} [IEEE Trans. Inf. Theory 47, No. 6, 2566--2573 (2001; Zbl 1019.94030)]. \textit{D. A. Leonard} and \textit{R. Pellikaan} [Finite Fields Appl. 9, No. 4, 479--504 (2003; Zbl 1085.11059)] used the algorithm to compute a module basis for the integral closure of the polynomial ring \(\mathbb{F}_q[x]\), \(\mathbb{F}_q\) a finite field, in some functions fields \(F=\mathbb{F}_q(x,y)\). In the present paper the \(q\)th power algorithm is adapted to construct a \(\mathbb{F}_q\)-basis for the Riemann-Roch spaces \({\mathcal{L}}( mQ_{\infty})\), where \(Q_{\infty}\) is the unique place of \(F\) over the pole \(P_{\infty}\) of \(x\) in \(\mathbb{F}_q(x)\). Section 2 gives a characterization of the integral closure of \(\mathbb{F}_q[x]\) in \(F\) (Theorem 3) improving a result of \textit{E. Mattig} [PhD thesis, Universität Duisburg-Essen (2003)]. For the rest of the paper \(F\) is supposed to be the function field, considered by Leonard and Pellikaan, \(F=\mathbb{F}_q(x,y)\) defined by \(f(y)=0\), \(f(T)=x^a+T^b+g(x,T)\), where \(\text{gcd}(a,b)=1\), \(a>b>\deg(g)\). The integral closure of \(\mathbb{F}_q[x]\) in \(F\) is the union \(\bigcup_{m=1}^{\infty}{\mathcal{L}}(mQ_{\infty})\) and the paper obtains \(\mathbb{F}_q\)-bases of \({\mathcal{L}}(mQ_{\infty})\). The paper also determines the maximum number of rounds of the \(q\)th power algorithm. Section 3 describes the algorithm to find a basis of \({\mathcal{L}}(mQ_{\infty})\), Section 4 presents a concrete example and Section 5 studies the complexity of the algorithm. As Theorem 14 shows the complexity of computing a basis of \({\mathcal{L}}(mQ_{\infty})\) is \(O(q^3a^3b^9m^3\log_q(ab^3))\).