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

1. Compute 2^{23 425 142} mod 23 425 143.
   Using your answer and Fermat's Little Theorem, what can you conclude about 23 425 143?
2. Is 3 a primitive root of \( \mathbb{F}_{11} \)? How about 2? Explain.

Submit answers through Canvas

---

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

1. What is the advantage of using Pollard's \( \rho \) for solving the DLP over using Shank's?
2. Pollard's \( \rho \) is a collision algorithm. What is the collision it looks for in the sequence \( \{x_i\} \)?

Submit answers through Canvas

---

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

1. Consider the DLP 2^x ≡ 21 mod 29. If you apply Shanks Babystep-Giantstep to solve this, how long will each list be?
2. Why are we studying the Chinese Remainder Theorem now?
3. Consider the DLP g^x ≡ 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=2³⋅ 5²⋅ 269⋅ 307⋅ 1009 is the prime factorization.
   How many smaller DLPs will you solve when applying Pohlig-Hellman to this DLP?

Submit answers through Canvas

---

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

1. Is 38 a Miller-Rabin witness for 289? Explain.
2. Is 36 a Miller-Rabin witness for 289? Explain.

Submit answers through Canvas

---

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

1. What's the advantage of using elliptic cuves in cryptography?
2. Why do we include the point \( \mathcal{O} \) at infinity in our elliptic curves?
3. If P₁ ≠ P₂ are points on the elliptic curve E, give a geometric description of the point P₁ + P₂ on E.
4. Consider the elliptic curve E: Y² = X³ -5 X +6 over \( \mathbb{F}_{23} \). Verify that P=(1,5) and Q=(4,2) lie on E and find P+Q.

Submit answers through Canvas

---

Week 9: Due Monday March 24 @ 9:00 am

Refresher on Shor's algorithm
Introduction to lattices

To Read

• Review the statements of Shor's algorithm for factoring (Nov 6, 2024 notes) and solving the DLP (Nov 11, 2024 notes)
• Section 7.3 A Brief Review of Vector Spaces
• Section 7.4 Lattices: Basic Definitions and Properties
• Section 7.5 Short Vectors in Lattices

There's a lot of information in here, so try not to get bogged down in the details, but try to pick up the high points. It's most important to understand the definitions of a lattice and a fundamental domain, as well as the statements of the Shortest Vector Problem and the Closest Vector Problem. The video will help explain these, too.

Optional videos from Spring 2021

• Introduction to Lattices - Link in Canvas

Pre-Class Questions

Let \( \mathcal{L} \) be the lattice generated by \( v_1=\left\langle 2,3 \right\rangle \) and \( v_2=\left\langle 1,5 \right\rangle \)

1. Give two points other than \( v_1 \) and \( v_2 \) that lie in \( \mathcal{L} \). Explain.
2. Does \( \left\langle \frac{1}{2}, \frac{5}{3} \right\rangle \) lie in \( \mathcal{L}\, \)? Explain.

Submit answers through Canvas

---

Week 10: Due Monday March 31 @ 9:00 am

Babai's Algorithm
LLL Lattice Reduction Algorithm

To Read

• Section 7.6 Babai's Algorithm and Using a "Good" Basis to Solve apprCVP
• Section 7.13 Lattice Reduction Algorithms

Pre-Class Questions

1. What is the purpose of Babai's algorithm?
2. Under what circumstances does Babai's algorithm fail?
3. What is the purpose of the LLL latice reduction algorithm?

Submit answers through Canvas

---

Week 11: For Monday April 7

Post-quantum cryptography

To Read

• What Is Post-Quantum Cryptography?, an overview from NIST
• Cryptography's Future Will Be Quantum-Safe. Here’s How It Will Work at Quanta Magazine
• 'Post-Quantum' Cryptography Scheme Is Cracked on a Laptop at Quanta Magazine
• CRYSTALS Kyber : The Key to Post-Quantum Encryption, a post at Medium
• FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard, a 2024 publication by NIST. Scan this to try to get a general idea for how the specs are written
• CRYSTALS: Cryptographic Suite for Algebraic Lattices is the home of the project that developed both CRYSTALS-Kyber and CRYSTALS-Dilithium
• Basic Lattice Cryptography: The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA) by Vadim Lyubashevsky at IBM Research Europe, Zurich is another good reference

No specific questions, but be prepared to discuss these.

---

Week 12: For Monday April 14

Post-quantum cryptography

To Read

No specific questions, but re-read the materials from last week. The ideas behind CRYSTALS-Kyber should be falling into place.