Computational Number Theory

CS60094, Spring 2020, LTP: 3-0-0

Prerequisites

I assume basic familiarity with probability theory, algebraic structures (groups, rings, fields), linear algebra and algorithms. These topics will not be covered in the course. No prior exposure to number theory is necessary.

Syllabus (Tentative)

• Arithmetic of Integers -- multi-precision arithmetic, divisibility, gcd, modular arithmetic, modular exponentiation, linear congruences, Chinese remainder theorem, polynomial congruences and Hensel lifting, orders and primitive roots, quadratic residues, modular square roots.
• Representation of finite fields -- Prime and extension fields, representation of extension fields, polynomial basis, primitive elements, normal basis, optimal normal basis, irreducible polynomials.
• Algorithms for polynomials -- root-finding and factorization, polynomials over finite fields, Lenstra-Lenstra-Lovasz algorithm.
• Elliptic curves -- The elliptic curve group, elliptic curves over finite fields, Schoof's point counting algorithm.
• Primality testing algorithms -- Fermat test, Miller-Rabin test, Solovay-Strassen test, AKS test.
• Integer factoring algorithms -- Trial division, Pollard rho method, p-1 method, CFRAC method, quadratic sieve method, elliptic curve method.
• Computing discrete logarithms over finite fields -- Baby-step-giant-step method, Pollard rho method, Pohlig-Hellman method, index calculus methods, linear sieve method, Coppersmith's algorithm.
• Applications -- Algebraic coding theory, cryptography.

Announcements

• Class on 26th February cancelled
• Class Test 1: 13th Feb from 8PM -- 9PM at CSE 119/120
• Tutorial on 7th Feb at CSE 107 from 5PM -- 6PM
• Extra class on 1st Feb at CSE 107 from 5PM -- 6PM
• Classes start on 3rd of January, 2020

References

• A. Das, Computational Number Theory, CRC Press. [Main Text]
• V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press.
• H. Cohen, A course in computational algebraic number theory, Springer-Verlag.
• J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge University Press.
• J. H. Silverman and J. Tate, Rational points on elliptic curves, Springer International Edition.
• I. Niven, H. S. Zuckerman and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley and Sons.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press.
• J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge University Press.

Evaluation

Solutions for Tests/Exams

Practice Problems