YoVDO

Algorithms with Numbers

Offered By: Saint Petersburg State University via Coursera

Tags

Algorithms and Data Structures Courses Programming Courses Cryptography Courses Signal Processing Courses Polynomials Courses Fast Fourier Transform Courses Modular Arithmetic Courses

Course Description

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.

Taught by

Alexander S. Kulikov, Nikolai Vavilov, Victor Petrov and Aliaksei Tolstsikau

Tags

Related Courses

Certified Ethical Hacker (CEH) - Linux Academy's Prep Course
A Cloud Guru
Certified Information Systems Security Professional (CISSP)
A Cloud Guru
CompTIA Security+ Certification Prep
A Cloud Guru
Encryption Fundamentals
A Cloud Guru
LPIC-3 Exam 303: Security
A Cloud Guru