Algorithms for exponentiation in finite fields

DOI10.1006/JSCO.1999.0309MaRDI QIDQ1581128zbMATH OpenOpenAlexFDO

Authors Shuhong Gao, Joachim von zur Gathen, Daniel Panario, Victor Shoup

Publication date 12 November 2002

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/f27837aadec08e903db1b3847d3a2714e59e36fb, https://ir.library.carleton.ca/pub/12551

zbMATH Keywords

fast exponentiation Gauss period normal basis

Mathematics Subject Classification ID

Structure theory for finite fields and commutative rings (number-theoretic aspects) (11T30) Number-theoretic algorithms; complexity (11Y16)

Review text

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.

Recommendations

Cites work

Cited in

(37)

This page was built for publication: Algorithms for exponentiation in finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1581128)