### Abstract

We present a new deterministic algorithm for the problem of constructing kth power nonresidues in finite fields F_{p}n, where p is prime and k is a prime divisor of p^{n} - 1. We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed n and p → ∞, our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if k is exponentially large. More generally, assuming the ERH, in time (n log p)^{O(n)} we can construct a set of elements that generates the multiplicative group F*_{p}n. An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.

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

Pages (from-to) | 1311-1326 |

Number of pages | 16 |

Journal | Mathematics of Computation |

Volume | 65 |

Issue number | 215 |

DOIs | |

State | Published - Jul 1996 |

### ASJC Scopus subject areas

- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Constructing nonresidues in finite fields and the extended Riemann hypothesis'. Together they form a unique fingerprint.

## Cite this

*Mathematics of Computation*,

*65*(215), 1311-1326. https://doi.org/10.1090/S0025-5718-96-00751-X