Algorithms for exponentiation in finite fields
type: Item
instance of: scholarly article
title: Algorithms for exponentiation in finite fields
zbMATH Open document ID: 0997.11112
author: Shuhong Gao
author: Joachim von zur Gathen
author: Daniel Panario
author: Victor Shoup
published in: Journal of Symbolic Computation
publication date: 2002-11-12T00:00:00Z
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.
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 1508227
zbMATH Keywords: Gauss period
zbMATH Keywords: normal basis
zbMATH Keywords: fast exponentiation
reviewed by: Gary L. Ebert
MaRDI profile type: Publication
OpenAlex ID: W1969341770
cites work: An implementation for a fast public-key cryptosystem
cites work: Advances in cryptology - EUROCRYPT '88. Workshop on the theory and application of cryptographic techniques, Davos, Switzerland, May 25--27, 1988. Proceedings
cites work: Q4091421
cites work: Low complexity normal bases
cites work: Factoring with Cyclotomic Polynomials
cites work: Bit-serial Reed - Solomon encoders
cites work: Fast Algorithms for Manipulating Formal Power Series
cites work: On arithmetical algorithms over finite fields
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Matrix multiplication via arithmetic progressions
cites work: Gauss periods: orders and cryptographical applications
cites work: Q4217866
cites work: Optimal normal bases
cites work: On Orders of Optimal Normal Basis Generators
cites work: Efficient and optimal exponentiation in finite fields
cites work: Modern computer algebra
cites work: Q4470462
cites work: Orders of Gauss periods in finite fields
cites work: Q3827943
cites work: Q4695307
cites work: Subquadratic-time factoring of polynomials over finite fields
cites work: Self-Complementary Normal Bases in Finite Fields
cites work: Q3136478
cites work: Optimal normal bases in \(GF(p^ n)\)
cites work: Q4692759
cites work: Fast multiplication of polynomials over fields of characteristic 2
cites work: Fast multiplication of large numbers
cites work: Some Observations on Parallel Algorithms for Fast Exponentiation in $\operatorname{GF}(2^n)$
cites work: Q5538955
cites work: Gaussian elimination is not optimal
cites work: Q3483365
cites work: Q3142322
DOI: 10.1006/JSCO.1999.0309
description: scientific article; zbMATH DE number 1508227