).
Summer 2005 REU Computational Number Theory
The research experience for undergraduates (REU) is a six-week intensive course held the first summer session of the University of Texas at Austin. It is a chance for students to study a topic in modern mathematics, in a research setting.
The topic in 2005 was Computational Number Theory, taught by Professor
Felipe Voloch
(email
).
The focus of this REU was on computational issues in number theory with special regards to primality testing (that is, how does one check quickly whether a large number is prime?). We covered some of the standard tests, including the very efficient probabilistic test of Miller and Rabin and then we moved on to the AKS algorithm which proves that one can test primality in deterministic polynomial time, solving a long-standing problem. In addition to the theory we learned how to use the mathematical package Pari/GP to do these calculations with big numbers. We investigated some questions about how to make these algorithms even faster and whether AKS can be made practical.
Prerequisites: M328K Number Theory or equivalent. Some knowledge of Algebra at the level of M343K is useful but not essential.
Good references are:
R. Crandall, C. Pomerance: Prime Numbers - A Computational Perspective, Springer, 2001.
Dietzfelbinger, Martin: Primality Testing in Polynomial Time From Randomized Algorithms to "PRIMES Is in P"
Springer Lecture Notes in Computer Science , Vol. 3000, 2004,
Available online
Links
Pari/GP