Mondays: 11AM to 12PM (NAB 401), Tuesdays: 12PM to 1PM (NAB 401) and Thursdays: 9AM to 10AM (NAB 401)
Class overview
In this course we will learn about the number theory algorithms and algebra of computers. This is a heavily mathematically exposed course. A good grasp in mathematics is highly required.
Syllabus:
Introduction to Number Theory and Computational Number Theory.
Algorithms for integer arithmetic: Divisibility, gcd, modular arithmetic, modular exponentiation, Montgomery arithmetic, congruence, Chinese remainder theorem, Hensel lifting, orders and primitive roots, quadratic residues, integer and modular square roots, prime number theorem, continued fractions and rational approximations.
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, Lenstra-Lenstra-Lovasz algorithm, polynomials over finite fields.
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.
Books:
[1]* A. Das, Computational number theory, Chapman and Hall/CRC.
[2]* V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press.
[3] M. Mignotte, Mathematics for computer algebra, Springer-Verlag.
[4] I. Niven, H. S. Zuckerman and H. L. Montgomery, An introduction to the theory of numbers, John Wiley.
[5]* David Burton, Elementary Number Theory, McGraw Hill.
*-marked books will be mostly followed.
References:
Evaluation:
Continuous Assessments: 15 Marks
Mid-sem (End of February): 25 Marks
End-sem (End of April): 60 marks