# Wednesday September 28

Second Quiz Today.

• Be able to perform by hand the following algorithms.  I may also ask you to demonstrate understanding of why/how they work through abstract questions.
• Basic modular arithmetic
• Euclidean algorithm & finding inverses mod n
• Efficient modular exponentiation (by repeated squaring)
• 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