Finding primitive elements in finite fields of small characteristic

DOI10.1090/CONM/632/12630MaRDI QIDQ3187293zbMATH OpenOpenAlexFDO

Authors

Publication date 2 September 2016

Published in Topics in Finite Fields (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.1206

zbMATH Keywords

primitive elementsdeterministic algorithmsfinite fields of small characteristic

Mathematics Subject Classification ID

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

Abstract: We describe a deterministic algorithm for finding a generating element of the multiplicative group of the finite field $mathbb{F}_{p^n}$ where $p$ is a prime. In time polynomial in $p$ and $n$, the algorithm either outputs an element that is provably a generator or declares that it has failed in finding one. The algorithm relies on a relation generation technique in Joux's heuristically $L(1/4)$-method for discrete logarithm computation. Based on a heuristic assumption, the algorithm does succeed in finding a generator. For the special case when the order of $p$ in $(mathbbZ/nmathbbZ{)}^{i}mes$ is small (that is $(lo{g}_p(n){)}^{mathcalO(1)}$), we present a modification with greater guarantee of success while making weaker heuristic assumptions.

Recommendations

• scientific article; zbMATH DE number 1504683
• On primitive elements in finite fields of low characteristic
• Searching for Primitive Roots in Finite Fields
• Orders of Gauss periods in finite fields
• On the construction of finite field elements of large order

Cited in

(6)

• Efficient polynomial time algorithms computing industrial-strength primitive roots
• On generating coset representatives of \(\mathrm{PGL}_2(\mathbb F_q)\) in \(\mathrm{PGL}_2(\mathbb F_{q^2})\)
• Factor base discrete logarithms in Kummer extensions
• High order elements in finite fields arising from recursive towers
• On the minimal number of small elements generating finite prime fields
• Classifying and generating exact coset representatives of \(\operatorname{PGL}_2(\mathbb{F}_q)\) in \(\operatorname{PGL}_2(\mathbb{F}_{q^2})\)

This page was built for publication: Finding primitive elements in finite fields of small characteristic

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