Pre-Class Assignments
Math 302 Advanced Cryptography, Spring 2021

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.

All Echo360 videos are avaialable through onCourse.

Be sure to check back, because this page will be updated often during the semester.


Week 2: Due Sunday February 7 @ midnight

Fermat's Little Theorem
Primitive roots

To Read

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.

To Watch

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 onCourse

Week 3: Due Sunday February 14 @ midnight

DLP vs DHP
Lagrange's Theorem
Introduction to big-\( \mathcal{O} \) O

To Read

As with last week's assignment, much of the first few sections will be review. There's a lot of information in Sections 2.5 & 2.6, and we'll hit the high points in the videos and during class.

To Watch

Pre-Class Questions

  1. Explain the difference between the Discrete Log Problem (DLP) and the Diffie-Hellman Problem (DLP).
  2. What is the order of (ℤ/8ℤ)*? What is the order of 3 in (ℤ/8ℤ)*? Explain.
  3. Why are we looking at big-\( \mathcal{O} \) notation now?
Submit answers through onCourse

Week 4: Due Sunday February 21 @ midnight

Shanks Babystep-Giantstep algorithm
The Chinese Remainder Theorem

To Read
To Watch

Pre-Class Questions

  1. Consider the DLP 2x ≡ 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?
Submit answers through onCourse

Week 5: Due Sunday February 28 @ midnight

The Pohlig-Hellman algorithm

To Read
To Watch

Pre-Class Questions

  1. Consider the DLP \( g^x \equiv 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^3\cdot5^2\cdot269\cdot307\cdot1009 \) is the prime factorization.
    How many smaller DLPs will you solve when applying Pohlig-Hellman to this DLP?
  2. Which algorithms/theorems that we have already learned are used when applying the Pohlig-Hellman algorithm?
    At what point are these used?
  3. How many times have you and your partner met to discuss Problem Set 2? How much progress has your group made?
Submit answers through onCourse

Week 6: Due Sunday March 7 @ midnight

Pollard's \( \rho \) applied to DLP

To Read
To Watch

Pre-Class Questions

  1. Coming by Thursday, March 4
Submit answers through onCourse

Week 7: Due Sunday March 14 @ midnight

More on Pollard's \( \rho \)
Primality testing

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 8: Due Sunday March 21 @ midnight

Miller-Rabin witnesses
Pollard's \( \rho \) applied to factoring

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 9: Due Sunday March 28 @ midnight

Introduction to elliptic curves

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 10: Due Sunday April 4 @ midnight

Elliptic curves over \( \mathbb{F}_p \)
The elliptic curve DLP

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 11: Due Sunday April 11 @ midnight

Elliptic curve DHKE
Elliptic curve DSA

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 12: Due Sunday April 18 @ midnight

Introduction to lattices
The closest vector problem

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 13: Due Sunday April 25 @ midnight

GGH lattice-based encryption

To Read
To Watch

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse

Week 14: Due Sunday May 2 @ midnight

Student presentations

To Read

Pre-Class Questions

  1. Coming soon. . .
Submit answers through onCourse