Relevant Textbook Sections:

2.4.4–2.4.5 (The theorems of Euler and Fermat; Using Euler’s $\varphi$ function), 2.7 (Runtimes and Big-Oh notation), 2.8–2.9 (The Discrete Logarithm and the Discrete Logarithm Problem), 2.10 (Parity of discrete log), 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 (the big-oh comparisons and the baby-step giant-step computation) are now posted: Solutions to Daily Due Sep 9. All daily post solutions are collected on the Archive page.
3. A bit of math practice that shows that the parity (even or oddness) of the discrete log can be discovered easily. Let $p$ be an odd prime number.
   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$.
   8. Comment on whether parity of a discrete log is well-defined modulo $n$. Why is it ok for odd primes $p$?
4. Review for Test 1. Use the Baby-Step-Giant-Step algorithm to solve the discrete logarithm problem $51 = 2^x \pmod{83}$. ($2$ is a primitive root modulo $83$.) Present both lists, labelled so it is clear where each entry comes from, identify the collision, and explain how it gives $x$. Then check your answer. You may use the tools on the Baby-Step Giant-Step page or the Sage Sandbox to generate the lists. Or do some by hand, for practice!
5. Review for Test 1. Compute $2^{(3^{2026})} \pmod{33}$ “by hand” (calculator is ok for multiplications and reductions, but show all steps). Remember to check the coprimality conditions that Euler’s theorem needs, each time you use it.
6. A runtime analysis. Here is a search problem: the input is two integers $N$ and $t$. The goal is to decide whether $t$ appears in the list $1^3+1, 2^3+2, 3^3+3, \ldots, i^3+i, \ldots, N^3 + N$. Two algorithms: Linear search computes the list from the beginning, comparing each computed entry to $t$, and stops when it finds $t$ or passes it. Binary search computes the middle entry, compares $t$ to that middle entry, discards the half of the list which cannot contain $t$, and repeats on the half that remains, until it finds $t$ or runs out of list.
   1. Determine the size of the input to this problem (in bits), as a function of $N$.
   2. Determine the runtime of each algorithm, in big-oh notation, as a function of the input size. Count a comparison of two integers as costing a number of bit operations proportional to their length in bits.
7. Remember to upload to canvas!