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

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

\begin{document}
\headers{Math373}{Homework 12}{Due **Wed**, Apr. 16, 2014}


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

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

\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

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

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

\begin{enumerate}

\newcommand{\dr}[3]%
{%
	$x^{#1} \equiv #2 \pmod{#3}$%
}

\item {} Alice's public key uses modulus 
\[N=22476~96411~17831.\]  
Of course, $N=pq$ for some secret primes $p$ and $q$.  Somehow, Eve is able to compute \[ (p-2)(q-3) = 22476~95651~24622. \]  
Help Eve use this information to factor $N$.  \emph{Hint:} try to adapt the technique for factoring $N$ given $(p-1)(q-1)$ to this new case.

\item {} [JJJ 3.13(a)] Here, we prove that $561$ is a Carmichael number.  That is, $561$ is composite and yet it has no Fermat witnesses.  Note that $561 = 3\cdot 11\cdot 17$.
\begin{enumerate}
    \item Prove that if $a\in \Z_{561}^*$, then $a$ satisfies the system
            \begin{align*}
                a^{560} \equiv 1 &\pmod{3}\\
                a^{560} \equiv 1 &\pmod{11}\\
                a^{560} \equiv 1 &\pmod{17}
            \end{align*}
    \item Prove that $561$ has no Fermat witnesses.
\end{enumerate}

\item For each pair $(n,a)$ below, determine whether $a$ is (i) a Fermat witness for $n$; and (ii) a Miller--Rabin witness for $n$.
\begin{enumerate}
    \item $n=21$ and $a=8$
    \item $n=1279$ and $a=1091$
    \item $n=1722971$ and $a=1711330$
    \item $n=1722971$ and $a=2$
    \item $n=8533633$ and $a=3862185$
    \item $n=8533633$ and $a=5393220$
\end{enumerate}


\end{enumerate}
\end{document}
