Algorithmic Number Theory (Spring 2024)
Instructor: Nam Hoai Le
Lecture time and location: Wednesdays, Linh Trung Campus, Thu Duc Ward (formerly Thu Duc District)
Textbook: Elementary Number Theory Its Applications - 6th eddition (Rosen 2018) by Kenneth H. Rosen
Course Schedule
| Week | Section(s) | Topics (Morning) | Recommended Exercises | Lab (Afternoon) |
|---|---|---|---|---|
| 1 | 2.1 2.2 2.3 3.1 3.2* |
Course intro Algorithms & complexity Integer representation Primes |
2.1: 1–7 2.2: 1–16 2.3: 1–15 |
— |
| 2 | 3.3 3.4 3.5 3.6* |
Euclid algorithm Bézout lemma |
3.3: 1–32 3.4: 1–10, 19, 20 |
— |
| 3 | 3.7 4.1 4.2 4.3 4.4–4.5* 5.1 |
Diophantine equations Congruences Chinese Remainder Theorem Linear congruence systems Divisibility |
3.7: 1–10 4.1: 5, 15, 30, 31, 36 4.2: 1–2 4.3: 4 |
Lab 1 — Python Intro |
| 4 | 6.1 6.2 6.3 7.1 7.2 |
Fermat & Wilson Pseudoprimes & Carmichael numbers Euler’s theorem Arithmetic functions |
6.1: 12, 13, 15, 17 6.2: 16,20 6.3: 5–12 7.1: 2,5,11,12 |
Lab 2 — Loops & Linked Lists |
| 5 | 7.3 7.4 9.1 |
Perfect numbers Mersenne primes Möbius function Primitive roots |
9.1: 1–20 | Lab 3 — Data Structures |
| 6 | 11.1 11.2 11.3 |
Quadratic residues Legendre symbol Jacobi symbol |
11.1: 4, 6, 8, 9, 10, 13, 20, 41 11.2: 1 |
Exercises + coding practice |
| 7 | — | Midterm review 90-min Midterm exam |
— | Lab 4 — Object-Oriented Programming |
| 8 | 6.2 11.4 |
Primality tests: Deterministic — trivial method Miller–Rabin Euler pseudoprimes Solovay–Strassen |
Design and implement the corresponding primality-testing algorithms | Lab 5 — File I/O |
| 9 | 9.5 3.6 4.6 6.1 12.5 |
Integer factorization: Pollard’s Rho Pollard \(p−1\) Continued fractions Continued-fraction–based factorization Number Field Sieve |
Design and implement the corresponding integer factorization algorithms | Lab 6 — Modules |
| 10 | 8.1 8.2 8.3 8.4 10.2 |
Caesar cipher RSA ElGamal |
Implement encryption and decryption algorithms for RSA and ElGamal. | Exercises + practice |
| 11 | — | Discrete Logarithm Problem: Baby-Step Giant-Step Pollard’s Rho Index calculus |
Design and implement the corresponding discrete logarithm algorithms | Lab 7 — Packages |
| 12 | — | Review Midterm Final exam prep |
— | Lab 8 — Exceptions |
* Further Reading
References
Rosen, K. H. 2018. Elementary Number Theory. Pearson Education. https://books.google.com/books?id=FPpKDwAAQBAJ.