Algorithms for exponentiation in finite fields (Q1581128)

Let \(q\) be a prime power, and let \(r=nk+1\) be a prime not dividing \(q\). Let \(e\) be the index of the subgroup generated by \(q\) in the multiplicative group \(\mathbb Z ^*_r=\mathbb Z _r \setminus \{0\}\), and let \(K\) be the unique subgroup of order \(k\) in \(\mathbb Z ^*_r\). Let \(\beta\) be a primitive \(r\)th root of unity in GF\((q^{nk})\). The authors show that \(\alpha = \sum _{a \in K} \beta ^a\), called a Gauss period of type \((n,k)\), is a normal element of GF\((q^n)\) over GF\((q)\) if and only if gcd\((e,n)=1\). It should be noted there is a typo in Theorem 3.1, where \({\mathcal F}_{q^r}\) should be \({\mathcal F}_{q^{r-1}}\). As a consequence of this result, it is shown that for \(n>2\), a normal basis of Gauss periods of type \((n,k)\) over GF\((q)\) is self-dual if and only if \(k\) is even and divisible by the characteristic of GF\((q)\). Moreover, if \(k\) and \(q\) are bounded and GF\((q^n)\) is represented by the normal basis generated by the Gauss periods of type \((n,k)\) over GF\((q)\), the authors show that multiplication in GF\((q^n)\) can be computed with \(O(n \log n \log \log n)\) operations in GF\((q)\), division can be computed with \(O(n \log ^2 n \log \log n)\) operations, and exponentiation can be computed with \(O(n^2 \log \log n)\) operations over GF\((q)\) for exponents less that \(q^n\) and ``small'' \(q\). A fast exponentiation algorithm using polynomial bases is also presented in the paper under review, although no claims about the practicality of the algorithm are made.