Pre-Class Assignments
Math 302 Advanced Cryptography, Spring 2025
This page uses MathJax to display mathematical notation, so please let me know if any part isn't clear.
All section numbers refer to the text, An Introduction to Mathematical Cryptography, 2nd Edition by Hoffstein, Pipher, and Silverman.
Be sure to check back, because this page will be updated often during the semester.
Week 2: Due Monday January 27 @ 9:00 am
Fermat's Little Theorem
Primitive roots
To Read
- Section 1.1 Simple Substitution Ciphers (skim for background info)
- Section 1.2 Divisibility and Greatest Common Divisors
- Section 1.3 Modular Arithmetic
- Section 1.4 Prime Numbers, Unique Factorizations, and Finite Fields
- Section 1.5 Powers and Primite Roots in Finite Fields
- Section 1.6 Cryptography Before the Computer Age
Much of this should be review for you from the fall semester. Don't get too caught up in all of the details, but try to focus on the differences in notation from the fall. We'll hit the main points in the videos and during class.
Optional videos from Spring 2021
- A Little Number Theory - Link in Canvas
Pre-Class Questions
- Compute 223 425 142 mod 23 425 143.
Using your answer and Fermat's Little Theorem, what can you conclude about 23 425 143? - Is 3 a primitive root of \( \mathbb{F}_{11} \)? How about 2? Explain.
Week 3: Due Monday February 3 @ 9:00 am
Pollard's \( \rho \) applied to DLP
To Read
- Section 5.5 Pollard's \( \rho \) Method
Optional videos from Spring 2021
- Pollard's \( \rho \) - Link in Canvas
Pre-Class Questions
- What is the advantage of using Pollard's \( \rho \) for solving the DLP over using Shank's?
- Pollard's \( \rho \) is a collision algorithm. What is the collision it looks for in the sequence \( \{x_i\} \)?
Week 4: Due Monday February 10 @ 9:00 am
The Chinese Remainder Theorem
The Pohlig-Hellman algorithm
To Read
- Section 2.7 A Collision Algorithm for the DLP
- Section 2.8 The Chinese Remainder Theorem
- Section 2.9 The Pohlig-Hellman algorithm
Optional videos from Spring 2021
- The Chinese Remainder Theorem - Link in Canvas
- The Pohlig-Hellman algorithm - Link in Canvas
Pre-Class Questions
- Consider the DLP 2x ≡ 21 mod 29. If you apply Shanks Babystep-Giantstep to solve this, how long will each list be?
- Why are we studying the Chinese Remainder Theorem now?
- Consider the DLP gx ≡ h mod p where g=3, h=7 065 119 811, and p=16 665 249 401.
Note that g is a primitive root of \( \mathbb{F}_p \) and that p-1=23⋅ 52⋅ 269⋅ 307⋅ 1009 is the prime factorization.
How many smaller DLPs will you solve when applying Pohlig-Hellman to this DLP?
Week 5: Due Monday February 17 @ 9:00 am
The Pohlig-Hellman algorithm
Review the materials from last week, but not questions to submit with the exam this week.
Week 6: Due Monday February 24 @ 9:00 am
Miller-Rabin witnesses for primality testing
To Read
- Section 3.2 The RSA Public Key Cryptosystem (for review)
- Section 3.3 Implementation and Security Issues (for review)
- Section 3.4 Primality Testing
Optional videos from Spring 2021
- The Miller-Rabin Test - Link in Canvas
Pre-Class Questions
- Is 38 a Miller-Rabin witness for 289? Explain.
- Is 36 a Miller-Rabin witness for 289? Explain.
Week 7: Due Monday March 3 @ 9:00 am
Introduction to elliptic curves
Elliptic curves over \( \mathbb{F}_p \)
To Read
- Section 6.1 Elliptic Curves
- Section 6.2 Elliptic Curves over Finite Fields
Optional videos from Spring 2021
- Elliptic Curves (Computerphile)
- Elliptic Curve Point Addition (Riverninj4)
- Theorem 6.6 Explained - Link in Canvas
Pre-Class Questions
- What's the advantage of using elliptic cuves in cryptography?
- Why do we include the point \( \mathcal{O} \) at infinity in our elliptic curves?
- If P1 ≠ P2 are points on the elliptic curve E, give a geometric description of the point P1 + P2 on E.
- Consider the elliptic curve E: Y2 = X3 -5 X +6 over \( \mathbb{F}_{23} \). Verify that P=(1,5) and Q=(4,2) lie on E and find P+Q.