18.18 Discrete Logarithms

Ordinary logarithms answer the question:

a^x = b

What is x?

Discrete logarithms ask the same question in modular arithmetic:

g^x ≡ h (mod p)

Given:

g
h
p

find:

Unlike ordinary logarithms, there is no simple closed-form formula. For sufficiently large primes, finding x is computationally difficult. This difficulty forms the foundation of many public-key cryptographic systems.

From an algorithmic perspective, discrete logarithms are a fascinating inverse problem. Modular exponentiation is easy. Recovering the exponent is hard.

Problem

Given:

g^x ≡ h (mod p)

find:

Example:

3^x ≡ 5 (mod 7)

Compute powers of 3:

3^0 ≡ 1
3^1 ≡ 3
3^2 ≡ 2
3^3 ≡ 6
3^4 ≡ 4
3^5 ≡ 5

Therefore:

x = 5

This works for tiny examples, but brute force quickly becomes impossible.

Existence of Solutions

Suppose:

is a primitive root modulo prime:

Then every nonzero residue can be written uniquely as:

g^x

for some:

0 ≤ x < p-1

In this case, a discrete logarithm always exists.

Example:

p = 7
g = 3

Since 3 is a primitive root modulo 7, every nonzero residue has a logarithm base 3.

If g is not a primitive root, only some residues can be represented.

Brute Force

The simplest approach computes powers until the target appears.

def discrete_log_bruteforce(g, h, p):
    value = 1

    for x in range(p):
        if value == h:
            return x

        value = value * g % p

    return None

Example:

print(discrete_log_bruteforce(3, 5, 7))

Output:

Complexity:

O(p)

This becomes impractical even for moderate primes.

Why the Problem Is Difficult

Modular exponentiation is easy.

pow(g, x, p)

runs in:

O(log x)

using fast exponentiation.

The inverse problem appears much harder.

Given:

g^x mod p

recovering:

has no known polynomial-time algorithm for general groups.

This asymmetry is the basis of discrete-logarithm cryptography.

Baby-Step Giant-Step

The standard practical algorithm for moderate-sized inputs is the Baby-Step Giant-Step algorithm developed by entity["people","Daniel Shanks","American mathematician"].

The idea is to split the exponent:

x = im + j

where:

m ≈ √p

Then:

g^(im+j)
=
g^(im)g^j

Rearrange:

h(g^-m)^i
=
g^j

The algorithm precomputes one side and searches for matches.

Instead of:

O(p)

work, it requires roughly:

O(√p)

time and memory.

Example

Solve:

2^x ≡ 5 (mod 13)

Compute:

m = ⌈√13⌉ = 4

Baby steps:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8

Store:

Now compute giant steps using:

2^-4 mod 13

Since:

2^4 = 16 ≡ 3

and:

3^-1 ≡ 9

we repeatedly multiply by 9.

Eventually a match occurs, yielding:

x = 9

Verification:

2^9 = 512
512 mod 13 = 5

Correct.

Implementation

from math import isqrt

def discrete_log_bsgs(g, h, p):
    m = isqrt(p) + 1

    baby = {}

    value = 1

    for j in range(m):
        if value not in baby:
            baby[value] = j

        value = value * g % p

    factor = pow(pow(g, m, p), p - 2, p)

    gamma = h

    for i in range(m):
        if gamma in baby:
            return i * m + baby[gamma]

        gamma = gamma * factor % p

    return None

Example:

print(discrete_log_bsgs(2, 5, 13))

Output:

Complexity

Let:

n = p-1

Brute force:

O(n)

Baby-Step Giant-Step:

O(√n)

time and:

O(√n)

memory.

This is a dramatic improvement.

For:

n = 10^12

the search space shrinks from:

10^12

to roughly:

10^6

operations.

Pollard's Rho for Logarithms

Baby-Step Giant-Step requires large memory.

Pollard's Rho for discrete logarithms uses pseudorandom walks to reduce memory usage.

