This project addresses the design and analysis of algorithms in number theory. It focuses on three subareas in detail: problems related to the prime factorization of integers, the behavior of iterated maps on finite algebraic objects such as fields and rings, and the exploitation of ideas from combinatorics and analytic number theory to further our knowledge about polynomial factoring.
The problems studied in this project are among the most important in computational number theory, and provide key examples for computational complexity theory and the emerging theory of quantum computing. Algorithms to solve these problems are also extremely useful for secure and reliable electronic communication, for computer algebra, and for pseudo-random number generation. Results obtained in the project will have the potential to impact all of the above areas. They will also enhance the connections between theoretical computer science and pure mathematics. This is because the behavior of number-theoretic algorithms is intimately connected to significant questions in analytic number theory, algebraic geometry, probability theory, and dynamical systems.
A key component of the project is graduate student support. Such aid, in the form of research assistantships supervised by the PI, will help maintain the pipeline of algorithmically trained researchers in the mathematical sciences. The project will also help integrate research and teaching, by helping him to develop and publicize interdisciplinary courses and seminars on topics such as applied number theory, communication technology, and quantum computation.
