TY - GEN

T1 - Searching for primitive roots in finite fields

AU - Shoup, Victor

PY - 1990

Y1 - 1990

N2 - Let GF(pn) be the finite field with pn elements where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of GF(pn) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(pn). We present three results. First, we present a solution to this problem for the case where p is small, i.e., p = nO(1). Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for GF(p) assuming the ERH.

AB - Let GF(pn) be the finite field with pn elements where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of GF(pn) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(pn). We present three results. First, we present a solution to this problem for the case where p is small, i.e., p = nO(1). Second, we present a solution to this problem under the assumption of the Extended Riemann Hypothesis (ERH) for the case where p is large and n = 2. Third, we give a quantitative improvement of a theorem of Wang on the least primitive root for GF(p) assuming the ERH.

UR - http://www.scopus.com/inward/record.url?scp=0025137208&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025137208&partnerID=8YFLogxK

U2 - 10.1145/100216.100293

DO - 10.1145/100216.100293

M3 - Conference contribution

AN - SCOPUS:0025137208

SN - 0897913612

SN - 9780897913614

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 546

EP - 554

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -