Course page for CS5610 - Computational Number Theory and Algebra
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.
Course Slot: S
(Tue 4:00-5:30 pm, Fri 2:30-4:00 pm),
List of topics:
Euclid's algorithm, Bezout's lemma, prime numbers, fundamental theorem of arithmetic, congruences,
Fermat's little theorem, the rings Zn
, 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.
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
See https://gmplib.org/ for the gmp library.
C (using gmp) ,
C++ (using gmp) ,
Division of marks:
Attendance: 10, Assignments: 10, Programming Assignments: 30-40,
Quizzes & Final Exam: 40-50