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

\title{Exercise 4 Cheat Sheet\\ElGamal + Pohlig--Hellman}
\date{}
\author{}

\begin{document}

\maketitle

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

\section*{1. Problem Recognition}

Given
\[
(p,\alpha,A), \quad A \equiv \alpha^x \pmod p
\]

This is an ElGamal / discrete log setting.

Typical tasks:
\begin{itemize}
\item Encrypt / decrypt messages
\item Recover secret exponent \(x\) (Pohlig--Hellman)
\end{itemize}

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

\section*{2. ElGamal Basics}

Public key:
\[
(p,\alpha,A)
\quad \text{with } A=\alpha^x \bmod p
\]

Secret key:
\[
x
\]

Encryption:
\[
B=\alpha^b \bmod p,\quad
C=mA^b \bmod p
\]
Ciphertext: \((B,C)\)

Decryption:
\[
m = C \cdot (B^x)^{-1} \bmod p
\]

Inverse:
\[
(B^x)^{-1} \equiv (B^x)^{p-2} \bmod p
\]

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

\section*{3. Fast ElGamal Procedures}

\subsection*{Encryption}

Input: \(m,b,p,\alpha,A\)

\begin{enumerate}
\item \(B=\alpha^b \bmod p\)
\item \(K=A^b \bmod p\)
\item \(C=mK \bmod p\)
\item Output \((B,C)\)
\end{enumerate}

\subsection*{Decryption}

Input: \((B,C), x\)

\begin{enumerate}
\item \(K=B^x \bmod p\)
\item Compute \(K^{-1}\)
\item \(m=C K^{-1} \bmod p\)
\end{enumerate}

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

\section*{4. Pohlig--Hellman (Discrete Log)}

Goal:
\[
\alpha^x \equiv A \pmod p
\]

Use:
\[
p-1=\prod q_i^{e_i}
\]

Solve \(x \bmod q_i^{e_i}\), then combine via CRT.

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

\section*{5. Core Algorithm}

\subsection*{Step 1: Factor group order}

\[
p-1=\prod q_i^{e_i}
\]

GAP:
\begin{verbatim}
FactorsInt(p-1);
\end{verbatim}

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

\subsection*{Step 2: Work modulo one prime power \(q^e\)}

Compute:
\[
g=\alpha^{(p-1)/q}, \quad h=A^{(p-1)/q}
\]

Table:
\[
g^0, g^1, \dots, g^{q-1}
\]

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

\subsection*{Step 3: First digit}

Find:
\[
h=g^{x_0}
\Rightarrow x_0
\]

GAP:
\begin{verbatim}
PowerMod(alpha,(p-1)/q,p);
PowerMod(A,(p-1)/q,p);
\end{verbatim}

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

\subsection*{Step 4: Remove digit}

\[
A \leftarrow A \cdot \alpha^{-x_0}
\]

GAP:
\begin{verbatim}
A := A * InverseMod(PowerMod(alpha,x0,p),p);
\end{verbatim}

Now:
\[
A=\alpha^{q(x_1+x_2q+\cdots)}
\]

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

\subsection*{Step 5: Next digits}

For digit \(x_i\):

\[
h = A^{(p-1)/q^{i+1}}
\quad \Rightarrow \quad h=g^{x_i}
\]

Then remove:
\[
A \leftarrow A \cdot \alpha^{-x_i q^i}
\]

Repeat until all digits are found.

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

\subsection*{Step 6: Reconstruct solution}

\[
x=x_0+x_1q+x_2q^2+\cdots+x_{e-1}q^{e-1}
\]

This gives:
\[
x \bmod q^e
\]

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

\subsection*{Step 7: Combine with CRT}

After computing all residues:

\[
x \equiv a_i \pmod{q_i^{e_i}}
\]

GAP:
\begin{verbatim}
ChineseRem([a1,a2,...],[m1,m2,...]);
\end{verbatim}

Final result:
\[
x \bmod (p-1)
\]

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

\section*{6. Exam Strategy (Optimized)}

\begin{itemize}
\item Factor \(p-1\) first
\item Solve one \(q^e\) fully before moving on
\item Always reuse the same \(g\)-table
\item Let GAP handle powers + CRT
\item Never brute-force full log in \((\mathbb{Z}/p\mathbb{Z})^*\)
\end{itemize}

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

\section*{Key Insight}

Each step projects the problem into a subgroup of order \(q\), isolating one digit of \(x\) at a time.

\end{document}