On Constructing Primitive Roots in Finite Fields With Advice

摘要

Finding primitive roots in a finite field of p^{4elements 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 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.}