\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\newcommand{\ord}{\mathrm{ord}}

\begin{document}
\headers{Math373}{Homework 5}{Due Fri, Feb. 14, 2014}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\F}{\mathbb{F}}
\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}


\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item Modular exponentiation in $\F_7$.
\begin{enumerate}
	\item Fill in the table so that row $a$ and column $k$ contains $a^k$, where $a^k \in \F_7$.
	\begin{center}
	{
	\def\arraystretch{1.5}
	\begin{tabular}{c|*{9}{|p{0.5cm}}}
		$a^k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & $\cdots$\\
		\hline
		\hline
		0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
		\hline
		1 & & & & & & & &\\
		\hline
		2 & & & & & & & &\\
		\hline
		3 & & & & & & & &\\
		\hline
		4 & & & & & & & &\\
		\hline
		5 & & & & & & & &\\
		\hline
		6 & & & & & & & &\\
	\end{tabular}
	}
	\end{center}

	\item For each non-zero element $a$, find the order of $a$ in $\F_7^*$.

	\item Use the table to find all primitive roots in $\F_7$.  Verify that the number of primitive roots equals $\phi(6)$.
\end{enumerate}

\item Use Fermat's Little Theorem and the fast power algorithm to compute the multiplicative inverse of $68$ in $\F_{101}$.


\item Using as few modular exponentiation computations as possible, determine whether the following are primitive roots in $\F_{101}$.
\begin{enumerate}
	\item $76$
	\item $87$
	\item $44$
\end{enumerate}

\item Primitive roots in $\F_{23}$.
\begin{enumerate} 
	\item Find a primitive root of $\F_{23}$.  
	\item Use part (a) to list all primitive roots of $\F_{23}$.
\end{enumerate}

\newpage
\item \compicon Fast Power Algorithm.  
\begin{enumerate}
	\item In sage, reducing an integer $a$ modulo $m$ is achieved with the expression $a~\%~m$.  The following sage code implements the fast power algorithm, but a few blanks are missing.  Fill in the blanks.
\begin{verbatim}
def fast_power (a, k, m):
    """for non-negative integers k, computes a^k modulo m"""
    if (k == 0):
        return ________
        
    if ((k % 2) == 1):
        # k is odd
        # recursively compute y = a^{k-1} (mod m)
        y = fast_power(a, k-1, m)
	
        return ________ % m
    else:
        # k is even
        # recursively compute y = a^{k/2} (mod m)
        y = fast_power(a, k/2, m)

        return ________ % m
\end{verbatim}

	\item Use the fast power algorithm to compute $(28324)^{14635515} \pmod{73254}$.  

	\item Use the fast power algorithm and Fermat's Little Theorem to make an educated guess about whether the following numbers are prime.
	\begin{enumerate}
		\item 29399891
		\item 34728343
		\item 837249143
		\item 296787375427
	\end{enumerate}
\end{enumerate}
\end{enumerate}
\end{document}
