This project investigates several aspects of the computational complexity of number theoretic problems. First, is the study of apparently intractable problems such as factoring, deciding quadratic residuosity, and the discrete logarithm. The goal is to find faster algorithms, both asymptotically and for "frontier" problem sizes. Second, the PI will explore the questions of how much randomness is necessary for the effective solution of number theoretic problems. Towards this end, measures of randomness utilization by algorithms will be developed. A subsequent goal is to establish that three problems i) primality testing ii) computation of square roots modulo a prime number, and iii) finding a quadratic nonresidue modulo a prime number, have effective algorithms with "low" randomness needs. Finally, this project will explore the complexity of proving statements about an integer N (e.g. "N has exactly 2 prime factors"), without revealing any information about N other than the fact that the target statement is true.
