Alice knows a prime p, a primitive root g, and an exponent k, and wants to compute g^k mod p. Bob knows p, g, and the value a = g^k mod p, and wants to find k. Whose problem is computationally harder?
AAlice's — exponentiation mod p requires inspecting every power of g
BBob's — finding k from g^k mod p is believed to be computationally infeasible for large p
CBoth are equally hard — modular arithmetic is always expensive
DNeither — both problems reduce to prime factorization
Alice's problem (computing g^k mod p given k) is easy: repeated squaring solves it in O(log k) multiplications regardless of how large p is. Bob's problem (recovering k from g^k mod p) is the discrete logarithm problem, believed to require time exponential in the size of p for the best known algorithms on general groups. This asymmetry — fast forward, slow reverse — is precisely what Diffie-Hellman and elliptic-curve cryptography exploit. Option D is wrong: discrete logs are not believed to reduce to factoring, which is why breaking one cryptosystem does not break the other.
Question 2 Multiple Choice
In the group (Z/pZ)*, we have log_g(ab) ≡ log_g(a) + log_g(b) (mod p-1). Which of the following best explains why this law holds?
AIt holds because multiplication distributes over addition in modular arithmetic
BIt mirrors ordinary logarithm laws because the group is cyclic of order p-1 and g is a generator
CIt is a coincidence that only applies when p is prime
DIt follows from the fact that g^k is always greater than g^j when k > j
The discrete log law is a direct consequence of the group structure. Since g generates (Z/pZ)*, we have g^k · g^j = g^(k+j). Taking the discrete log of both sides: log_g(g^k · g^j) = k + j = log_g(g^k) + log_g(g^j). The exponents live in Z/(p-1)Z (because g^(p-1) ≡ 1), so addition is mod p-1 — exactly the same reason ordinary logs have log(xy) = log(x) + log(y): in both cases the underlying operation on exponents is addition in a suitable group.
Question 3 True / False
The discrete logarithm obeys additive laws that mirror ordinary logarithms: log_g(ab) ≡ log_g(a) + log_g(b) (mod p-1).
TTrue
FFalse
Answer: True
True. Because g is a generator of the cyclic group (Z/pZ)* of order p-1, every nonzero residue is a unique power of g. Multiplying two residues g^j and g^k gives g^(j+k), so the discrete log of a product equals the sum of the individual discrete logs — exactly as with ordinary logarithms. The addition takes place mod p-1 because the exponents cycle with period p-1.
Question 4 True / False
Using a larger prime p makes the forward computation g^k mod p slower, which is why large primes improve cryptographic security.
TTrue
FFalse
Answer: False
False — this reverses the relevant asymmetry. The forward computation g^k mod p uses repeated squaring and costs O(log k · log²p) bit operations, which grows very slowly as p increases. It is the *inverse* computation (finding k from g^k mod p) that becomes harder as p grows, because the best algorithms (baby-step giant-step, index calculus) have running times that grow with p. Cryptographic security comes from making the *reverse* problem hard, not the forward problem.
Question 5 Short Answer
What makes the discrete logarithm problem a 'one-way function,' and why is this property essential for cryptographic key exchange?
Think about your answer, then reveal below.
Model answer: Computing g^k mod p given g, k, and p is fast (O(log k) multiplications via repeated squaring), but recovering k given g, p, and g^k mod p is believed to require time exponential in the bit-length of p. This asymmetry means two parties can publicly exchange values derived from discrete exponentiation without an eavesdropper being able to recover the secret exponents — the basis of Diffie-Hellman.
The one-way property is not proved but is a widely believed computational hardness assumption. Diffie-Hellman works because Alice can publish g^a mod p and Bob can publish g^b mod p; Alice computes (g^b)^a = g^ab and Bob computes (g^a)^b = g^ab — the same shared secret — while an eavesdropper would need to solve the discrete log problem to recover a or b from the public values.