Offensive Security Researcher & Quantum Cryptography Analyst

Discrete Logarithm Generation Algorithm: Working, Explanation, and Cryptography

Abdul Wahab Junaid
discrete logarithm generation algorithm and working of this algorithm

discrete logarithm generation algorithm and working of this algorithm

I think the discrete logarithm problem is one of the two or three pillars that modern public-key cryptography rests on, alongside integer factorization. Whenever I explain Diffie-Hellman key exchange, ElGamal encryption, DSA signatures, or elliptic curve cryptography to someone, I always end up circling back to this one core idea: in certain mathematical groups, computing $g^x \bmod p$ is easy, but going backwards — given $g$, $p$, and $g^x \bmod p$, finding $x$ — is believed to be extremely hard. That asymmetry, that one-way difficulty, is what I want to unpack in this file, covering both how discrete logs are generated/used constructively and the algorithms used to attack (compute) them.

History and Background

I trace the discrete logarithm problem’s cryptographic relevance to Whitfield Diffie and Martin Hellman’s 1976 paper “New Directions in Cryptography,” which introduced the Diffie-Hellman key exchange — the very first published public-key construction, built directly on the presumed hardness of the discrete log problem in the multiplicative group of integers modulo a prime. Taher ElGamal extended this in 1985 into a full public-key encryption and signature scheme. On the attacking side, algorithms for actually computing discrete logarithms have a long history reaching back to Gauss-era number theory, but the modern algorithmic attacks I care about here — Baby-step Giant-step (Shanks, 1971), Pollard’s rho method (1978), the Pohlig-Hellman algorithm (1978), and index calculus methods — were developed through the 1970s and refined ever since, directly shaping how large cryptographic parameters need to be chosen to stay secure.

Problem Statement

Formally, given a finite cyclic group $G$ with generator $g$, and given an element $h \in G$ such that $h = g^x$ for some integer $x$, the discrete logarithm problem asks me to find $x$. In the cryptographically relevant case, $G$ is usually the multiplicative group of integers modulo a large prime $p$ (or a subgroup of it), or the group of points on an elliptic curve. The “generation” side of this topic is about how I construct secure parameters (choosing $g$, $p$, and the group structure) so that the discrete log problem is hard in that group; the “computation” side is about the algorithms an attacker (or a legitimate party solving a known-hard cryptanalysis benchmark) would use to actually try to recover $x$.

Core Concepts

How It Works

I’ll describe both directions: generating secure discrete-log parameters, and computing a discrete log (as an attacker would).

Parameter generation (defender’s side):

  1. I choose a large prime $p$, ideally a “safe prime” where $q = (p-1)/2$ is also prime, to avoid small subgroup attacks.
  2. I find a generator $g$ of a large-order subgroup of $\mathbb{Z}_p^*$ (often the subgroup of order $q$), by testing candidate values and confirming their multiplicative order is large.
  3. I publish $p$ and $g$ as public parameters. A private key $x$ is chosen randomly, and the corresponding public value $h = g^x \bmod p$ is published, while $x$ remains secret.

Baby-step Giant-step (attacker’s side), to compute $x$ given $g, h, p, n$ (group order):

  1. I compute $m = \lceil \sqrt{n} \rceil$.
  2. I build a table of “baby steps”: for each $j$ from $0$ to $m-1$, I compute and store $g^j \bmod p$.
  3. I compute the “giant step” factor $g^{-m} \bmod p$.
  4. Starting with $\gamma = h$, I repeatedly check whether $\gamma$ matches any entry in my baby-step table; if it does, at iteration $i$ with match at $j$, then $x = i \cdot m + j$.
  5. If no match, I update $\gamma = \gamma \cdot g^{-m} \bmod p$ and try again, up to $m$ giant steps.

Pollard’s rho (attacker’s side), an alternative that saves memory:

  1. I define a pseudo-random iteration function that partitions group elements into a small number of sets and updates a running value using $g$ and $h$ exponents depending on which set the current value falls into.
  2. I run two “walkers” through this sequence at different speeds (tortoise and hare), watching for a collision (the same group element reached via two different exponent combinations).
  3. Once a collision is found, the difference in the accumulated exponents gives me a linear equation in $x$, which I solve (often via modular inverse, handling the case of a shared factor with the group order carefully).

Working Principle

I think of the discrete logarithm’s hardness as coming from the fact that exponentiation in these groups mixes information in a way that’s easy to compute forward (via fast modular exponentiation, exploiting the structure of repeated squaring) but has no known efficient “undo” operation in a generic group — unlike, say, ordinary real-number logarithms, which have closed-form inverses. Baby-step giant-step exploits a simple algebraic rewriting: any exponent $x$ less than $n$ can be written as $x = im + j$ for $0 \le i, j < m$, turning the search into two smaller searches that meet in the middle, at the cost of needing $O(\sqrt{n})$ storage. Pollard’s rho instead relies on the birthday paradox: a pseudo-random walk over a group of size $n$ is expected to produce a collision after roughly $O(\sqrt{n})$ steps, and because the walk’s structure ties each element to a specific combination of $g$ and $h$ exponents, a collision translates directly into a linear equation revealing $x$ — all without needing to store the whole path, unlike baby-step giant-step.

