Chinese Remainder Theorem to solve a pair of congruences

Fermat primality test

Fermat factorization

Miller-Rabin primality test

RSA creating public and private keys

RSA encryption/decryption using keys

Computing Euler phi function as in Mission #4

Given n an phi(n), where n is an RSA modulus, compute a factorization of n using quadratic formula

Given a public key, and the factorization of the modulus, compute the private key

Be able to give well-written proofs of:

The multiple square root principle

Fermat’s Little Theorem (including the fact that multiplication by invertible elements is bijective)

Chinese Remainder Theorem (using ax+by=1)

novel statements involving basic definitions of modular arithmetic, or variations on the proofs just mentioned, or variations on the proofs of Mission #4

Things to know about:

divides, gcd, lcm, prime, composite, factor

statement of Euler’s Theorem

The multiple square root principle

Dangers of choosing primes close to each other in RSA

big O notation and runtimes of algorithms we’ve discussed (e.g. gcd, successive squaring)

multiplicative order of an element mod n

What “probably prime” means in theory and practice, pseudoprimes and strong pseudoprimes

Note: I’ve stayed pretty close to the textbook, so you’ll find all these things in there (except maybe big O notation and runtimes?) if your course-notes are lacking.