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:

2. ElGamal Basics

Public key:

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

Secret key:

x

Encryption:

B ≡ αb (mod p), C ≡ m · Ab (mod p)

Ciphertext: (B, C)

Decryption:

m ≡ C · (Bx)−1 (mod p)

Inverse:

(Bx)−1 ≡ (Bx)p−2 (mod p)

3. Fast ElGamal Procedures

Encryption

Input: m, b, p, α, A

  1. B ≡ αb (mod p)
  2. K ≡ Ab (mod p)
  3. C ≡ m · K (mod p)
  4. Output (B, C)

Decryption

Input: (B, C), x

  1. K ≡ Bx (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 = Π qiei

Solve x mod qiei, then combine via CRT.

5. Core Algorithm

Step 1: Factor group order

p−1 = Π qiei
GAP 
FactorsInt(p-1);

Step 2: Work modulo one prime power qe

Compute:

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

Table:

g0, g1, …, gq−1

Step 3: First digit

Find:

h = gx₀ ⇒ 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 xi:

h = A(p−1)/qi+1 ⇒ h = gxi

Then remove:

A ← A · α−xi·qi

Repeat until all digits are found.

Step 6: Reconstruct solution

x = x₀ + x₁·q + x₂·q² + … + xe−1·qe−1

This gives:

x mod qe

Step 7: Combine with CRT

After computing all residues:

x ≡ ai (mod qiei)
GAP 
ChineseRem([a1, a2, ...], [m1, m2, ...]);

Final result:

x mod (p−1)

6. Exam Strategy (Optimized)

Key Insight

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