Allotted Class Slot | WED: 11:00-11:55; THUR: 12:00-12:55 †; FRI: 08:00-08:55 |
† Tutorial Interactive session during one of the other two class hours (students will be notified regarding the same) |
|
Instructor | Somindu Chaya Ramanna |
Teaching assistants | Aditya Anand |
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.
Topic | Subtopic | Links |
---|---|---|
Introduction | -- | Video | Board work |
Arithmetic of Integers | Basic Arithmetic on Multi-Precision Integers | Videos: Part 1 Part 2 | Board work |
Fast Multiplication | Video | Board work | |
Divisibility, GCD, Extended GCD | Video | Board work | |
Congruences, Residue Systems, Modular Arithmetic, Euler's Totient Function, Euler's Theorem, Fermat's Little Theorem, Modular Exponentiation, Barrett Reduction |
Videos: Part 1, Part 2 | Board work: Part 1, Part 2 | |
Linear Congruences, Chinese Remainder Theorem | Video | Board work | |
Polynomial Congruences, Hensel Lifting | Video | Board work | |
Quadratic Congruences, Quadratic (Non-)Residues, Legendre Symbol, Jacobi Symbol, Quadratic Reciprocity Law | Videos: Part 1, Part 2 | Board work | |
Multiplicative Order, Primitive Roots | Video | Board work | |
Arithmetic of Finite Fields | Existence and Uniqueness | Video | Board work |
Representation and Basic Arithmetic: polynomial basis representation, arithmetic operations, choice of defining polynomial | Video | Board work | |
Some Properties of Finite Fields: order, primitive elements, normal elements, minimal polynomials | Video | Board work | |
Alternative Representations: arbitrary bases, normal bases, discrete logarithm representation, towers of extensions, isomorphisms bettween representations | Video | Board work |