Mondays: 11AM to 12PM (NAB 401), Tuesdays: 12PM to 1PM (NAB 403) 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:
Basic Number Theory: Introduction, Divisibility, Mathematical Induction, GCD, Extended GCD, Primes and their distribution, Theory of Congruences, Chinese Remainder Theorem, Fermat's little theorem and pseudoprimes, Euler's generalization of Fermat's theorem, Euler's phi function, Primitive roots and indices, Legendre symbol, Quadratic residues and non-residues, Quadratic reciprocity law.
Algorithms for integer arithmetic: Divisibility, gcd, Bezout's relation, modular arithmetic, fast integer arithmetic, modular exponentiation, Montgomery arithmetic, congruence, Hensel lifting, integer and modular square roots, prime number theorem, Reiman's hypothesis.
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 [Syllabus: Chapter 1 and Chapter 2]
End-sem (End of April): 60 marks