The Discrete Logarithm Problem

Cryptography · Axiom Academy

LESSON The Discrete Logarithm Problem The computational hardness at the heart of modern cryptography 1. The Discrete Logarithm Problem The Discrete Logarithm Problem asks: given a generator g, a result h, and a modulus n, find the exponent x such that: The term "discrete" refers to the fact that we're working in a finite group (like integers modulo n) rather than the continuous real numbers where ordinary logarithms are defined. 2. Continuous vs. Discrete Logarithms In the continuous case (real numbers), computing logarithms is easy: But in the discrete case (modular arithmetic), finding x is computationally hard: 3. The Easy Direction: Modular Exponentiation Computing g^x mod n is efficient using the square-and-multiply algorithm (fast exponentiation). This runs in O(log x) time: This asymmetry—easy to compute forward, hard to reverse—creates a trapdoor function , the foundation of public-key cryptography. 4. The Hard Direction: Finding the Discrete Log Given g^x ≡ h (mod n), finding x is believed to be hard. The best known algorithms are subexponential but still impractical for large enough groups: Not all groups are suitable for cryptography. We need groups where the DLP is believed to be hard: 6. Related Problems: CDH and DDH The security of cryptographic protocols often relies on problems related to but potentially easier than DLP:

This is the written version of the interactive lesson above. See the full Cryptography course.