Index calculus is based on two simple ideas:
- Every integer can be written as a product of primes.
- 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.
