Small Prime Primitive Roots in Arithmetic Progressions

Abstract

Let $p>1$ be a large prime number, let $q=O(\log \log p)$ and let $1\le a<q$ be a pair of relatively prime integers. It is proved that there is a prime primitive root $u\ll (\log p)(\log \log p{)}^5$ such that $u\equiv a\mathrm{mod}q$ in the prime finite field ${\mathbb{F}}_p$.

Eighteen Pages. Keywords: Primitive root mod $p$; Least prime Primitive root; Arithmetic progression; Complexity theory; Finite field