CS60082 Computational Number Theory: Spring 2011

CS60082/CS60094 Computational Number Theory

Spring 2011

General Information

Instructor: Abhijit Das
Slot: U (Monday 14:30-16:25, Tuesday: 13:30-15:25)
Venue: CSE 120, CSE Department
Teaching Assistants: Pratyay Mukherjee, Satrajit Ghosh, Somnath Ghosh.

Notices and Announcements

February 14, 2011: The mid-semester test will be conducted centrally. The date is Feb 21, 2011 (Monday), 09:00--11:00am. CS60082 students will go to Room V1, and CS60094 students to Room V2. The mid-semester test will be a conventional test (that is, closed-book and closed-time).
February 14, 2011: Class Test 1 is rescheduled to Feb 16, 2011 (Wednesday), 6:00--7:00pm. The venue is F-116 (Bhatnagar auditorium). As per popular demand, the class test will be open-notes.
February 02, 2011: Class Test 1 scheduled on Feb 11, 2011 (Friday) cannot be conducted, since all usable rooms in the department and in the central pool (main building and Vikramshila complex) are booked on that evening. The only viable option seems like shifting the test to Feb 15, 2011 (Tuesday).
January 03, 2011: Each student (UG or PG) may register for either CS60082 or CS60094 (but not both) in the ERP system.

Prerequisites

I will mercilessly assume that a student registering for this course is equipped with rudimentary knowledge of discrete mathematical structures (groups, rings, fields), algorithms (design and analysis techniques), and probability. Students lacking one or more of these backgrounds may find the exposition difficult to follow. I will, under no circumstances, entertain requests to cover these elementary topics in this course. Note, however, that no prior acquaintance with number theory (elementary, analytic, or algebraic) is necessary for attending this course.

Syllabus

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.

References

[1]      V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press.
[2]      M. Mignotte, Mathematics for computer algebra, Springer-Verlag.
[3]      I. Niven, H. S. Zuckerman and H. L. Montgomery, An introduction to the theory of numbers, John Wiley.
[4]      J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge University Press.
[5]      R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press.
[6]      A. J. Menezes, editor, Applications of finite fields, Kluwer Academic Publishers.
[7]      J. H. Silverman and J. Tate, Rational points on elliptic curves, Springer International Edition.
[8]      D. R. Hankerson, A. J. Menezes and S. A. Vanstone, Guide to elliptic curve cryptography, Springer-Verlag.
[9]      A. Das and C. E. Veni Madhavan, Public-key cryptography: Theory and practice, Pearson Education Asia.
[10]      H. Cohen, A course in computational algebraic number theory, Springer-Verlag.

Exercises and tests

Class Test: Feb 16, 2011
Questions | Solutions
Mid-Semester Test: Feb 21, 2011
Questions | Solutions
End-Semester Test: Apr 25, 2011
Questions | Solutions

[1]	V. Shoup, A computational introduction to number theory and algebra, Cambridge University Press.
[2]	M. Mignotte, Mathematics for computer algebra, Springer-Verlag.
[3]	I. Niven, H. S. Zuckerman and H. L. Montgomery, An introduction to the theory of numbers, John Wiley.
[4]	J. von zur Gathen and J. Gerhard, Modern computer algebra, Cambridge University Press.
[5]	R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Cambridge University Press.
[6]	A. J. Menezes, editor, Applications of finite fields, Kluwer Academic Publishers.
[7]	J. H. Silverman and J. Tate, Rational points on elliptic curves, Springer International Edition.
[8]	D. R. Hankerson, A. J. Menezes and S. A. Vanstone, Guide to elliptic curve cryptography, Springer-Verlag.
[9]	A. Das and C. E. Veni Madhavan, Public-key cryptography: Theory and practice, Pearson Education Asia.
[10]	H. Cohen, A course in computational algebraic number theory, Springer-Verlag.