Constructing nonresidues in finite fields and the extended Riemann hypothesis |
| |
Authors: | Johannes Buchmann Victor Shoup |
| |
Institution: | Universität des Saarlandes, Fb 14 -- Informatik, PF 151150, 66041 Saarbrücken, Germany Victor Shoup ; Bellcore, 445 South St., Morristown, New Jersey 07960 |
| |
Abstract: | We present a new deterministic algorithm for the problem of constructing th power nonresidues in finite fields , where is prime and is a prime divisor of . We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed and , our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if is exponentially large. More generally, assuming the ERH, in time we can construct a set of elements that generates the multiplicative group . An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991. |
| |
Keywords: | |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|