Learn · Computational Number Theory and Algebra
Lecture 29 of 29Week 12: Integer factoring. Pollard, Fermat, Morrison-Brillhart, Quadratic sieve methods.
Lecture 27: Pollard's p-1, Fermat, Morrison-Brillhart, Quadratic and Number field sieve methods
Prof. Nitin Saxena · IIT Kanpur
Credits and licence
- From
- Computational Number Theory and Algebra, IIT Kanpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Lecture 1: Introduction: Computation and Algebra
- Lecture 2: Background
- Lecture 3: GCD algorithm and Chinese Remainder Theorem
- Lecture 4: Fast polynomial multiplication
- Lecture 5: Fast polynomial multiplication (contd.)
- Lecture 6: Fast integer multiplication and division
- Lecture 7: Fast integer arithmetic and matrix multiplication
- Lecture 8: Matrix Multiplication Tensor.
- Lecture 9: Polynomial factoring over finite fields: Irreducibility testing
- Lecture 10: Equi-degree factorization and idea of Berlekamp's algorithm
- Lecture 11: Berlekamp's algorithm as a reduction method
- Lecture 12: Factoring over finite fields: Cantor-Zassenhaus algorithm
- 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
- Lecture 16: Bivariate polynomial factoring (continued)
- Lecture 17: Multivariate Polynomial Factorization
- Lecture 18: Multivariate Factoring - Hilbert's Irreducibility Theorem
- Lecture 19: Multivariate factoring (continued)
- Lecture 20: Analysis of LLL algorithm.
- Lecture 21: Analysis of LLL algorithm (continued)
- Lecture 22: Analysis of LLL-reduced basis algorithm and Introduction to NTRU cryptosystem
- Lecture 23: NTRU cryptosystem (continued) and Introduction to Primality testing
- Lecture 24: Randomized Primality testing: Solovay-Strassen and Miller-Rabin tests
- Lecture 25: Deterministic primality test (AKS) and RSA cryptosystem
- Lecture 26: Integer factoring: Smooth numbers and Pollard's rho method
- Lecture 27: Pollard's p-1, Fermat, Morrison-Brillhart, Quadratic and Number field sieve methods