Uploaded February 2022 | Updated September 2026, 2 weeks ago

---

This lecture is part of my Berkeley math 115 course "Introduction to number theory"
For the other lectures in the course see youtube.com/playlist?list=PL8yHsr3EFj53L8sMbzIhhXSAOpuZ1Fov8

We discuss some methods for speeding up number theory calcuations on a computer.

Correction: the "modular" method to speed up multiplication mentioned in the lecture is only faster if one does many
calculations with these numbers (as in computing determinants) because the initial cost of reducing the input modulo many spall primes is still high.

The textbook is "An introduction to the theory of numbers" by Niven, Zuckerman, and Montgomery (5th edition).