Algorithms in Number Theory

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

This project will study the computational complexity of number-theoretic problems, which is relevant to both the theory and practive of computing. On the practical side, computational problems in number theory arise in the design of systems for random number generation, cryptography, and computer algebra. On the theoretical side, many of the classic questions about the relative power of various computational resources are crucial to number theory. For example, if randomization is not necessary for polynomial-time computation, then there is a fast deterministic test for primality. This work falls into four categories: a) designing improved models for the analysis of number-theoretic algorithms, b) improving statistical tests of heuristic models for number-theoretic algorithms, c) applying analytic and algebraic number theory to computations in number theory, and d) incorporating efficient algorithms into the teaching of elementary cryptography.