Mathematical Foundation

The discrete logarithm problem: given $g, h \in G$ with $h = g^x$, find $x$ such that:

$$g^x \equiv h \pmod{p}$$

Baby-step giant-step decomposition, writing $x = i m + j$ with $m = \lceil \sqrt{n} \rceil$:

$$h = g^{im+j} \implies h \cdot g^{-im} = g^{j} \implies h \cdot (g^{-m})^{i} = g^{j}$$

I search for a match between the baby-step table ${g^j : 0 \le j < m}$ and the giant-step sequence ${h \cdot (g^{-m})^i : 0 \le i < m}$.

Pollard’s rho collision equation: if two points in the pseudo-random walk collide, meaning $g^{a_1} h^{b_1} = g^{a_2} h^{b_2}$, then since $h = g^x$:

$$g^{a_1 + b_1 x} = g^{a_2 + b_2 x} \implies a_1 + b_1 x \equiv a_2 + b_2 x \pmod{n} \implies x \equiv \frac{a_1 – a_2}{b_2 – b_1} \pmod{n}$$

Pohlig-Hellman, for a group order $n = \prod p_i^{e_i}$, reduces the problem to computing $x \bmod p_i^{e_i}$ for each small prime power factor independently, then reconstructing $x$ via the Chinese Remainder Theorem:

$$x \equiv x_i \pmod{p_i^{e_i}} \text{ for each } i, \quad \text{combine via CRT to recover } x \bmod n$$

which is precisely why $n$ (the group order, or the order of the subgroup used) must have a large prime factor for the discrete log problem to remain hard.

Diagrams

flowchart TD
    A[Choose large prime p and generator g] --> B[Compute group order n = p-1 or subgroup order q]
    B --> C[Check n has a large prime factor - avoid Pohlig-Hellman weakness]
    C --> D[Publish g, p as system parameters]
    D --> E[Private key x chosen randomly]
    E --> F[Public key h = g^x mod p]
    F --> G[Discrete log problem: recover x from g,h,p - believed hard]

Pseudocode

// Baby-step Giant-step algorithm
function baby_step_giant_step(g, h, p, n):
    m = ceil(sqrt(n))
    table = empty_hash_map()
    for j in 0..m-1:
        table[pow_mod(g, j, p)] = j

    g_inv_m = pow_mod(mod_inverse(g, p), m, p)
    gamma = h

    for i in 0..m-1:
        if gamma in table:
            j = table[gamma]
            return i * m + j
        gamma = (gamma * g_inv_m) mod p

    return "no solution found"

// Pollard's rho for discrete logarithms (simplified)
function pollard_rho_dlog(g, h, p, n):
    define step(x, a, b):
        subset = x mod 3
        if subset == 0: return (x*x mod p, 2*a mod n, 2*b mod n)
        if subset == 1: return (x*g mod p, (a+1) mod n, b)
        return (x*h mod p, a, (b+1) mod n)

    x1, a1, b1 = 1, 0, 0
    x2, a2, b2 = 1, 0, 0

    repeat:
        x1, a1, b1 = step(x1, a1, b1)          // tortoise: one step
        x2, a2, b2 = step(x2, a2, b2)          // hare: two steps
        x2, a2, b2 = step(x2, a2, b2)
    until x1 == x2

    numerator = (a1 - a2) mod n
    denominator = (b2 - b1) mod n
    return (numerator * mod_inverse(denominator, n)) mod n

Step-by-Step Example

I’ll work a small example with Baby-step Giant-step, small enough to trace by hand.

  1. Let p = 23, and I choose g = 5, which is a primitive root modulo 23 (its powers generate all of 1..22). The group order is n = 22.
  2. Suppose the public value is h = 8, and I want to find x such that 5^x mod 23 = 8.
  3. I compute m = ceil(sqrt(22)) = 5.
  4. I build my baby-step table for j = 0..4: 5^0=1, 5^1=5, 5^2=25 mod 23=2, 5^3=10, 5^4=50 mod 23=4. Table: {1:0, 5:1, 2:2, 10:3, 4:4}.
  5. I compute g^-1 mod 23. Since 5*14 = 70 = 3*23+1, g^-1 = 14. Then g^-m = 14^5 mod 23. Computing stepwise: 14^2=196 mod23=12, 14^4=12^2=144 mod23=6, 14^5=6*14=84 mod23=84-69=15. So g^-m = 15.
  6. I start gamma = h = 8. Check if 8 is in my table — it’s not.
  7. Giant step i=1: gamma = 8*15 mod 23 = 120 mod 23 = 120-115=5. Check table: 5 is there, with j=1!
  8. So x = i*m + j = 1*5 + 1 = 6.
  9. I verify: 5^6 mod 23 = 15625 mod 23. Computing: 5^2=25mod23=2, 5^4=2^2=4, 5^6=5^4*5^2=4*2=8. Yes, 5^6 mod 23 = 8, confirming x = 6 is correct.

