Algorithms with Numbers

Overview

This course represents an introduction to algorithms with numbers, including linear algebra problems and arbitrary precision arithmetic, that appear virtually everywhere, from cryptography to audio processing. You will learn how to:
- implement the basic number theory algorithms like Euclidean algorithm that are basic building blocks for modern cryptography;
- work with large numbers arising in cryptography and high precision arithmetic;
- solve systems of linear equations that appear in many areas from designing electrical circuits to computer graphics;
- implement Fast Fourier Transform that is inevitable in signal processing.
Each module includes a programming assignment that will improve both your understanding of the topics and your programming skills.

Syllabus

Prime numbers and Euclid's Algorithm

In this module, you will practice implementing the basic number theory algorithms (such as the classical Euclid's algorithm) that are used millions of times every day as they are the basic building blocks of modern cryptography.

Arbitrary Precision Arithmetic and Polynomials

Many applications (including cryptographic ones) require arbitrary long numbers. In this module, you will practice implementing two techniques for working with large numbers: modular arithmetic and arbitrary precision arithmetic. Though some programming languages have built-in implementations for long integers, it is still important to be able to implement them on your own: first, you need to know the details of implementation to estimate the running time; second, in some cases you need to extend a built-in implementation for a particular task you face in practice. You will also practice implementing basic algorithms for working with polynomials.

Systems of Linear Equations

Solving systems of linear equations is important in various branches of mathematics and computer science: designing electrical circuits, analyzing random processes, constructing trend lines, to name just a few. In this module, you will practice implementing various methods for solving such systems.

Matrices and Fast Fourier Transform

In this module, we will see that the school method for integer multiplication is not optimal! We will implement together various algorithms for multiplying integers and matrices and will go through several practical applications of them.