IIT Kanpur · Mathematics & Statistics

Computational Number Theory and Algebra

Prof. Nitin Saxena · 29 free video lectures

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…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1: Introduction: Computation and Algebra
  2. Lecture 2: Background
  3. Lecture 3: GCD algorithm and Chinese Remainder Theorem
  4. Lecture 4: Fast polynomial multiplication
  5. Lecture 5: Fast polynomial multiplication (contd.)
  6. Lecture 6: Fast integer multiplication and division
  7. Lecture 7: Fast integer arithmetic and matrix multiplication
  8. Lecture 8: Matrix Multiplication Tensor.
  9. Lecture 9: Polynomial factoring over finite fields: Irreducibility testing
  10. Lecture 10: Equi-degree factorization and idea of Berlekamp's algorithm
  11. Lecture 11: Berlekamp's algorithm as a reduction method
  12. Lecture 12: Factoring over finite fields: Cantor-Zassenhaus algorithm
  13. Lecture 5: Fast polynomial multiplication (contd.)
  14. Lecture 6: Fast integer multiplication and division
  15. Lecture 13: Reed Solomon Error Correcting Codes
  16. Lecture 14: List Decoding
  17. Lecture 15: Bivariate Factorization - Hensel Lifting
  18. Lecture 16: Bivariate polynomial factoring (continued)
  19. Lecture 17: Multivariate Polynomial Factorization
  20. Lecture 18: Multivariate Factoring - Hilbert's Irreducibility Theorem
  21. Lecture 19: Multivariate factoring (continued)
  22. Lecture 20: Analysis of LLL algorithm.
  23. Lecture 21: Analysis of LLL algorithm (continued)
  24. Lecture 22: Analysis of LLL-reduced basis algorithm and Introduction to NTRU cryptosystem
  25. Lecture 23: NTRU cryptosystem (continued) and Introduction to Primality testing
  26. Lecture 24: Randomized Primality testing: Solovay-Strassen and Miller-Rabin tests
  27. Lecture 25: Deterministic primality test (AKS) and RSA cryptosystem
  28. Lecture 26: Integer factoring: Smooth numbers and Pollard's rho method
  29. Lecture 27: Pollard's p-1, Fermat, Morrison-Brillhart, Quadratic and Number field sieve methods

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights