À propos de ce cours
16,827 consultations récentes

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Niveau débutant

Approx. 16 heures pour terminer

Recommandé : 4 weeks, 2-5 hours/week...


Sous-titres : Anglais, Grec

Compétences que vous acquerrez

Number TheoryCryptographyModular Exponentiation

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.

Niveau débutant

Approx. 16 heures pour terminer

Recommandé : 4 weeks, 2-5 hours/week...


Sous-titres : Anglais, Grec

Programme du cours : ce que vous apprendrez dans ce cours

4 heures pour terminer

Modular Arithmetic

In this week we will discuss integer numbers and standard operations on them: addition, subtraction, multiplication and division. The latter operation is the most interesting one and creates a complicated structure on integer numbers. We will discuss division with a remainder and introduce an arithmetic on the remainders. This mathematical set-up will allow us to created non-trivial computational and cryptographic constructions in further weeks.

10 vidéos (Total 90 min), 4 lectures, 13 quiz
10 vidéos
Numbers6 min
Divisibility6 min
Remainders9 min
Problems6 min
Divisibility Tests5 min
Division by 212 min
Binary System11 min
Modular Arithmetic12 min
Applications7 min
Modular Subtraction and Division11 min
4 lectures
Python Code for Remainders5 min
Slides1 min
Slides1 min
Slides1 min
12 exercices pour s'entraîner
Divisibility15 min
Remainders10 min
Division by 45 min
Four Numbers10 min
Division by 10110 min
Properties of Divisibility10 min
Divisibility Tests8 min
Division by 24 min
Binary System8 min
Modular Arithmetic8 min
Remainders of Large Numbers10 min
Modular Division10 min
4 heures pour terminer

Euclid's Algorithm

This week we'll study Euclid's algorithm and its applications. This fundamental algorithm is the main stepping-stone for understanding much of modern cryptography! Not only does this algorithm find the greatest common divisor of two numbers (which is an incredibly important problem by itself), but its extended version also gives an efficient way to solve Diophantine equations and compute modular inverses.

7 vidéos (Total 78 min), 4 lectures, 7 quiz
7 vidéos
Euclid’s Algorithm15 min
Extended Euclid’s Algorithm10 min
Least Common Multiple8 min
Diophantine Equations: Examples5 min
Diophantine Equations: Theorem15 min
Modular Division12 min
4 lectures
Greatest Common Divisor: Code15 min
Extended Euclid's Algorithm: Code10 min
Slides1 min
Slides10 min
7 exercices pour s'entraîner
Greatest Common Divisor10 min
Tile a Rectangle with Squares20 min
Least Common Multiple10 min
Least Common Multiple: Code15 min
Diophantine Equations15 min
Diophantine Equations: Code20 min
Modular Division: Code20 min
4 heures pour terminer

Building Blocks for Cryptography

Cryptography studies ways to share secrets securely, so that even eavesdroppers can't extract any information from what they hear or network traffic they intercept. One of the most popular cryptographic algorithms called RSA is based on unique integer factorization, Chinese Remainder Theorem and fast modular exponentiation. In this module, we are going to study these properties and algorithms which are the building blocks for RSA. In the next module we will use these building blocks to implement RSA and also to implement some clever attacks against RSA and decypher some secret codes.

14 vidéos (Total 91 min), 4 lectures, 6 quiz
14 vidéos
Prime Numbers3 min
Integers as Products of Primes3 min
Existence of Prime Factorization2 min
Euclid's Lemma4 min
Unique Factorization9 min
Implications of Unique Factorization10 min
Remainders7 min
Chinese Remainder Theorem7 min
Many Modules5 min
Fast Modular Exponentiation10 min
Fermat's Little Theorem7 min
Euler's Totient Function6 min
Euler's Theorem4 min
4 lectures
Slides10 min
Slides10 min
Fast Modular Exponentiation7 min
Slides10 min
5 exercices pour s'entraîner
Integer Factorization20 min
Remainders8 min
Chinese Remainder Theorem: Code15 min
Fast Modular Exponentiation: Code20 min
Modular Exponentiation8 min
5 heures pour terminer


Modern cryptography has developed the most during the World War I and World War II, because everybody was spying on everybody. You will hear this story and see why simple cyphers didn't work anymore. You will learn that shared secret key must be changed for every communication if one wants it to be secure. This is problematic when the demand for secure communication is skyrocketing, and the communicating parties can be on different continents. You will then study the RSA cryptosystem which allows parties to exchange secret keys such that no eavesdropper is able to decipher these secret keys in any reasonable time. After that, you will study and later implement a few attacks against incorrectly implemented RSA, and thus decipher a few secret codes and even pass a small cryptographic quest!

9 vidéos (Total 67 min), 4 lectures, 2 quiz
9 vidéos
One-time Pad4 min
Many Messages7 min
RSA Cryptosystem14 min
Simple Attacks5 min
Small Difference5 min
Insufficient Randomness7 min
Hastad's Broadcast Attack8 min
More Attacks and Conclusion5 min
4 lectures
Many Time Pad Attack10 min
Slides10 min
Randomness Generation10 min
Slides and External References10 min
2 exercices pour s'entraîner
RSA Quiz: Code2 h
RSA Quest - Quiz6 min
27 avisChevron Right


a commencé une nouvelle carrière après avoir terminé ces cours


a bénéficié d'un avantage concret dans sa carrière grâce à ce cours

Principaux examens pour Number Theory and Cryptography

par PWNov 22nd 2018

I was really impressed especially with the RSA portion of the course. It was really well explained, and the programming exercise was cleverly designed and implemented. Well done.

par LJan 2nd 2018

A good course for people who have no basic background in number theory , explicit clear explanation in RSA algorithm. Overall,a good introduction course.



Alexander S. Kulikov

Visiting Professor
Department of Computer Science and Engineering

Michael Levin

Computer Science

Vladimir Podolskii

Associate Professor
Computer Science Department

À propos de Université de Californie à San Diego

UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory....

À propos de Université nationale de recherche, École des hautes études en sciences économiques

National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communicamathematics, engineering, and more. Learn more on www.hse.ru...

À propos de la Spécialisation Introduction to Discrete Mathematics for Computer Science

Discrete Math is needed to see mathematical structures in the object you work with, and understand their properties. This ability is important for software engineers, data scientists, security and financial analysts (it is not a coincidence that math puzzles are often used for interviews). We cover the basic notions and results (combinatorics, graphs, probability, number theory) that are universally needed. To deliver techniques and ideas in discrete mathematics to the learner we extensively use interactive puzzles specially created for this specialization. To bring the learners experience closer to IT-applications we incorporate programming examples, problems and projects in our courses....
Introduction to Discrete Mathematics for Computer Science

Foire Aux Questions

  • Une fois que vous êtes inscrit(e) pour un Certificat, vous pouvez accéder à toutes les vidéos de cours, et à tous les quiz et exercices de programmation (le cas échéant). Vous pouvez soumettre des devoirs à examiner par vos pairs et en examiner vous-même uniquement après le début de votre session. Si vous préférez explorer le cours sans l'acheter, vous ne serez peut-être pas en mesure d'accéder à certains devoirs.

  • Lorsque vous vous inscrivez au cours, vous bénéficiez d'un accès à tous les cours de la Spécialisation, et vous obtenez un Certificat lorsque vous avez réussi. Votre Certificat électronique est alors ajouté à votre page Accomplissements. À partir de cette page, vous pouvez imprimer votre Certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez seulement lire et visualiser le contenu du cours, vous pouvez accéder gratuitement au cours en tant qu'auditeur libre.

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.