Computational Number Theory

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

Class Timings	WED: 12:00-12:55; THUR: 11:00-11:55; FRI: 09:00-09:55

Venue	CSE 107
Instructor	Somindu Chaya Ramanna
Teaching assistants	Sayani Sinha

Notices and Announcements

Class Test 1 to be held from 9 AM to 10 AM (during the regular class hour) on Friday, the 7th of February.
Class on 24 January cancelled due to Spring Fest
No class on 17 January due to compensatory holiday
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 3rd of January 2025.

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 Sem: 30%
End Sem: 50%
TA: 20%

Lectures

Week	Date	Topics
1	3 January	Introduction
2	8 January	Integer Arithmetic - Multiprecision Representation, Addition, Subtraction, Multiplication
	9 January	Euclidean Division, Karatsuba-Offman, Toom-Cook Multiplication
	10 January	FFT-based Multiplication
3	15 January	Euclid's GCD, Extended Euclidean Algorithm
	16 January	Congruences, Modular Arithmetic
	17 January	No Class - Compensatory Holiday
4	22 January	Fast Modular Exponentiation, Barrett Reduction
	23 January	Linear Congruences, Chinese Remainder Theorem, Polynomial Congruences, Hensel Lifting
	24 January	No Class - Spring Fest
5	29 January	Hensel Lifting (contd.), Quadratic Congruences, Legendre Symbol, Euler's Criterion
	30 January	Jacobi symbol, Multiplicative Orders and Primitive Roots
	31 January	Introduction to Finite Fields - Existence and Uniqueness

Practice Problems

Problem Set 1