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