\documentclass{article}
\usepackage{amsmath,amssymb,geometry}
\geometry{margin=0.75in}

\title{Exercise 3 Cheat Sheet -- RSA}
\date{}
\author{}

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Recognition}

\begin{itemize}
\item \textbf{(a)} Given $p,q,e,c$ $\rightarrow$ RSA decryption.
\item \textbf{(b)} Given $n,e,d$ $\rightarrow$ Factor $n$ using $ed-1$.
\item \textbf{(c)} Count bases causing the factorization algorithm to stop at a given step.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Key Formulas}

\[
n=pq,\qquad
\phi(n)=(p-1)(q-1),
\]

\[
ed\equiv1\pmod{\phi(n)},
\]

\[
m=c^d\pmod n,
\]

\[
k=ed-1=2^st,\qquad t\text{ odd}.
\]

\[
\boxed{ed-1\text{ is a multiple of }\phi(n)}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{A. RSA Decryption}

\[
\phi=(p-1)(q-1)
\]

\[
d=e^{-1}\pmod\phi
\]

\[
m=c^d\pmod n
\]

\textbf{GAP}

\begin{verbatim}
phi := (p-1)*(q-1);
InverseMod(e,phi);
PowerMod(c,d,n);
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{B. Factoring $n$ from $d$}

\begin{enumerate}
\item Compute
\[
k=ed-1=2^st.
\]

\item Compute
\[
x=a^t\pmod n.
\]

If $x=\pm1$, the base fails.

\item Repeat

\[
y=x^2\pmod n.
\]

If $y\neq1$, set $x\leftarrow y$.

Stop when

\[
y=1
\quad\text{and}\quad
x\neq\pm1.
\]

\item Recover

\[
\boxed{
p=\gcd(x-1,n),\qquad
q=\gcd(x+1,n)
}
\]

Verify $pq=n$.
\end{enumerate}

\textbf{GAP}

\begin{verbatim}
PowerMod(a,t,n);
PowerMod(x,2,n);

Gcd(x-1,n);
Gcd(x+1,n);

FactorsInt(n);
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{C. Count Bases Found at Step $t$}

Let

\[
k=2^sm,
\]

and define

\[
E=2^tm.
\]

Suppose the desired factor is $p$ and the other prime is $q$.

\bigskip

Modulo $p$:

\[
x^{2E}\equiv1,
\qquad
x^E\not\equiv1.
\]

\[
\boxed{
N_p=
\gcd(2E,p-1)-\gcd(E,p-1)
}
\]

Modulo $q$:

\[
x^{2E}\not\equiv1.
\]

\[
\boxed{
N_q=(q-1)-\gcd(2E,q-1)
}
\]

By CRT,

\[
\boxed{
N=N_pN_q.
}
\]

Useful fact:

\[
\boxed{
\#\{x:x^r\equiv1\pmod p\}
=
\gcd(r,p-1)
}
\]

\textbf{GAP}

\begin{verbatim}
Gcd(2*E,p-1);
Gcd(E,p-1);

Gcd(2*E,q-1);

ChineseRem([a,b],[p,q]);
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Remember}

\begin{itemize}
\item $ed-1\neq\phi(n)$ in general.
\item $t$ must be odd.
\item If $a^t=\pm1$, choose another base.
\item Stop at the \emph{first} occurrence of $y=1$.
\item Always verify $pq=n$.
\end{itemize}

\end{document}