TY - GEN
T1 - Constructing nonresidues in finite fields riemann hypothesis (Preliminary Version)
AU - Buchmann, Johannes
AU - Shoup, Victor
PY - 1991/1/3
Y1 - 1991/1/3
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=85031905133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031905133&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85031905133
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 72
EP - 79
BT - Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991
PB - Association for Computing Machinery
T2 - 23rd Annual ACM Symposium on Theory of Computing, STOC 1991
Y2 - 5 May 1991 through 8 May 1991
ER -