### Abstract

Let GF(p^{n}) be the finite field with p^{n} elements, where p is prime. We consider the problem of how to deterministically generate in polynomial time a subset of GF(p^{n}) that contains a primitive root, i.e., an element that generates the multiplicative group of nonzero elements in GF(p^{n}). We present three results. First, we present a solution to this problem for the case where p is small, i.e., p = n^{O(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.

Original language | English (US) |
---|---|

Pages (from-to) | 369-380 |

Number of pages | 12 |

Journal | Mathematics of Computation |

Volume | 58 |

Issue number | 197 |

DOIs | |

State | Published - Jan 1992 |

### ASJC Scopus subject areas

- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics