Topic: Computational number theory
Description: We will discuss algorithms for fundamental structures in number theory. There will be some emphasis on actual calculations with a computer algebra system such as sage. Topics to be covered include : Euclidean algorithm, rational reconstruction, Chinese remainder theorem, finite fields and fast modular arithmetic, solution of congruences, and randomized algorithms for primality testing, factoring integers and polynomials over finite fields. Applications in cryptography and coding theory will also be explored. Some more advanced topics such as Fast Fourier transforms, LLL lattice-basis reduction, p-adic numbers and AKS deterministic primality testing may also be covered.
Since this is a seminar course, the students will be doing most of the lecturing, with some help from me.
[02.10.2012] Here is a link to the textbook on Victor Shoup's webpage (we're using the 2nd edition).
[02.19.2012] Problem Set 1 has been posted on the homework page.
[02.28.2012] Problem Set 2 has been posted on the homework page.
[03.20.2012] Problem Set 3 has been posted on the homework page.
[04.11.2012] Problem Set 4 has been posted on the homework page.