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

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}
 
\lstset{style=mystyle}
\lstset{language=Python}

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


\begin{document}
\headers{Math373}{Homework 9}{Due Wed, Mar. 29, 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{\ZZ}{\mathbb{Z}}


\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}

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

\item {} [JJJ 3.1] Solve the following congruences.
\begin{enumerate}
\item \dr{19}{36}{97}.
\item \dr{137}{428}{541}.
\item \dr{73}{614}{1159}.
\item \dr{751}{677}{8023}.
\item \dr{38993}{328047}{401227}.  \emph{Hint:} $401227 = 607\cdot 661$.
\end{enumerate}

\item {} [JJJ 3.6] Alice publishes her RSA public key $(N,e) = (2038667, 103)$.
\begin{enumerate}
	\item Bob wants to send Alice the message $m=892383$.  What ciphertext does Bob send to Alice?
	\item Alice knows that her modulus factors into a product of two primes, one of which is $p=1301$.  Find a decryption exponent $d$ for Alice.
	\item Alice receives the ciphertext $c=317730$ from Bob.  Decrypt the message.
\end{enumerate}

\item {} [JJJ 3.7] Bob's RSA public key has modulus $N=12191$ and exponent $e=37$.  Alice sends Bob the ciphertext $c=587$.  Unfortunately, Bob has chosen too small a modulus.  Help Eve by factoring $N$ and decrypting Alice's message.  \emph{Hint:} $N$ has a factor that is less than $100$.

\item {} [JJJ 3.8] For each of the given values $N=pq$ and $N'=(p-1)(q-1)$, use the method in the proof that \textbf{FactorN} is at least as easy as \textbf{ComputeN'} to find $p$ and $q$.
\begin{enumerate}
	\item $N = 352717$ and $N' = 351520$
	\item $N = 28424293$ and $N' = 28411488$
	\item $N = 111702827046011$ and $N' = 111702805302024$.
\end{enumerate}

\item {} Consider the following two problems.
\begin{paragraph}{FactorN} 
Given an integer $N$ that is the product of distinct, unknown primes $p$ and $q$, output $p$ and $q$.
\end{paragraph}
\begin{paragraph}{Reduce} 
Given an integer $a$ and an integer $N$ that is the product of distinct, unknown primes $p$ and $q$ with $p<q$, output $b\in \Z_p$ and $c\in \Z_q$ such that $a\equiv b\pmod{p}$ and $a\equiv c\pmod{q}$.
\end{paragraph}

\begin{enumerate}
	\item Prove that $\textbf{Reduce} \le \textbf{FactorN}$.
	\item Prove that $\textbf{FactorN} \le \textbf{Reduce}$.
	\item Illustrate part (b) by factoring $N = 446846784807308867$.  Given $a=723728945230$ and $N$, your black box for \textbf{Reduce} reports that $a\equiv 299450419 \pmod{p}$ and $a\equiv 316955067 \pmod{q}$.
\end{enumerate}

\newpage
\item Suppose we know $N = pqr$, where $p$, $q$, and $r$ are large, distinct, unknown primes.  Somehow, we also know $N'=(p-1)(q-1)(r-1)$.
\begin{enumerate}
	\item Use CRT to show that if $\gcd(a,N)=1$, then $a^{N'} \equiv 1\pmod{N}$.
	\item Show that if $z^2 \equiv 1 \pmod{N}$ but $z\not\equiv 1\pmod{N}$ and $z\not\equiv -1\pmod{N}$, then either $\gcd(z+1,N)$ or $\gcd(z-1,N)$ equals one of the three prime factors of $N$.
\end{enumerate}
Comment: if we pick a random nonzero $a\in \ZZ_N$, then it is very likely that $a\in \ZZ_N^*$ (and if not, then $\gcd(a,N)$ will give a nontrivial factor of $N$, such as $p$ or $qr$).  For $a\in \ZZ_N^*$, we know $a^{N'}\equiv 1\pmod{N}$.  Consider the sequence $a^{N'}$, $a^{N'/2}$, \ldots, $a^{N'/{2^t}}$, where $t$ is the number of two's in the prime factorization of $N'$.  It can be shown that with probability at least $3/4$, there exists $j$ with $0\le j < t$ such that $a^{N'/{2^j}} \equiv 1\pmod{N}$ but $a^{N'/2^{j+1}} \not\equiv 1\pmod{N}$ and $a^{N'/2^{j+1}} \not\equiv -1\pmod{N}$.

\item We are given integers $N$ and $N'$ below, where $N=pqr$ for distinct primes $p$, $q$, and $r$, and $N'=(p-1)(q-1)(r-1)$.  Use the technique discussed in the previous problem to factor $N$ into $p$, $q$, and $r$.
\begin{align*}
N = ~
&72574282558749478121831961777522352979922891373732\\
&52640081888768849043774022906446542805410221085953\\
&00320753253765830617357759810616109946937994358826\\
&06986514546697691739228771789807430161740480008459\\
&94519388579818777093657700884011035146955891511632\\
&70929871604931894785301810967243572125489584556940\\
&45473107493737916010001372683015487240076263495755\\
&41741391564430620495878448206248824390176132499743\\
&08464723507896655471450786645437290981254061675506\\
&591968920507\\
\\
N' = ~
&72574282558749478121831961777522352979922891373732\\
&52640081888768849043774022906446542805410221085953\\
&00320753253765830617357759810616109946937994358826\\
&06962150459726539985546509445091036999523033880687\\
&58640992957060218013371880785638527490838866766191\\
&73477424917381568854124195679472206337664104285772\\
&87792424246967982171313723487443851203509397176816\\
&39436095420869102811572345353957338637093468469585\\
&20585013311419045148556822618738932355904529716212\\
&332777917280
\end{align*}

\end{enumerate}
\end{document}
