For each of the following pairs of functions, determine if $f=O(g)$ and if $g=O(f)$.
$f(x) =|sin(x)|$ and $g(x) = 1/2$.
$f(x) = 2^x$ and $g(x) = 3^x$.
Use exhaustive search or any method to determine $L_2(3)$ modulo $13$. You can use Sage’s modular arithmetic functions such as the tables on this page.
It is a fact that $p=101$ is prime, and $2$ is a primitive root modulo $p$. It is a fact that $L_2(3)=69$ and $L_2(5)=24$ modulo $p$. It is also a fact that the integer factorization of $24$ is $24 = 2^3 \cdot 3$. Using these facts, evaluate $L_2(24)$ modulo $p$ with minimal work (just combine the facts above).
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.
Show that if $ab \equiv 0 \pmod p$ then $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$
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$.
Let $g$ be a primitive root mod $p$. Show that $g^{(p-1)/2} \equiv -1 \pmod p$. (This uses the previous part.)
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.
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.
Check whether you are correct by finding $x$ (by any method).
Comment on the runtime of this test for the parity of $x$.
Comment on whether parity of a discrete log is well-defined modulo $n$. Why is it ok for odd primes $p$?