Why does Index Calculus work?

Question

I understand how the Index Calculus algorithm works - I know & understand the steps. I understand how the steps are derived. However, I am not able to figure out why it works.

I can understand why Pohlig-Hellman works - PH reduces the computation of the discrete log in $G$ to the computation of the discrete log in prime order subgroups of $⟨G⟩$. The PH algorithm allows your solve the DLP in the smaller subgroups and then combine the solutions using the Chinese Remainder Theorem to get the solution for the original DLP. I am looking for a similar theoretical explanation for Index Calculus

Why does Index Calculus work for solving a DLP?

Answer 1

Index calculus is based on two simple ideas:

1. Every integer can be written as a product of primes.
2. A system of linear equations in a small number of variables can be solved with enough independent equations.

Take for example the cyclic group $\mathbb{Z}/p$ with $p$ a prime and primitive root c. The elements $c^i$ (for $i=0,1,2,...,p-1$) are congruent modulo p to the integers $1,2,...,p-1$. These integers can be expressed with powers of the small number of primes $P_1,..., P_k $ smaller than $p$. If we know the index of each prime, then, because indices are additive modulo $p-1$, then we know the index of each element in our group.

So in this example the variables are the indices of the primes $P_j$ and the equations are given by $$c^i=\prod_j P_j^{r_j} \leadsto i=\sum_j r_j \operatorname{ind}(P_j).$$ Note that since $c^i$ will also hit the $P_j$, we have enough independent equations to solve for all indices. The hope is, of course, that we won't need to run through all equations but that already the first few contain all indices and are enough linearly independent. The choice of c is important in how quickly one will have enough information to solve the linear system.

You can generalize this to more general groups, but the idea stays the same.