Computational Mathematics

Instructor: Curtis Bright

This class provides a broad introduction to discrete computational mathematics with a focus on symbolic computation.

That is, we cover how to effectively do mathematics on computers. This involves topics such as:

• Using a computer algebra system like Maple or Sage
• Algorithms for performing arithmetic on polynomials and arbitrarily large integers
• Solving linear Diophantine equations and the extended Euclidean algorithm
• Efficient modular arithmetic and the Chinese remainder algorithm
• Primality testing and factorization
• Polynomial evaluation and interpolation
• Karatsuba multiplication, fast multiplication, and the discrete Fourier transform
• Fast division and Newton iteration
• Satisfiability solving and the Davis–Putnam–Logemann–Loveland procedure

A number of applications of these topics will be discussed, such as to coding theory, cryptography, and computer-assisted proofs.

Lecture Notes

1. Sage Introduction (pdf, ipynb)
2. Basic Algebraic Operations (pdf, ipynb)
3. The Euclidean Algorithm (pdf, ipynb)
4. Modular Arithmetic (pdf, ipynb)
5. Cryptography and Coding Theory (pdf, ipynb)
6. Finite Fields and Reed–Solomon Codes (pdf, ipynb)
7. Satisfiability Solving (pdf, ipynb)
8. Polynomial Evaluation and Interpolation (pdf, ipynb)
9. Fast Multiplication and the Discrete Fourier Transform (pdf, ipynb)
10. Primality Testing and Factoring (pdf, ipynb)
11. A Modular Euclidean Algorithm (pdf, ipynb)
12. Factoring Polynomials (pdf, ipynb)

The lectures roughly cover the first eight chapters of Modern Computer Algebra as well as chapters 14 and 18 to 20. A few topics do not appear in MCA (such as satisfiability solving).

References

There is no required textbook for the course, but the following books are excellent references:

• Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard
• A Computational Introduction to Number Theory and Algebra by Victor Shoup (freely available)
• Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance

Software

Programming in this class will be done in either Maple or Sage. Maple is a commercial computer algebra system developed by Maplesoft. Sage is a computer algebra system that is freely available and runs on Linux, Windows, and MacOS.

Previous Versions

The course was also taught in 2022 and 2021.