This is a renewal project to investigate the compuational complexity of number-theoretic problems. Besides providing a number of unsolved problems in complexity theory, number theory is useful in the design of systems for random number generation, cryptography, and computer algebra. The investigations fall into three categories: a) Exploration of the algorithmic consequences of heuristic assumptions such as the Extended Riemann Hypothesis. b) Analysis and design of number-theoretic algorithms, with special attention being paid to efficient randomized algorithms for primality, factorization of polynomials, etc. c) Applications of algebraic geometry (especially the theory of varieties over finite fields) to constructives techniques.
