Computational Number Theory

CS60094, Spring 2026, LTP: 3-0-0

Class Timings	Mon: 11:00-11:55; TUE: 08:00-09:55

Venue	CSE 119
Instructor	Somindu Chaya Ramanna
Teaching assistants	Nibedita Dutta

Notices and Announcements

First class test scheduled on 16 February during class hour.
Syllabus for class test and mid-semester examination: arithmetic of integers (everything covered till 9th of February).
First Quiz to be held on 10 February during class hours.
Approval decisions for subject registration will be based on CGPA. Those who are not familiar with the course prerequisites (mentioned below) are strongly discouraged from joining this course.
Classes start on 5rd of January 2026.

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 -- multi-precision arithmetic, divisibility, gcd, modular arithmetic, linear congruences, Chinese remainder theorem, polynomial congruences and Hensel lifting, orders and primitive roots, quadratic residues.
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.
^§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.

^§ To be covered if time permits

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 Plan (tentative)

Mid-Semester Examination: 30%
End Semester Examination: 30%
TA (Class Tests + Quizzes): 40%

Lectures

Week	Date	Topics Covered
1	5 January	Introduction
1	6 January	Integer Arithmetic - Multiprecision Representation, Addition, Subtraction, Multiplication Fast Multiplication: Karatsuba-Offman, Toom-Cook
2	12 January	Fast Multiplication using Discrete Fourier Transforms
2	13 January	Euclidean Division for Multiprecision Numbers Divisibility, Euclid's Theorem, Bezout's relation Euclid's GCD, Extended Euclidean Algorithm
3	19 January	Congruences, Modular Arithmetic
3	20 January	Fast Modular Exponentiation, Barrett Reduction Linear Congruences, Chinese Remainder Theorem
4	26 January	No Class - Institute Holiday (Republic Day)
4	27 January	Polynomial Congruences, Hensel Lifting Quadratic Congruences: Legendre Symbol, Euler's Criterion
5	2 February	Quadratic Congruences: Jacobi Symbol
5	3 February	Multiplicative Orders, Primitive Roots, Computing Orders
6	9 February	Finding Square-roots: Tonelli-Shanks Algorithm
6	10 February	Finite Fields: Existence and Uniqueness Polynomial Basis Representation, Arithmetic Quiz 1
7	16 February	Test 1
7	17 February	No Class
	18 - 26 February	Mid-Semester Examination
8	2 March	Polynomial Arithmetic, Irreducible Polynomials
8	3 March	Properties: Multiplicative Orders, Normal Elements, Minimal Polynomials
9	9 March	Alternative Representations of Finite Fields
9	10 March	Computing Isomorphisms between Representations Counting Irreducible Polynomials of a certain degree
10	16 March
10	17 March
11	23 March
11	24 March
12	30 March
12	31 March	No Class - Institute Holiday (Mahavir Jayanti)
13	6 April
13	7 April
14	13 April
14	14 April
15	20 April
15	21 April
	20 - 30 April	End Semester Examination