The least primitive roots mod p

Abstract

Let p>1p\gt 1 be a large prime number, and let ε>0\varepsilon \gt 0 be a small number. The established unconditional upper bounds of the least primitive root u≠±1,v2u\ne \pm 1,{v}^{2} in the prime finite field Fp{{\mathbb{F}}}_{p} have exponential magnitudes u≪p1⁄4+εu\ll {p}^{1/4+\varepsilon }. This note contributes a new result to the literature. It proves that the upper bound of the least primitive root has polynomial magnitude u≤(logp)1+εu\le {\left(\log p)}^{1+\varepsilon } unconditionally.

Keywords

• primitive root
• least primitive root
• finite field
• cryptographic algorithm
• complexity theory
• 11a07
• 11n05
• 11n32