Complexity:

Expected O(√n)

time and:

O(1)

memory.

The algorithm is considerably more sophisticated but is often preferred for very large groups.

The same idea appears in Pollard's Rho factorization.

Discrete Logarithms in Finite Fields

For prime modulus:

the multiplicative group contains:

p - 1

elements.

If:

is primitive, every nonzero residue has a logarithm.

Example:

mod 11

Primitive root:

g = 2

Powers:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 5
2^5 = 10
2^6 = 9
2^7 = 7
2^8 = 3
2^9 = 6
2^10 = 1

Thus:

log₂(6) = 9

modulo 11.

Logarithm Tables

For small moduli, precomputing logarithms is practical.

def log_table(g, p):
    table = {}

    value = 1

    for x in range(p - 1):
        table[value] = x
        value = value * g % p

    return table

Example:

logs = log_table(2, 11)

print(logs[6])

Output:

This turns discrete logarithm queries into constant-time lookups.

Diffie-Hellman

The classic Diffie-Hellman protocol relies directly on the difficulty of discrete logarithms.

Public parameters:

prime p
primitive root g

Alice chooses:

and sends:

g^a mod p

Bob chooses:

and sends:

g^b mod p

Both compute:

g^(ab) mod p

An attacker sees:

g
g^a
g^b

but must solve discrete logarithms to recover:

or:

The security depends on that problem being computationally difficult.

ElGamal Encryption

The ElGamal cryptosystem also relies on discrete logarithms.

Public key:

g^x

Private key:

Recovering:

from:

g^x

is exactly a discrete logarithm problem.

Index Calculus

For very large prime fields, the fastest known algorithms are based on index calculus.

Complexity is roughly:

exp(
√(log p log log p)
)

which is substantially faster than:

√p

for extremely large primes.

This is why cryptographic systems require carefully chosen parameter sizes.

Elliptic Curve Discrete Logarithms

In elliptic curve cryptography, the analogous problem is:

Q = kP

Given:

P
Q

find:

This is the elliptic curve discrete logarithm problem.

No index-calculus-style attack is known for general elliptic curves.

As a result, elliptic curve systems achieve comparable security with much smaller key sizes.

Common Mistakes

Assuming Every Residue Has a Logarithm

This is true only when the base generates the entire multiplicative group.

Primitive roots guarantee this property.

Forgetting Modulo p−1

Exponents in a cyclic group are taken modulo:

p-1

for prime modulus p.

Using Brute Force for Large Inputs

The complexity grows linearly.

Use Baby-Step Giant-Step or better algorithms.

Confusing Logarithms and Inverses

The equation:

g^x ≡ h

is fundamentally different from:

ax ≡ b

The latter is a linear congruence.

Ignoring Memory Costs

Baby-Step Giant-Step requires:

O(√n)

storage.

For very large groups, this becomes a limiting factor.

Testing

Basic examples:

def test_discrete_log():
    assert discrete_log_bsgs(2, 5, 13) == 9
    assert discrete_log_bsgs(3, 5, 7) == 5

Verification:

def verify(g, h, p):
    x = discrete_log_bsgs(g, h, p)

    if x is None:
        return False

    return pow(g, x, p) == h

Property test:

for p in [7, 11, 13, 17]:
    g = primitive_root_prime(p)

    for x in range(p - 1):
        h = pow(g, x, p)

        assert discrete_log_bsgs(g, h, p) == x

This verifies correctness across all residues generated by the primitive root.

Takeaway

Discrete logarithms reverse modular exponentiation. Given g^x ≡ h (mod p), the goal is to recover the exponent x. While modular exponentiation is easy, no efficient general solution for the inverse problem is known. Baby-Step Giant-Step reduces the search from O(p) to O(√p), while more advanced methods such as Pollard's Rho and index calculus improve performance in specific settings. The hardness of discrete logarithms underpins Diffie-Hellman, ElGamal, and many other cryptographic systems.