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- Pari/GP for Linux, Mac OS X (source) and Windows (binary). You will also find links to documentation and others there. For Mac OS X binary you can also download from Fink.
- Pari/GP reference card.
- Pari/GP code snippets for Miller-Rabin, Baillie-PSW and polynomial rings. The second incorporates code to compute Lucas sequences by Marc Joye.

- Bernstein's paper and table.
- Granville's paper.
- The AKS paper (local mirror).
- Arnault's paper on the probabilistic Lucas test.
- Pomerance's paper on possible counterexamples to the BPSW test.

- Greene's work on the BPSW test.
- Pinch's list of Carmichael numbers up to 10
^{16}.

- Kichul Kim's notes on Miller-Rabin bases (problem 8, formula for |S|).
- Further notes on Miller-Rabin bases by Bach Bui, Kevin Hughes and Rob Selheimer (problem 8, divisibility of |G| by |S|).
- Even more notes on Miller-Rabin bases by Kevin Hughes (problem 6, bound for |S|).
- Notes on problem 3 by Kevin Hughes and Zach Jones.
- Kichul Kim's notes on problems 11, 12 and 13.
- Kevin Hughes's notes on problem 15.
- Kichul Kim's notes on generalization of Carmichaels.
- Notes on problem 19 (AKS conjecture) by Bach Bui, Kevin Hughes and Allison Moore.

- Problems list as of 6/17/05.
- The Prime Page (An Index of Information on Prime Numbers)
- EFF award.