Computational Mathematics

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.

Instructor: Curtis Bright
Course Code: COMP8920-1-R-2022F Selected Topics
Class: Mondays and Wednesdays 4:00–5:20 PM (Erie Hall 1114)
Office Hours: Fridays 9:00–11:00 AM (Lambton Tower 5110)
Webpage: cm.curtisbright.com

Lecture Notes

These notes have been archived since 2023. I recommend referring to the most recent notes as they may correct some typos.

• 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)

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

Exercises

• Exercise Worksheet 1
• Exercise Worksheet 2
• Exercise Worksheet 3
• Exercise: Break RSA!

Assessment

Assessment for the course will be based on a few things:

• Completing implementations of some of the algorithms that we discuss or related exercises (20%)
• Writing explanatory notes on topics related to the course that are of interest to you (30%)
• A final project that will consist of reviewing a paper or collection of papers and writing a report of around 10–15 pages (50%)

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. Maple has a free trial and I can provide you with a discount code if you are interested in purchasing an indefinite license or a license for the term.