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

\title{Crypto Exam Formula Card: Fermat + Miller--Rabin + CRT (with GAP)}
\date{}
\author{}

\begin{document}
\maketitle

\section*{1. Setup (always first)}

Let:
\[
n = pq \quad (p,q \text{ primes})
\]

Split everything:
\[
x \bmod n \leftrightarrow (x \bmod p,\; x \bmod q)
\]

Final count always:
\[
\boxed{N = N_p \cdot N_q}
\]

\subsection*{GAP check}
\begin{verbatim}
p := 433;; q := 1153;;
n := p*q;;
IsPrime(p); IsPrime(q);
\end{verbatim}

---

\section*{2. Fermat pseudoprimes}

Condition:
\[
a^{n-1} \equiv 1 \pmod n
\]

Count:
\[
\boxed{
N_p = \gcd(n-1,p-1), \quad N_q = \gcd(n-1,q-1)
}
\]

\[
\boxed{
N = \gcd(n-1,p-1)\cdot \gcd(n-1,q-1)
}
\]

\subsection*{GAP check}
\begin{verbatim}
Gcd(n-1, p-1);
Gcd(n-1, q-1);
\end{verbatim}

---

\section*{3. Miller--Rabin (only rule you need)}

Write:
\[
n-1 = 2^s d \quad (d \text{ odd})
\]

Compute:
\[
a^d,\; a^{2d},\; a^{4d},\dots,a^{2^s d}
\]

\textbf{PASS iff:}
\[
\boxed{
a^d \equiv 1 \;\; \text{OR} \;\; \exists i:\ a^{2^i d} \equiv -1
}
\]

Otherwise: witness.

\subsection*{GAP check}
\begin{verbatim}
n := 499249;;
Factors(n-1);
\end{verbatim}

---

\section*{4. Pattern shortcut (MR counting)}

If sequence pattern is:
\[
*,\; *,\; -1,\; 1
\]

Then:
\[
a^{4d} \equiv -1,\quad a^{8d} \equiv 1
\]

Count in cyclic group of size \(m\):
\[
\boxed{
\#(x^k=1) = \gcd(k,m)
}
\]

So:

\[
\boxed{
N_p = \gcd(8d,p-1) - \gcd(4d,p-1)
}
\]
\[
\boxed{
N_q = \gcd(8d,q-1) - \gcd(4d,q-1)
}
\]

Final:
\[
\boxed{
N = N_p N_q
}
\]

\subsection*{GAP check}
\begin{verbatim}
Gcd(8*d, p-1) - Gcd(4*d, p-1);
Gcd(8*d, q-1) - Gcd(4*d, q-1);
\end{verbatim}

---

\section*{5. Miller--Rabin Construction ($*,*, -1, 1$)}

Goal:
\[
*,\;*,\;-1,\;1 \Longleftrightarrow a^{4d} \equiv -1,\; a^{8d} \equiv 1
\]

Split:
\[
n = pq,\quad \text{solve mod } p \text{ and } q
\]

Final:
\[
a \equiv a_p \pmod p,\quad a \equiv a_q \pmod q
\]

\subsection*{GAP check}
\begin{verbatim}
ChineseRem([a_p, a_q], [p, q]);
\end{verbatim}

---

\subsection*{Step 1: Generator form}

Let $g$ generate $(\mathbb{Z}/p\mathbb{Z})^*$:
\[
a_p = g^k
\]

\subsection*{GAP check}
\begin{verbatim}
g := PrimitiveRootMod(p);
\end{verbatim}

---

\subsection*{Step 2: Fix target value}

\[
g^\ell \equiv -1 \pmod p
\quad \Rightarrow \quad \ell = \frac{p-1}{2}
\]

\subsection*{GAP check}
\begin{verbatim}
PowerMod(g, (p-1)/2, p);   # should give -1 mod p
\end{verbatim}

---

\subsection*{Step 3: Exponent equation}

\[
4d \cdot k \equiv \ell \pmod{p-1}
\]

Solve:
\[
k \equiv (4d)^{-1}\ell \pmod{p-1}
\]

Then:
\[
a_p = g^k
\]

Repeat for $q$.

\subsection*{GAP check}
\begin{verbatim}
k := (4*d)^-1 * ((p-1)/2) mod (p-1);
PowerMod(g, k, p);
\end{verbatim}

---

\subsection*{Step 4: Combine}

\[
a \equiv a_p \pmod p,\quad a \equiv a_q \pmod q
\]

---

\subsection*{Step 5: Second solution}

If $a$ works, then:
\[
n-a
\]
also works.

\subsection*{GAP check}
\begin{verbatim}
PowerMod(n-a, 4*d, n);
\end{verbatim}

---

\subsection*{Workflow summary}

\begin{itemize}
\item write $a = g^k$
\item replace $-1$ by $(p-1)/2$
\item solve $4dk \equiv (p-1)/2$
\item build $a_p, a_q$
\item CRT
\end{itemize}

\end{document}