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
  • 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.