### 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) |
---|---|

Title of host publication | Proc 22nd Annu ACM Symp Theory Comput |

Publisher | Publ by ACM |

Pages | 546-554 |

Number of pages | 9 |

ISBN (Print) | 0897913612, 9780897913614 |

DOIs | |

State | Published - 1990 |

Event | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990 |

### Publication series

Name | Proc 22nd Annu ACM Symp Theory Comput |
---|

### Other

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

City | Baltimore, MD, USA |

Period | 5/14/90 → 5/16/90 |

### ASJC Scopus subject areas

- Engineering(all)

## Fingerprint Dive into the research topics of 'Searching for primitive roots in finite fields'. Together they form a unique fingerprint.

## Cite this

*Proc 22nd Annu ACM Symp Theory Comput*(pp. 546-554). (Proc 22nd Annu ACM Symp Theory Comput). Publ by ACM. https://doi.org/10.1145/100216.100293