Discrete Logarithm
Discrete logarithm: given g and h, find the integer x with g^x=h (mod p); it is the security basis of Diffie-Hellman and DSA.
Purpose
To understand the security assumption behind public-key cryptography and analyze discrete-log hardness.
Mechanism
Solve for x in a group of order n. Generic algorithms (BSGS, Pollard rho) cost O(√n). Special groups (smooth order) allow Pohlig-Hellman decomposition. The index calculus method is subexponential for certain groups.
Use cases
- Cryptographic security analysis
- DH parameter selection
- Number theory