Relevant Textbook Sections:

2.12 (ElGamal Encryption) for review.

To Do:

1. Do the El Gamal ciphertext chain if you haven’t already (last daily post).
2. Suppose that $x^2 \equiv y^2 \pmod n$ but $x \not\equiv \pm y \pmod n$. Explain how this can help you factor $n$. Hint: Factor a difference of squares.
3. Look at the modular arithmetic playground. Try some different functions and look at the dynamical portraits. Now, click on the modulus and use the arrow keys to go through different moduli. Look for patterns and see if you can predict whether or not $n$ is prime, or anything about its factorization, from studying the patterns. Do certain patterns imply that the modulus is prime or composite?

Added Sept 23: solutions to this daily post (how $x^2 \equiv y^2$ factors $n$, and the patterns in the dynamical portraits) are now posted: Solutions to Daily Due Sep 18.