Finding primitive elements in finite fields of small characteristic

DOI10.1090/CONM/632/12630zbMATH Open1418.11160arXiv1304.1206OpenAlexW1549465692MaRDI QIDQ3187293FDOQ3187293

Authors:

Publication date: 2 September 2016

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

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.

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

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

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)

Cited In (4)

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

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)