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