Course page for CS5610 - Computational Number Theory and Algebra

Back to my homepage

Course Information

Course Slot: S (Tue 4:00-5:30 pm, Fri 2:30-4:00 pm), Classroom: A-117
List of topics: Euclid's algorithm, Bezout's lemma, prime numbers, fundamental theorem of arithmetic, congruences, Fermat's little theorem, the rings Zn and Zp, Lagrange's theorem, roots of unity, quadratic residues, quadratic equations in Zp, finite fields, applications of finite fields, univariate polynomial factorization in Zp, linear equations over Z, lattices, Hermite Normal Form, the LLL algorithm, polynomial factorization over Z, primality testing, integer factoring, the RSA cryptosystem, binary quadratic forms.

References:
1. Victor Shoup: A computational introduction to number theory and algebra
2. Neal Koblitz: A course in number theory and cryptography
3. Crandall and Pomerance: Prime numbers - A computational perspective
Other recommended books on Number Theory:
4. The Higher Arithmetic by Henry Davenport, 5. A Concise Introduction to the Theory of Numbers by Alan Baker, 6. An Introduction to the Theory of Numbers by Hardy and Wright 7. A course in number theory by H.E. Rose

Course Notes

Notes in progress Updated up to the class on 16/08/2022.

Assignments

HW 1 and Programming HW 1
Programming: We'll be working with numbers up to 512 bits. If you are writing in C/C++, you'll need a library for large number arithmetic.
See https://gmplib.org/ for the gmp library. Sample program: C (using gmp) , C++ (using gmp) , Python

Division of marks:

Attendance: 10, Assignments: 10, Programming Assignments: 30-40, Quizzes & Final Exam: 40-50

Academic Honesty Policy