Course11110413829 lectures
Computational Number Theory and Algebra
Prof. Nitin Saxena · IIT Kanpur
About
Algebra plays an important role in both finding algorithms, and understanding the limitations of computation. This course will focus on some of the fundamental algebraic concepts that arise in computation, and the algebraic algorithms that have applications in real life. The course will cover the problems of fast integer (or polynomial) multiplication (or factoring), fast matrix multiplication, primality testing, computing discrete logarithm, error-correcting codes, lattice- based cryptography, etc. The course intends to introduce both basic concepts and practical applications.
INTENDED AUDIENCE : Computer Science & Engineering, Mathematics, Electronics, Physics, & similar disciplines.
PREREQUISITES : Preferable (but not necessary)-- Theory of Computation, Algorithms, Algebra
Theory of Computation:
https://nptel.ac.in/courses/106104148
https://nptel.ac.in/courses/106106242
Fundamental Algorithms:Design and Analysis:
https://nptel.ac.in/courses/106105157
Algebra - I:
https://nptel.ac.in/courses/111106137
Lectures
Week 1: Outline. Notation. Background.
Week 2: GCD. Chinese Remaindering. Fast polynomial multiplication.
Week 3: Fast integer multiplication. Fast integer division. Fast gcd.
- Lecture 5: Fast polynomial multiplication (contd.)
- Lecture 6: Fast integer multiplication and division
Week 4: Fast matrix multiplication. Tensor rank.
- Lecture 7: Fast integer arithmetic and matrix multiplication
- Lecture 8: Matrix Multiplication Tensor.
Week 5: Factorization over finite fields.
- Lecture 9: Polynomial factoring over finite fields: Irreducibility testing
- Lecture 10: Equi-degree factorization and idea of Berlekamp's algorithm
Week 6: Berlekamp, Cantor-Zassenhaus factoring algorithms.
- Lecture 11: Berlekamp's algorithm as a reduction method
- Lecture 12: Factoring over finite fields: Cantor-Zassenhaus algorithm
Week 7
- Lecture 5: Fast polynomial multiplication (contd.)
- Lecture 6: Fast integer multiplication and division
- Lecture 13: Reed Solomon Error Correcting Codes
- Lecture 14: List Decoding
- Lecture 15: Bivariate Factorization - Hensel Lifting
Week 8: Kaltofen's blackbox multivariate factoring.
- Lecture 16: Bivariate polynomial factoring (continued)
- Lecture 17: Multivariate Polynomial Factorization
- Lecture 18: Multivariate Factoring - Hilbert's Irreducibility Theorem
Week 9: Integral polynomial factoring. LLL algo. Shortest vector in lattice.
- Lecture 19: Multivariate factoring (continued)
- Lecture 20: Analysis of LLL algorithm.
- Lecture 21: Analysis of LLL algorithm (continued)
Week 10: Lattice-based cryptography.
- Lecture 22: Analysis of LLL-reduced basis algorithm and Introduction to NTRU cryptosystem
- Lecture 23: NTRU cryptosystem (continued) and Introduction to Primality testing
Week 11: Primality testing. RSA cryptosystem. Diffie-Hellman. Discrete Log.
- Lecture 24: Randomized Primality testing: Solovay-Strassen and Miller-Rabin tests
- Lecture 25: Deterministic primality test (AKS) and RSA cryptosystem
Week 12: Integer factoring. Pollard, Fermat, Morrison-Brillhart, Quadratic sieve methods.
Syllabus and materials
At NPTEL, as the course publishes them.
Credits and licence
- Institution
- IIT Kanpur
- Department
- Mathematics
- Teacher
- Prof. Nitin Saxena
- Level
- Undergraduate
- Language
- English
- Subjects
- Mathematics
- Source
- NPTEL
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed