Constructing nonresidues in finite fields riemann hypothesis (Preliminary Version)

Johannes Buchmann, Victor Shoup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We describe a new deterministic algorithm for the problem of constructing k-Th power nonresidues in finite fields GF(pn), where p is prime and k is a prime divisor of pn - 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 previous algorithms for this problem, this polynomial time bound holds even if k is very large. More generally, assuming the ERH, in time (log p)"(n) we can construct a set of elements that generates GF(pn).

Original languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991
PublisherAssociation for Computing Machinery
Pages72-79
Number of pages8
ISBN (Electronic)0897913973
StatePublished - Jan 3 1991
Event23rd Annual ACM Symposium on Theory of Computing, STOC 1991 - New Orleans, United States
Duration: May 5 1991May 8 1991

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F130073
ISSN (Print)0737-8017

Other

Other23rd Annual ACM Symposium on Theory of Computing, STOC 1991
CountryUnited States
CityNew Orleans
Period5/5/915/8/91

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Constructing nonresidues in finite fields riemann hypothesis (Preliminary Version)'. Together they form a unique fingerprint.

Cite this