\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,mathrsfs}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage[theorems,skins]{tcolorbox}
\usepackage[colorlinks=true]{hyperref}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\Pcal}{\mathscr{P}}
\newtheorem{theorem}{Theorem}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\begin{document}
\huge{DLP Exercises (Daily Due Sept 14)}
\large{Katherine E. Stange, CU Boulder}
In the exercises that follow, you are asked to use Sage to do computations. It's strongly recommended to use Sage instead of other software, because Sage has so many in-built number theory functions that we will make use of\footnote{But if you insist, you can use something else. I won't be able to support you with other languages/software, likely, since I'm not an expert in everything. ;)}. In particular, if Sage does something with a one-line command, and I don't specifically ask you to implement it yourself, go for it. (For example, relevant to this assignment, Sage will compute the multiplicative order of an element in an \texttt{IntegerModRing} using the command \texttt{multiplicative\_order()}.)
\section*{Exercise 1}
Use Sage to find all primitive roots modulo the prime $29$. One of them is $2$, for example.
\section*{Exercise 2}
Create a chart of the powers of $2$ modulo $29$ (use Sage).
\section*{Exercise 3}
Using the chart above, \emph{by hand}, compute the following discrete logarithms:
\begin{enumerate}
\item $L_2(7)$
\item $L_2(11)$
\item $L_4(7)$ (hint: use item (1) above)
\end{enumerate}
\section*{Exercise 4}
\begin{enumerate}
\item Using Sage, but without calling any discrete logarithm functionality directly, implement an algorithm to determine the discrete logarithm of an element $a$ modulo $n$ with respect to a generator (primitive root) $g$. Paste in the code to your solutions.
\item Use the code to compute that the discrete log of $17$ to the base $2$ in $\ZZ/197\ZZ$ is $159$, i.e. $L_2(17) = 159$ in $\ZZ/197\ZZ$. (If this doesn't work, fix your code!)
\end{enumerate}
\end{document}