Cryptography


Notes from MATH 470 — Communications and Cryptography at Texas A&M during Fall 2021 with Dr. Josiah Park.

Based off of the lectures and An Introduction to Mathematical Cryptography by J. Hoffstein, J. Pipher, and J.H. Silverman.

The course is an exploration into the mathematical foundations of cryptography and how they are used in public- and private-key cryptosystems, with topics covering modular groups and fields, primality testing, factorization, and elliptic curves.

Specific topics include Diffie-Hellman key-exchange, RSA, AKS/Baillie-PSW/Miller-Rabin primality testing, Pollard rho/sieves/Lenstra factorization.

Notation

  • Zn\mathbb{Z}_n and Z/nZ\mathbb{Z}/n\mathbb{Z} are used interchangably; as are (Zn)×(\mathbb{Z}_n)^\times and (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times
  • Zn\mathbb{Z}_n is sometimes used in place of (Zn)+(\mathbb{Z}_n)^{+} or (Zn)×(\mathbb{Z}_n)^\times, which is disambiguated based on context
  • N\mathbb{N} are the natural numbers, defined without 0.
  • P\mathbb{P} are the set of primes
  • The interval notation [ab],[a\dots b], (ab),(a\dots b), (ab],(a\dots b], [ab)[a\dots b) defines the set of integers between aa and bb with brackets for inclusivity or parentheses for exclusivity[a].

2026 Update

Over the years I've come to prefer the set notation {a,,b}[ab],\{a, \dots, b\} \triangleq [a\dots b], even if it means that I have to explicitly state n1n - 1 instead of using a parenthesis for when something is exclusive.

^a: Not everything has been touched in my update; some portions of these notes may use the interval notation, and in others the set notation.