Orders of Gauss periods in finite fields
type: Item
instance of: scholarly article
title: Orders of Gauss periods in finite fields
zbMATH Open document ID: 0931.11057
author: Joachim von zur Gathen
author: Igor E. Shparlinski
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 1998-08-12T00:00:00Z
review text: The problem of determining a fast algorithm to construct primitive roots in a finite field \({\mathbb F}_q\) of \(q\) elements is considered. All known algorithms for this problem work in two stages, first determining a small set guaranteed to contain a primitive element and, second, testing all elements of the set for primitivity. This last part requires the integer factorization of \(q-1\) which is not known to be obtainable in polynomial time. This problem is relaxed here to first, determine an element large order and second, to obtain such elements in some sufficiently dense sequence of fields, rather than all fields. The technique described here uses the notion of a Gauss period of type \((n,2)\), an element constructed in the following manner. For \(r=2n+1\) a prime not dividing \(q\) and \(\beta\) a primitive \(r\)th root of unity in \({\mathbb F}_{q^{2n}}\) then \[ \alpha = \beta + {\beta}^{-1} \in {\mathbb F}_{q^{2n}} \] is called a Gauss period of type \((n,2)\). It is shown here how such elements can be used to give an explicit polynomial-time computation of elements of exponentially large multiplicative order is some finite fields.
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 1164281
zbMATH Keywords: finite fields
zbMATH Keywords: algorithms
zbMATH Keywords: primitive roots in finite fields
zbMATH Keywords: normal bases
zbMATH Keywords: Artin's conjecture
reviewed by: Ian Blake
MaRDI profile type: Publication
full work available at URL: s002000050093
OpenAlex ID: W2914712547
Wikidata QID: Q56144517
DOI: 10.1007/S002000050093
DBLP publication ID: journals/aaecc/GathenS98
Recommended article: Orders of Gauss periods in finite fields
Recommended article: Q2712109
Recommended article: Multiplicative orders of Gauss periods and the arithmetic of real quadratic fields
Recommended article: Order of Gauss periods in large characteristic
Recommended article: Gauss periods: orders and cryptographical applications
Recommended article: MULTIPLICATIVE ORDER OF GAUSS PERIODS
Recommended article: Gaussian Periods and Units in Certain Cyclic Fields
Recommended article: Elliptic periods for finite fields
Recommended article: Q5235403
Recommended article: Orders of quadratic extensions of number fields
description: scientific article; zbMATH DE number 1164281