Course page for CS5610 - Computational Number Theory and Algebra

Back to my teaching page

Course Information

Course Slot: E (Tue 10:00-11:00, Thu 12:00-13:00, Fri 09:00-10:00)
Classroom: CS-LH1
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, polynomial factorization over Z, primality testing, integer factoring, binary quadratic forms.

References:
1. Course Notes (in progress)
2. Victor Shoup: A computational introduction to number theory and algebra
3. Crandall and Pomerance: Prime numbers - A computational perspective
4. Neal Koblitz: A course in number theory and cryptography
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

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 programs for trial division: C (using gmp) , C++ (using gmp) , Python
Also see: Sage software

Division of marks:

Assignments: 10, Programming Assignments: 35, Quizzes: 15 & Final Exam: 40

Academic Honesty Policy