RIEMANN HYPOTHESIS AND FINDING ROOTS OVER FINITE FIELDS.

Abstract

The author discusses deterministic polynomial time algorithm for finding roots of the reduction mod p of abelian integral polynomials, based on Generalized Riemann Hypothesis. The algorithm realizes the divide-and-conquer strategy via number theorectical methods. The generalized Riemann Hypothesis is used in establishing the existence of 'small' nonresidues in finite fields, a result essential to the algorithm. The proof of this result reveals an interesting connection between the power reciprocity law and the Generalized Riemann Hypothesis. However, the deterministic complexity of the general problem of finding roots over finite fields remains open.