- Level Foundation
- Duration 17 hours
- Course by University of California San Diego
-
Offered by
About
A prominent expert in the number theory Godfrey Hardy described it in the beginning of 20th century 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 world 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 course we will start with the basics of the number theory and get to cryptographic protocols based on it. 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.Modules
Divisibility
8
Assignment
- Divisibility
- Puzzle: Take the last rock
- Division by 101
- Remainders
- Division by 4
- Four Numbers
- Properties of Divisibility
- Divisibility Tests
5
Readings
- Numbers
- Divisibility
- Remainders
- Problems
- Divisibility Tests
Modular Arithmetic
3
Assignment
- Modular Arithmetic
- Remainders of Large Numbers
- Modular Division
3
Readings
- Modular Arithmetic
- Applications
- Modular Subtraction and Division
Euclid's Algorithm
2
Assignment
- Greatest Common Divisor
- Tile a Rectangle with Squares
3
Videos
- Greatest Common Divisor
- Euclid’s Algorithm
- Extended Euclid’s Algorithm
3
Readings
- Greatest Common Divisor: Code
- Extended Euclid's Algorithm: Code
- Slides
Applications
5
Assignment
- Least Common Multiple
- Least Common Multiple: Code
- Diophantine Equations
- Diophantine Equations: Code
- Modular Division: Code
4
Videos
- Least Common Multiple
- Diophantine Equations: Examples
- Diophantine Equations: Theorem
- Modular Division
1
Readings
- Slides
Integer Factorization
2
Assignment
- Puzzle: Arrange Apples
- Integer Factorization
5
Readings
- Introduction
- Prime Numbers
- Factoring: Existence
- Factoring: Uniqueness
- Unique Factoring: Consequences
Chinese Remainder Theorem
2
Assignment
- Remainders
- Chinese Remainder Theorem: Code
2
Readings
- Remainders for Two Modulo Values
- Chinese Remainder Theorem
Modular Exponentiation
2
Assignment
- Fast Modular Exponentiation: Code
- Modular Exponentiation
4
Readings
- Modular Exponentiation
- Fast Modular Exponentiation
- Fermat's Little Theorem
- Euler's Theorem
One-time Pad
1
Labs
- Many Time Pad Attack
5
Readings
- Cryptography
- Secure Communication
- Substitution Ciphers
- One-time Pad
- Many Time Pad Attack
RSA Cryptosystem
2
Assignment
- RSA Quiz: Code
- RSA Quest - Quiz
1
Labs
- RSA Quest Notebook
3
Readings
- RSA Cryptosystem
- Attacks and Vulnerabilities
- Randomness Generation
Auto Summary
Unlock the fascinating world of "Number Theory and Cryptography" in this foundational IT & Computer Science course. Dive into the essential principles of number theory, once deemed purely theoretical, and discover their revolutionary application in modern cryptographic protocols. Guided by a seasoned expert, you'll explore the journey from basic mathematical concepts to the development and implementation of RSA encryption – a cornerstone of secure digital communication. This engaging course is designed for anyone with a basic understanding of mathematics and Python programming, making it accessible to motivated high school students, IT professionals, and enthusiasts alike. Over approximately 1020 minutes of comprehensive content, learners will gain the skills to encrypt and decrypt messages, understand the intricacies of cryptographic protocols, and even tackle a cryptographic quest. Join us on Coursera with our flexible Starter subscription plan and embark on a journey to master the crucial intersection of number theory and cybersecurity. Perfect for those eager to enhance their knowledge and capabilities in the ever-evolving IT landscape.

Michael Levin

Alexander S. Kulikov
Michael Levin

Владимир Подольский