g^x ≡ h (mod p)

B = {2, 3, 5, 7, 11, ...}

Now, the real work begins. We're going to generate a ton of equations. We do this by picking a random exponent k and calculating:

g^k (mod p)

Then, we check if the result is "smooth" over our factor base. A number is B-smooth if all of its prime factors are in our factor base B.

Let's say our factor base is {2, 3, 5}. The number 12 = 2^2 * 3 is smooth. The number 90 = 2 * 3^2 * 5 is smooth. The number 14 = 2 * 7 is not smooth because 7 isn't in our base.

Here's the loop a programmer would write (in pseudocode):

relations = []
factor_base = [2, 3, 5, 7, 11, ...]

while len(relations) < len(factor_base) + a_bit_more:
    k = random_integer_between(1, p - 1)
    y = pow(g, k, p)

    # Try to factor y using only primes from our base
    exponents = try_to_factor(y, factor_base)

    if exponents is not None: # It's a smooth number!
        # We found a relation: g^k ≡ p1^e1 * p2^e2 ... (mod p)
        relations.append((k, exponents))
        print(f"Found relation! {len(relations)}/{len(factor_base)}")

Every time we find a smooth number, we've found a "relation." For example, we might find that for k = 428, `g^428 ≡ 2^3 * 5^1 * 11^2 (mod p)`.

Step 3: From Relations to Linear Algebra

This is where the magic happens. If we take the discrete log of both sides of our relation, we get a linear equation. Remember that log(a*b) = log(a) + log(b).

Our relation `g^428 ≡ 2^3 * 5^1 * 11^2 (mod p)` becomes:

log(g^428) ≡ log(2^3 * 5^1 * 11^2) (mod p-1)

(Note: The modulus changes to p-1 because of Fermat's Little Theorem. It's a key detail!)

This simplifies to:

428 ≡ 3*log(2) + 1*log(5) + 2*log(11) (mod p-1)

We have one equation with several unknowns: log(2), log(5), and log(11). These are the values we want for our database!

If we collect enough of these relations (a few more than the number of primes in our factor base), we get a system of linear equations. For example:

k1 ≡ a1*log(p1) + a2*log(p2) + ...
k2 ≡ b1*log(p1) + b2*log(p2) + ...
k3 ≡ c1*log(p1) + c2*log(p2) + ...
...

This is a classic Ax = b problem from linear algebra. We can use techniques like Gaussian elimination to solve for the unknowns: log(p1), log(p2), etc. The catch is that this math must be done modulo p-1, which requires a specialized linear algebra solver (you won't just plug this into NumPy).

Once solved, we have our database! We know the discrete logs of all the small primes in our factor base.

The Payoff: Finding the Logarithm We Actually Want

Now we go back to our original problem: find x where g^x ≡ h (mod p). The hard part is over.

We perform a similar trick. We pick a random integer s, and compute:

y = (h * g^s) (mod p)

We keep trying random values of s until we find a y that is smooth over our factor base. Because h and g are essentially random, this doesn't take too long.

Let's say we get lucky with s = 99 and find that `h * g^99 ≡ 2^5 * 7^1 (mod p)`.

Again, we take the log of both sides:

log(h) + log(g^99) ≡ 5*log(2) + 1*log(7) (mod p-1)

Which simplifies to:

log(h) + 99 ≡ 5*log(2) + 1*log(7) (mod p-1)

But wait! We already know log(2) and log(7) from our preprocessing step! We can just plug them in and solve for log(h) with simple arithmetic.

log(h) ≡ (5*log(2) + 1*log(7) - 99) (mod p-1)

And that's it! We've found x = log(h). We've cracked the discrete logarithm.

What Actually Works: The Programmer's Reality

So, can you fire up a Python script and break modern crypto? Not quite. Here's the reality check:

• Complexity is Key: Index Calculus is a sub-exponential algorithm. It's vastly superior to exponential brute-force, but it's still incredibly slow for the parameter sizes used in real-world cryptography (e.g., 2048-bit primes).
• Sieving is the Bottleneck: The hardest part by far is Step 2, finding enough smooth relations. For large primes, the probability of a random number being smooth is astronomically low. Modern attacks use highly advanced sieving techniques (like the Number Field Sieve, or NFS) that are conceptually related but far more complex.
• The Linear Algebra is Non-Trivial: Solving a massive system of equations over a finite field (modulo p-1) requires specialized libraries and a lot of memory. The matrices involved can be huge but are also very sparse, which can be exploited.
• This is Why We Can't Have Small Primes: This attack is the very reason cryptographic standards demand such large prime numbers for p. The difficulty of the Index Calculus attack (and its descendants) grows very quickly with the size of p. It's also why certain "special" primes (that might make finding smooth numbers easier) are avoided.

Conclusion: A Beautiful Attack

The Index Calculus algorithm is a beautiful piece of computational number theory. It shows how a seemingly impossible problem can be broken down into more manageable parts: factorization and linear algebra.

For a programmer, it's not a tool you'll likely implement to break a real system. But understanding its logic gives you a deep appreciation for the invisible arms race of cryptography. It explains why parameter choices matter, why key sizes have to be so large, and how attackers think. It's a reminder that security often relies on making a problem just computationally expensive enough for our current technology and algorithms—a line that is constantly shifting.