Modular algorithms apply the Chinese remainder theorem to speed up a computation involving polynomials with integer or rational coefficients. They also apply polynomial evaluation and interpolation to speed up a computation involving multivariate polynomials. In the case of the Euclidean algorithm, they are used to avoid the phenomenon of intermediate expression swell.
Michael Monagan, Simon Fraser University (4 lectures, 8 hours)
Lecture 1 : Ring homomorphisms, the Schwartz-Zippel Lemma. The Chinese remainder theorem and algorithm.
Video Lec8Anotes.pdf Lec8Bnotes.pdf Lec8Handouts.zipLecture 2 : A modular algorithm for multiplication in ℤ[x]. Polynomial interpolation, homomorphic imaging.
Video Lec9Anotes.pdf Lec9Bnotes.pdf Lec9Cnotes.pdf Lec9Handouts.zipLecture 3 : The modular GCD algorithm.
Video Lec11Anotes.pdf Lec11Bnotes.pdf Lec11Cnotes.pdf Lec11Handouts.zipLecture 4 : Cost of the modular GCD algorithm. The Sylvester resultant and unlucky primes.
Video Lec12Anotes.pdf Lec12Bnotes.pdf Lec12Cnotes.pdf