Computational Number Theory
CS60094, Spring 2019, LTP: 3-0-0
Class Timings |
WED: 11:00-11:55; THUR: 12:00-12:55; FRI: 08:00-08:55 |
Venue |
CSE 107 |
Instructor |
Somindu Chaya Ramanna |
Teaching assistants |
Jaydeep Das, Mousam Roy, Urbi Chatterjee |
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 -- 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.
-
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.
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
The evaluation for this course will be based on a class test mid-sem, end-sem examinations and a term paper. Details are below.
50%: end-sem exam
30%: mid-sem exam
20%: class tests (best two out of 3)
Tests/Exams
Class test 1: Questions with solutions
MidSem: Questions with solutions
Class test 2: Questions with solutions
Class test 3: Questions with solutions
EndSem: Questions