Este curso faz parte do Programa de cursos integrados Introduction to Discrete Mathematics for Computer Science

oferecido por

University of California San Diego

National Research University Higher School of Economics

Programa de cursos integrados Introduction to Discrete Mathematics for Computer Science

University of California San Diego

Informações sobre o curso

4.6

93 classificações

•

21 avaliações

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.

Comece imediatamente e aprenda em seu próprio cronograma.

Redefinir os prazos de acordo com sua programação.

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

Legendas: Inglês

Number TheoryCryptographyModular Exponentiation

Comece imediatamente e aprenda em seu próprio cronograma.

Redefinir os prazos de acordo com sua programação.

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

Legendas: Inglês

Semana

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 vídeos (total de (Total 90 mín.) min), 4 leituras, 13 testes

Numbers6min

Divisibility6min

Remainders9min

Problems6min

Divisibility Tests5min

Division by 212min

Binary System11min

Modular Arithmetic12min

Applications7min

Modular Subtraction and Division11min

Python Code for Remainders5min

Slides1min

Slides1min

Slides1min

Divisibility15min

Remainders10min

Division by 45min

Four Numbers10min

Division by 10110min

Properties of Divisibility10min

Divisibility Tests8min

Division by 24min

Binary System8min

Modular Arithmetic8min

Remainders of Large Numbers10min

Modular Division10min

Semana

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 vídeos (total de (Total 78 mín.) min), 4 leituras, 7 testes

Euclid’s Algorithm15min

Extended Euclid’s Algorithm10min

Least Common Multiple8min

Diophantine Equations: Examples5min

Diophantine Equations: Theorem15min

Modular Division12min

Greatest Common Divisor: Code15min

Extended Euclid's Algorithm: Code10min

Slides1min

Slides10min

Greatest Common Divisor10min

Tile a Rectangle with Squares20min

Least Common Multiple10min

Least Common Multiple: Code15min

Diophantine Equations15min

Diophantine Equations: Code20min

Modular Division: Code20min

Semana

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 vídeos (total de (Total 91 mín.) min), 3 leituras, 6 testes

Introduction7min

Prime Numbers3min

Integers as Products of Primes3min

Existence of Prime Factorization2min

Euclid's Lemma4min

Unique Factorization9min

Implications of Unique Factorization10min

Remainders7min

Chinese Remainder Theorem7min

Many Modules5min

Fast Modular Exponentiation10min

Fermat's Little Theorem7min

Euler's Totient Function6min

Euler's Theorem4min

Slides10min

Slides10min

Slides10min

Integer Factorization20min

Remainders8min

Chinese Remainder Theorem15min

Fast Modular Exponentiation15min

Modular Exponentiation8min

Semana

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 vídeos (total de (Total 67 mín.) min), 4 leituras, 2 testes

Cryptography7min

One-time Pad4min

Many Messages7min

RSA Cryptosystem14min

Simple Attacks5min

Small Difference5min

Insufficient Randomness7min

Hastad's Broadcast Attack8min

More Attacks and Conclusion5min

Many Time Pad Attack10min

Slides10min

Randomness Generation10min

Slides and External References10min

RSA Quizmin

RSA Quest - Quiz6min

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

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

Quando terei acesso às palestras e às tarefas?

Ao se inscrever para um Certificado, você terá acesso a todos os vídeos, testes e tarefas de programação (se aplicável). Tarefas avaliadas pelos colegas apenas podem ser enviadas e avaliadas após o início da sessão. Caso escolha explorar o curso sem adquiri-lo, talvez você não consiga acessar certas tarefas.

O que recebo ao me inscrever nesta Especialização?

Quando você se inscreve no curso, tem acesso a todos os cursos na Especialização e pode obter um certificado quando concluir o trabalho. Seu Certificado eletrônico será adicionado à sua página de Participações e você poderá imprimi-lo ou adicioná-lo ao seu perfil no LinkedIn. Se quiser apenas ler e assistir o conteúdo do curso, você poderá frequentá-lo como ouvinte sem custo.

Qual é a política de reembolso?

Existe algum auxílio financeiro disponível?

Mais dúvidas? Visite o Central de Ajuda ao Aprendiz.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.