Aspects of Algorithmic Number Theory

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Abstract for CCF-0635355, Aspects of Algorithmic Number Theory PI: Eric Bach This project deals with the design and analysis of algorithms for solving problems in number theory, and the mathematics that underlies these algorithms. Number-theoretic algorithms are basic to the nation's infrastructure, as they are used continually for public key encryption, encoding of messages to resist transmission errors, and pseudo-random number generation. They also form the innermost layer of any computer algebra system. In addition, many fundamental questions in computational complexity theory are linked to number theory. The research focuses on five specific areas: a) Arithmetic functions related to factoring and the uniform generation of decomposable objects; b) Optimality testing, including generalizations of Carmichael numbers; c) Algorithms for factoring polynomials over finite fields; d) Algorithms for discrete logarithms; e) Combinatorial computations of an arithmetic nature. Broader impacts of the research include helping to train the next generation of computationally oriented researchers, contributing to better systems for secure and reliable communication, and enhancing local computational infrastructure and local, national, and international intellectual collaboration.