On Constructing Primitive Roots in Finite Fields With Advice

Finding primitive roots in a finite field of p(n) elements of characteristic p remains to be a hard computational problem with the bottlenecks coming from both locating a small set of possible candidates and also factoring p(n) - 1 in order to test these candidates. Kopparty et al (2016) have introduced a question of designing a fast algorithm to find primitive roots with a short advice from an oracle. Trivially, for an m-bit prime p, such a primitive root can he fully described by about inn bits of information received from an all-powerful oracle. Here, we have shown that one can achieve this in polynomial time and with about (1/2 + o(1))m + O(log n) bits of advice.