**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.

- Sage Introduction (pdf, ipynb)
- Basic Algebraic Operations (pdf, ipynb)
- The Euclidean Algorithm (pdf, ipynb)
- Modular Arithmetic (pdf, ipynb)
- Cryptography and Coding Theory (pdf, ipynb)
- Finite Fields and Reed–Solomon Codes (pdf, ipynb)
- Satisfiability Solving (pdf, ipynb)
- Polynomial Evaluation and Interpolation (pdf, ipynb)
- Fast Multiplication and the Discrete Fourier Transform (pdf, ipynb)
- Primality Testing and Factoring (pdf, ipynb)
- A Modular Euclidean Algorithm (pdf, ipynb)
- Factoring Polynomials (pdf, ipynb)

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

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

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.