Numbers Made Dumber
Project Description
This project will serve as an introduction to Number Theory and some of its cool real world applications like in Cryptography! One component (the obvious one) is theoretical where the idea would be to cover theory (some Olympiad related and some algebra related) and tickle the brain cells by solving some problems. The other component would be implementing some of the algorithms in code as we study them. This would give a more hands on feel and an idea about using it in applications.
Mentors
- Yatharth Goswami
- Vivek Kumar Singh
- Rohan Baijal
Learning Roadmap
- Number Theory
Divisibility and Euclid’s Division Algorithm. This is easy but important as these topics will lay the foundation. Read the notes and attempt the assignment after going through these videos
Divisibility and the Euclidean Algorithm
Next we’re covering some Prime numbers and some important results and techniques related to it. Go through the notes and assignment.
After primes study modular arithmetic and Chinese Remainder Theorem. This is an important topic and requires a lot of practice. Watch all the videos, and got through the notes and assignment.
Modular Arithmetic and Linear Congruences Chinese Remainder Theorem Some more NT theorems
- Use of Number Theory in Competitive Programming
We felt it might be good to do some problem solving so that you get a feel about making observations and applying these techniques to make some problems easier.
Here are the links for practice
Euclid Algorithm
Extended Euclid Algorithm
Linear Diophantine Equation
Fibonacci Numbers
Sieve of Eratosthenes
Phi Function
Divisors
Chinese Remainder Theorem
Try to go through the write-up and also try implementing the algorithms on your own.
- Use of Number Theory in Cryptography
We will study one of the most famous public-key cryptography schemes out there, i.e. RSA. First of all, you should all know what this public key cryptography means.
Public Key Cryptography - Computerphile
This video provides an elementary and intuitive idea of public-key crypto and its importance. Various protocols achieve this idea of public-key crypto, the most famous being RSA encryption. When you study RSA, you will see that it relies basically on hard number-theoretic and group-theoretic problems. We learned a lot about number theory throughout the project, but wait, what is this “Group-theoretic”? You must be wondering why we need abstract algebra in cryptography in the first place. I would suggest reading through this discussion first before stepping into the details of RSA.
Abstract algebra in Cryptography
If you want to get anything out of this discussion, go through the above material first.
Prime Numbers & RSA Encryption Algorithm - Computerphile
Computerphile has some amazing videos on cryptography; you are free to explore more of these in future.
These are some blogs which will hopefully give you a good idea about Public Key Algorithms.
If you are intrigued by this application you might want to read up about more public key algorithms like Diffie-Hellman
Resources
Books:
- Elementary number theory by David M Burton
- Elementary Number Theory by Niven and Zuckerman
Notes and Assignments: NMD Notes and Assignments