On Constructing Primitive Roots in Finite Fields With Advice
Igor E. Shparlinski · IEEE Transactions on Information Theory · 2018
Finding primitive roots in a finite field of p4elements 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 pn- 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 be fully described by about mn 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.