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
The Euclidean Algorithm
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
