Relevant Textbook Sections:

2.7 (Runtimes and Big-Oh notation), 2.8–2.9 (The Discrete Logarithm and the Discrete Logarithm Problem), 2.10.1 (The Baby-Step Giant-Step Algorithm)

To Do:

1. Reminder: the first test is in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus.
2. Solutions to the last daily post (a complete worked example of the Diffie-Hellman exercise, with numbers you can try in the tools) are now posted: Solutions to Daily Due Sep 4. All daily post solutions are collected on the Archive page.
3. For each of the following pairs of functions, determine if $f=O(g)$ and if $g=O(f)$.
   1. $f(x) =|\sin(x)|$ and $g(x) = 1/2$.
   2. $f(x) = 2^x$ and $g(x) = 3^x$.
4. Use the Baby-Step-Giant-Step algorithm (and show all steps) to solve the discrete logarithm problem $34 = 3^x \pmod{113}$. You may use Sage’s functionality to compute the lists, including the tools on the Baby-Step Giant-Step page if you want to (ask for help on discord if you need some explanation of the page), so it shouldn’t involve much work by hand. But please present the solutions tidily and in a well-explained and well-labelled way (indicate where each term in each list comes from, not just the value you get), so the algorithm is evident.
5. If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.
6. Remember to upload to canvas!

Added Sept 9: solutions to this daily post (the big-oh comparisons and the baby-step giant-step computation) are now posted: Solutions to Daily Due Sep 9.