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!
This course is part of the Introduction to Discrete Mathematics for Computer Science Specialization
Number Theory and Cryptography
Offered By
Introduction to Discrete Mathematics for Computer Science SpecializationAbout this Course
Learner Career Outcomes
50%
40%
Skills you will gain
Learner Career Outcomes
50%
40%
100% online
Course 4 of 5 in the
Flexible deadlines
Beginner Level
Approx. 17 hours to complete
English
Syllabus - What you will learn from this course
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.
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.
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.
Cryptography
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!
Reviews
4.6
TOP REVIEWS FROM NUMBER THEORY AND CRYPTOGRAPHY
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.
Final week is a bit rushed, think it would have benefited from being one week longer.\n\nNevertheless, an excellent introduction to an extremely difficult and complex subject.
Amazing course, learnt a lot. The assignments were a bit difficult [ and time consuming ] but they helped me gain a better understanding of the concepts.
A good course for people who have no basic background in number theory , explicit clear explanation in RSA algorithm. Overall,a good introduction course.
Good material and presentation from the professors. Programming exercises were a bit confusing at times. Overall, short but mathematically solid course.
My first experience with cryptography. The coding assignments are enough to make me think and ensure that I understood the concepts.
Excellent course, this course is more about numerical theory behind cryptography.\n\nIt has excellent assignments using Python.
Sometimes material is very dense. Watching in 1x speed multiple times advisable for some modules later in the course.
in a short 4 weeks, it explains the theory of RSA well and also the RSA itself.
Right amount off details with very simple and intuitive explanation.
good material, good presentation, very good problem sets. thank you!
Great course, just felt that the last quiz was a bit redundant.
About University of California San Diego
About National Research University Higher School of Economics
About the Introduction to Discrete Mathematics for Computer Science Specialization
Frequently Asked Questions
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.
