On arithmetical algorithms over finite fields (Q910432)

Let \(F=F_ 0\) be a finite field of characteristic p and \(F_ k\) be the smallest extension field of \(F_ 0\) containing \(\text{GF}(p^{p^ k})\). Then \(\dim (F_ k/F_{k-1})\leq p\) and \(\tilde F=\cup F_ k\) is the splitting field of the sequence of polynomials \(t^{p^{p^ k}}-t\), \(k=1,2,... \). If \(F=\text{GF}(p^ r)\) and \((p,r)=1\) then \(\dim_ F(F_ k/F_{k-1})=p\) and \(\dim_ F(F_ k/F)=p^ k\). A construction is given for a basis of \(\tilde F\) and from this the following construction of a sequence of irreducible polynomials is given. Let \(\omega\) be a primitive \((2p-1)\)th root of unity in the algebraic closure of \(\text{GF}(p)\). Define \(f_ 1(x)=x^ p-x-1\). If \(p=2\) put \(f_ 2(x)=f_ 1(x^ 2-x)\). Otherwise put \[ g_ k(x^{2p-1})=\sum^{2p-2}_{i=0}f_{k-1}(\omega^ ix),\quad f_ k(x)=g_ k(x^ p-x). \] Then \(f_ k(x)\) is irreducible over \(\text{GF}(p)\), \(k=1,2,... \). An analog of the fast Fourier transform is then given which efficiently evaluates a polynomial on some of the additive subgroups of \(F\). This leads to new fast algorithms for polynomial computation.