gen-define-the-discrete-logarithm-problem-and-give-one-short-wor-9901

Define the discrete logarithm problem and give one short worked example.

# Discrete Logarithm Problem (DLP) ## Definition Given: - A cyclic group G with generator g - An element h ∈ G **Find:** The integer x such that g^x = h (if it exists) The integer x is called the **discrete logarithm** of h to the base g, often written as x = log_g(h). This problem is computationally hard in certain groups (like large prime-order subgroups), which makes it useful for cryptography. ## Worked Example Let's work in the multiplicative group **Z*₁₇** (integers mod 17). **Given:** - Generator g = 3 - Target element h = 12 - Prime p = 17 **Find:** x such that 3^x ≡ 12 (mod 17) **Solution** (by trial for small example): - 3¹ ≡ 3 (mod 17) - 3² ≡ 9 (mod 17) - 3³ ≡ 27 ≡ 10 (mod 17) - 3⁴ ≡ 30 ≡ 13 (mod 17) - 3⁵ ≡ 39 ≡ 5 (mod 17) - 3⁶ ≡ 15 (mod 17) - 3⁷ ≡ 45 ≡ 11 (mod 17) - 3⁸ ≡ 33 ≡ 16 (mod 17) - 3⁹ ≡ 48 ≡ 14 (mod 17) - 3¹⁰ ≡ 42 ≡ 8 (mod 17) - 3¹¹ ≡ 24 ≡ 7 (mod 17) - 3¹² ≡ 21 ≡ 4 (mod 17) - 3¹³ ≡ 12 (mod 17) ✓ **Answer:** x = 13