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

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

\begin{document}
\headers{Math373}{Homework 5}{Due Wed, Feb. 15, 2023}

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

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

\makeatletter
\def\@oddfoot{}
\makeatother

\newcommand{\K}{\mathcal{K}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}


\newcommand{\ord}{\mathrm{ord}}
\newcommand{\F}{\mathbb{F}}

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

\begin{enumerate}

\item Multiplicative inverses in two ways.  Let $m=101$.
\begin{enumerate}
	\item Use Fermat's Little Theorem and the fast power algorithm to compute the inverse of $68$ in $\Z_m$.
	\item Use the extended Euclidean algorithm to compute the inverse of $68$ in $\Z_m$.
	\item Which method is better?  Are there circumstances when one method can be used, but not the other?
\end{enumerate}


\item {} [JJJ 1.36] Compute the value of $2^{(p-1)/2} \pmod{p}$ for every prime $p$ such that $3 \le p < 20$.  (You do not need to show the details of your computation.)  Make a conjecture as to the possible values of $2^{(p-1)/2} \pmod{p}$ and prove that your conjecture is correct.

\item {} Let $m=1961$. Use Fermat's Little Theorem to prove that $m$ cannot be prime.  Do not factor $m$.

\item {} Fast Power Algorithm
\begin{enumerate}
	\item Implement the fast power algorithm $\mathtt{fast\_power}(a,n,m)$ as a function that computes $a^n\pmod{m}$.  A recursive implementation will probably not work due to limited stack space provided by most programming environments, so an iterative implementation is recommended.  Submit your code for $\mathtt{fast\_power}(a,n,m)$.  Hints: make a loop that computes $\alpha\cdot (\beta)^n\pmod{m}$, where $\alpha$ and $\beta$ are variables.  In each iteration, your loop should decrease $n$ by $1$ (if $n$ is odd) or cut $n$ in half (if $n$ is even), modifying $\alpha$ and $\beta$ appropriately.
	\item Use your code to compute $3^n\pmod{m}$ where 
\begin{align*}
n = ~
& 8210362893450651574131722296757356605200830169356578785813400124279769 \\
& 1494399109783730964536462425805314596635511606535459103343485526667825 \\
& 0438301548529598352882812656428385418093139636082570658299829788458938 \\
& 9083806978918503471627935113458406773943290254539587711017833207101432 \\
& 5550216588266041278200122901497676684219641814803583019462296990591112 \\
& 6993897921967321817986478442195134063060064678359754030334303960856670 \\
& 3483740856368972704219205926958570459413034458778737766317296872902209 \\
& 6773871939461088592535234193912878536049772231013533830752722286864466 \\
& 45520706511373820234488918043529860446112677987265442292451\\
\\
m = ~
& 8651150043557325511450175101264786208775439422974363414691402687392683 \\
& 8617465807737218060864732534779835429286856745443958175654305684571482 \\
& 1187406006409811660901887625785757970044918073643563547474989534274434 \\
& 9444036680156887905621835235579495131134575217730594952389382011952799 \\
& 2513893144681242141885337139933240910034594095241655333780810035436287 \\
& 1109951870215818680246819107214492903711323010930843097199754799801451 \\
& 3126712689350813090877776469762068452734380642840997344165805371355959 \\
& 3568737196797196120707485389647731118058940157480809918125993307434175 \\
& 65437712641882372654734647375636810215509202840599416602729
\end{align*}
Hint: to check your work, the answer begins ``860...'' and the sum of the digits is 2765.
\item Compute $3^{m-1}\pmod{m}$, $4^{m-1}\pmod{m}$, and $5^{m-1}\pmod{m}$.  What might these computations suggest about $m$?
\end{enumerate}


\end{enumerate}
\end{document}
