This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization

Offered By

University of California San Diego

National Research University Higher School of Economics

Introduction to Discrete Mathematics for Computer Science Specialization

University of California San Diego

About this Course

4.6

93 ratings

•

21 reviews

We all learn numbers from the childhood. Some of us like to count, others hate it, but any person uses numbers everyday to buy things, pay for services, estimated time and necessary resources. People have been wondering about numbers’ properties for thousands of years. And for thousands of years it was more or less just a game that was only interesting for pure mathematicians. Famous 20th century mathematician G.H. Hardy once said “The Theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the word nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to e-mail and other personal services. In this short course, we will make the whole journey from the foundation to RSA in 4 weeks. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest!
As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 4 weeks, 2-5 hours/week...

Subtitles: English

Number TheoryCryptographyModular Exponentiation

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 4 weeks, 2-5 hours/week...

Subtitles: English

Week

1In 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 videos (Total 90 min), 4 readings, 13 quizzes

Numbers6m

Divisibility6m

Remainders9m

Problems6m

Divisibility Tests5m

Division by 212m

Binary System11m

Modular Arithmetic12m

Applications7m

Modular Subtraction and Division11m

Python Code for Remainders5m

Slides1m

Slides1m

Slides1m

Divisibility15m

Remainders10m

Division by 45m

Four Numbers10m

Division by 10110m

Properties of Divisibility10m

Divisibility Tests8m

Division by 24m

Binary System8m

Modular Arithmetic8m

Remainders of Large Numbers10m

Modular Division10m

Week

2This 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 videos (Total 78 min), 4 readings, 7 quizzes

Euclid’s Algorithm15m

Extended Euclid’s Algorithm10m

Least Common Multiple8m

Diophantine Equations: Examples5m

Diophantine Equations: Theorem15m

Modular Division12m

Greatest Common Divisor: Code15m

Extended Euclid's Algorithm: Code10m

Slides1m

Slides10m

Greatest Common Divisor10m

Tile a Rectangle with Squares20m

Least Common Multiple10m

Least Common Multiple: Code15m

Diophantine Equations15m

Diophantine Equations: Code20m

Modular Division: Code20m

Week

3Cryptography 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 videos (Total 91 min), 3 readings, 6 quizzes

Prime Numbers3m

Integers as Products of Primes3m

Existence of Prime Factorization2m

Euclid's Lemma4m

Unique Factorization9m

Implications of Unique Factorization10m

Remainders7m

Chinese Remainder Theorem7m

Many Modules5m

Fast Modular Exponentiation10m

Fermat's Little Theorem7m

Euler's Totient Function6m

Euler's Theorem4m

Slides10m

Slides10m

Slides10m

Integer Factorization20m

Remainders8m

Chinese Remainder Theorem15m

Fast Modular Exponentiation15m

Modular Exponentiation8m

Week

4Modern 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 videos (Total 67 min), 4 readings, 2 quizzes

One-time Pad4m

Many Messages7m

RSA Cryptosystem14m

Simple Attacks5m

Small Difference5m

Insufficient Randomness7m

Hastad's Broadcast Attack8m

More Attacks and Conclusion5m

Many Time Pad Attack10m

Slides10m

Randomness Generation10m

Slides and External References10m

RSA Quizs

RSA Quest - Quiz6m

4.6

21 ReviewsBy PW•Nov 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.

By L•Jan 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.

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

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 communications, IT, mathematics, engineering, and more.
Learn more on www.hse.ru...

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

When will I have access to the lectures and assignments?

Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

What will I get if I subscribe to this Specialization?

When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

What is the refund policy?

Is financial aid available?

More questions? Visit the Learner Help Center.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.