Time Complexity

Space Complexity

Baby-step Giant-step requires $O(\sqrt{n})$ space to store its lookup table, which becomes impractical for very large groups (a 128-bit security level would require storing roughly $2^{64}$ table entries, well beyond feasible memory). Pollard’s rho needs only $O(1)$ space for its core walk, which is why it’s the practical choice for attacking (or benchmarking) larger discrete log instances. Index calculus methods require more substantial space to store relations and perform linear algebra over a “factor base,” typically $O(L_p[1/3, c])$ as well, subexponential but still large for cryptographic-sized primes.

Correctness Analysis

I can verify Baby-step Giant-step’s correctness directly from the algebraic identity $x = im + j \implies h \cdot g^{-im} = g^j$: every valid exponent $x$ in the range $[0, n)$ has a unique representation as $im+j$ with $0 \le i, j < m$, so the algorithm is guaranteed to find a match within $m$ giant steps if a solution exists, and the match directly yields the correct $x$. Pollard’s rho’s correctness relies on the birthday-paradox argument: because the pseudo-random walk function is deterministic given the current state, and the state space is finite, the sequence must eventually cycle (enter a “rho” shape), and detecting the collision via Floyd’s cycle-detection (tortoise and hare) is guaranteed to terminate; the correctness of the recovered $x$ follows from the linear relationship between the accumulated exponents at the collision point, as I derived in the mathematical foundation section — though I do have to be careful about the case where $\gcd(b_2 – b_1, n) \ne 1$, which requires special handling since a modular inverse might not exist directly.

Advantages

Disadvantages

Applications

Discrete logarithm hardness underlies Diffie-Hellman key exchange (used constantly in TLS/SSL for establishing session keys), the Digital Signature Algorithm (DSA) and ElGamal signatures/encryption, and — in its elliptic curve form — Elliptic Curve Diffie-Hellman (ECDH) and ECDSA, which power much of modern TLS, SSH, cryptocurrency transaction signing, and secure messaging protocols. I also see discrete log algorithms (Baby-step Giant-step, Pollard’s rho) used directly in cryptanalysis research and in solving discrete log “challenge” problems used to benchmark real-world security margins.

Implementation in C

#include <stdio.h>
#include <stdint.h>
#include <math.h>

/* modular exponentiation: base^exp mod mod */
long long pow_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

/* extended Euclidean algorithm for modular inverse */
long long mod_inverse(long long a, long long m) {
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;
    a = ((a % m) + m) % m;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m; m = a % m; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}

/* Baby-step Giant-step: find x such that g^x = h (mod p), 0 <= x < n */
long long baby_step_giant_step(long long g, long long h, long long p, long long n) {
    long long m = (long long)ceil(sqrt((double)n));

    /* simple table: linear search for teaching clarity (a hash map
       would be used in a production implementation for speed) */
    long long *values = malloc(m * sizeof(long long));
    long long cur = 1;
    for (long long j = 0; j < m; j++) {
        values[j] = cur;
        cur = (cur * g) % p;
    }

    long long g_inv = mod_inverse(g, p);
    long long g_inv_m = pow_mod(g_inv, m, p);
    long long gamma = h % p;

    long long answer = -1;
    for (long long i = 0; i < m && answer == -1; i++) {
        for (long long j = 0; j < m; j++) {
            if (values[j] == gamma) {
                answer = i * m + j;
                break;
            }
        }
        gamma = (gamma * g_inv_m) % p;
    }

    free(values);
    return answer;
}

int main(void) {
    long long p = 23, g = 5, h = 8, n = 22; /* group order p-1 = 22 */

    long long x = baby_step_giant_step(g, h, p, n);

    printf("p = %lld, g = %lld, h = %lld\n", p, g, h);
    printf("Discrete log x such that g^x mod p = h: x = %lld\n", x);
    printf("Verification: g^x mod p = %lld\n", pow_mod(g, x, p));

    return 0;
}

Sample Input and Output

Input: p = 23, g = 5, h = 8, group order n = 22, solved with the Baby-step Giant-step implementation above.

Output:

p = 23, g = 5, h = 8
Discrete log x such that g^x mod p = h: x = 6
Verification: g^x mod p = 8

This matches my hand-worked example exactly.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version