Start
Announcements
Syllabus
References
Course notes
Exercises and tests
CNT in 2007

General information
Instructor: Abhijit Das
Teaching assistant: Santosh Ghosh
Timing: [Slot U] M 14:3016:25, Tu 13:3015:25
Venue: Room CSE119
LTP: 300
Credits: 3
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.
Announcements
First meeting (Jan 05, 2008)
The first meeting will be on Jan 07, 2008 (Monday), 14:30 hours, at CSE119.
There will be no class on Jan 08, 2008 (Tuesday).
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: Rootfinding and factorization,
LenstraLenstraLovasz 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, MillerRabin test, SolovayStrassen
test, AKS test.
 Integer factoring algorithms: Trial division, Pollard rho method,
p1 method, CFRAC method, quadratic sieve method, elliptic curve method.
 Computing discrete logarithms over finite fields: Babystepgiantstep method,
Pollard rho method, PohligHellman 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, SpringerVerlag.
 [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, SpringerVerlag.
 [9]
 A. Das and C. E. Veni Madhavan, Publickey cryptography: Theory and practice, Pearson Education Asia.
 [10]
 H. Cohen, A course in computational algebraic number theory, SpringerVerlag.

Course notes
Exercises and tests
Midsemester test: Feb 29, 2008, Questions, Solutions.
Endsemester test: Apr 29, 2008, Questions, Solutions.
