For Friday:

1. For each of the following pairs of functions, determine if $f=O(g)$ and if $g=O(f)$.
   1. 1. $f(x) =|sin(x)|$ and $g(x) = 1/2$.
      2. $f(x) = 2^x$ and $g(x) = 3^x$.
2. Read your textbook, Section 2.9 “One Time Pads”.  This explains the “add your message to the shared key” approach I used in the last daily post.  (Let me know if you don’t have access to the text yet.)
3. Fill in this Google Form collecting some info on how you want to do office hours and whether you want some extra tutorial on proofs.
4. A bit of math practice that shows that the parity (even or oddness) of the discrete log can be discovered easily.  Let $p$ be a prime number.
   1. 1. Show that if $ab \equiv 0 \pmod p$ then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$
      2. Use part (1) on the expression $(x+1)(x-1)$ to show that the only two solutions to $x^2 \equiv 1 \pmod p$ are $1$ and $-1$.
      3. Let $g$ be a primitive root mod $p$.  Show that $g^{(p-1)/2} \equiv -1 \pmod p$.  (This uses the previous part.)
      4. Suppose $h \equiv g^x \pmod p$ is given to you (but $x$ is not known).  Show how you can determine if $x$ is even or odd.  Hint: Raise the equation $h\equiv g^x \pmod p$ to the $(p-1)/2$ power and see what you get using the previous part.
      5. Note that $2$ is a primitive root modulo $11$.  Use the test above to determine if $x$ so that $2^x \equiv 5 \pmod{11}$ is even or odd.
      6. Check whether you are correct by finding $x$ (by any method).
      7. Comment on the runtime of this test for the parity of $x$.
5. If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.  We discussed this in class and saw that the Sage server wasn’t having it, with my little for loop.  But maybe you can make it work!