## COURSE DESCRIPTION

**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.

## RECENT UPDATES

**[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.