# Exercise 4 Cheat Sheet
## ElGamal + Pohlig--Hellman

---

## 1. Problem Recognition

Given

    (p, α, A),    A ≡ α^x (mod p)

This is an ElGamal / discrete log setting.

Typical tasks:

- Encrypt / decrypt messages
- Recover secret exponent x (Pohlig--Hellman)

---

## 2. ElGamal Basics

Public key:

    (p, α, A)    with A ≡ α^x (mod p)

Secret key:

    x

Encryption:

    B ≡ α^b (mod p),    C ≡ m * A^b (mod p)

Ciphertext: (B, C)

Decryption:

    m ≡ C * (B^x)^(-1) (mod p)

Inverse:

    (B^x)^(-1) ≡ (B^x)^(p-2) (mod p)

---

## 3. Fast ElGamal Procedures

### Encryption

Input: m, b, p, α, A

1. B ≡ α^b (mod p)
2. K ≡ A^b (mod p)
3. C ≡ m * K (mod p)
4. Output (B, C)

### Decryption

Input: (B, C), x

1. K ≡ B^x (mod p)
2. Compute K^(-1)
3. m ≡ C * K^(-1) (mod p)

---

## 4. Pohlig--Hellman (Discrete Log)

Goal:

    α^x ≡ A (mod p)

Use:

    p-1 = Π q_i^e_i

Solve x mod q_i^e_i, then combine via CRT.

---

## 5. Core Algorithm

### Step 1: Factor group order

    p-1 = Π q_i^e_i

GAP:
```
FactorsInt(p-1);
```

---

### Step 2: Work modulo one prime power q^e

Compute:

    g ≡ α^((p-1)/q),    h ≡ A^((p-1)/q)

Table:

    g^0, g^1, ..., g^(q-1)

---

### Step 3: First digit

Find:

    h = g^x₀  ⇒  x₀

GAP:
```
PowerMod(alpha, (p-1)/q, p);
PowerMod(A, (p-1)/q, p);
```

---

### Step 4: Remove digit

    A ← A * α^(-x₀)

GAP:
```
A := A * InverseMod(PowerMod(alpha, x0, p), p);
```

Now:

    A = α^(q * (x₁ + x₂*q + ...))

---

### Step 5: Next digits

For digit x_i:

    h = A^((p-1)/q^(i+1))  ⇒  h = g^x_i

Then remove:

    A ← A * α^(-x_i * q^i)

Repeat until all digits are found.

---

### Step 6: Reconstruct solution

    x = x₀ + x₁*q + x₂*q² + ... + x_{e-1}*q^(e-1)

This gives:

    x mod q^e

---

### Step 7: Combine with CRT

After computing all residues:

    x ≡ a_i (mod q_i^e_i)

GAP:
```
ChineseRem([a1, a2, ...], [m1, m2, ...]);
```

Final result:

    x mod (p-1)

---

## 6. Exam Strategy (Optimized)

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

---

## Key Insight

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