Number Theory & Cryptography
An Online Course Offered At The Georgia Institute of Technology
Skip to content
Home
About This Course
Introductory Video
Applications of Number Theory
Office Hours
Site Map
Lessons
Lesson 1: Pythagorean Triples
The Pythagorean Theorem
Patterns in Primitive Pythagorean Triples
The Pythagorean Triples Theorem
(*) Fermat’s Last Theorem
Lesson 2: Divisibility and Unique Factorization
The GCD
The Euclidean Algorithm
Solving Linear Equations in Integers
A Fundamental Property of Primes
The Fundamental Theorem of Arithmetic
Lesson 3: Modular Arithmetic and Applications
Modular Arithmetic
Calendar Calculations
Music Theory
Divisibility Tests
Fermat’s Last Theorem for Exponent 4
Additional Resources
Lesson 4: Congruences
Modular Inverses
A Multiplicative Inverse Theorem
Linear Congruence
The Number of Solutions to a Linear Congruence
Lesson 5: The Theorems of Fermat and Euler
Towards Fermat’s Little Theorem
FLT and its Proof
A Lemma
Simplifying Computations
Proving Compositeness
Successive Squaring
Euler’s Generalization of FLT
Euler’s φ function
Lesson 6: The Chinese Remainder Theorem and Euler Phi Function
The Chinese Remainder Theorem
The Euler Phi Function
The CRT and ϕ
Card Tricks and the CRT
Fast Parallel Integer Arithmetic
Order
Perfect Shuffles
Lesson 7: Prime Numbers and Sage
The Prime Number Theorem
Recent Developments
Probability
Sage
Lesson 8: Primality Testing
Primality Testing
Carmichael Numbers
The Rabin-Miller Test
Lesson 9: Introduction to Public Key Cryptography
Historical Approaches
Public Key Cryptography
The Diffie-Hellman Protocol
Analysis of the Protocol
Practical Issues
Additional Resources
Lesson 10: The RSA and ElGamal Cryptosystems
Development of the RSA Algorithm
How RSA Works
Why RSA Works
The Security of RSA
Factoring Large Numbers
ElGamal Cryptosystem
Additional Resources
Lesson 11: Primitive Roots and Discrete Logarithms
Introduction to Primitive Roots
Primitive Root Theorem
Preliminary Result: The Ord Function
Two Additional Preliminary Results
Proof of the PRT
Primitive Roots for Non-Primes
Discrete Logarithms
Quadratic Residues
Lesson 12: Quadratic Residues
Introduction to QR
Euler’s Criterion
Square Roots Mod p
Square Roots Mod n = pq
Square Roots and Factoring
Flipping A Coin Over the Telephone
Lesson 13: The Law of Quadratic Reciprocity
The Law of Quadratic Reciprocity
Permutations
Zolotarev’s Lemma
Translating to a Combinatorial Problem
Proof of Claim 1
Proof of Claim 2
Mersenne Primes
Lesson 14: Euler, Master of Us All
The Probability that Two Randomly Chosen Integers are Relatively Prime
Euler’s Proof that There are Infinitely Many Primes
The Distribution of Primes
A Second Theorem on the Distribution of Primes
The Riemann Hypothesis
Additional Resources
Course Summary
Course Activities
Introduce Yourself
Weekly Assignments
Midterms
Final Project
Important Dates
Lesson 10: The RSA and ElGamal Cryptosystems
To view the content on this page,
click here to log in using your Course Website account
. If you are having trouble logging in, email your instructor.
Comments are closed.
Search for:
Search
Helpful Links
Course Syllabus (PDF)
Math 2803 on Piazza, Fall 2018
Matt Baker's Website
