Motivation§

Under special cases, the discrete logarithm problem (DLP) becomes easier to solve, i.e. $\text{ord}_p(g)$ is the product of small primes, is a prime power, or is prime.

The Index Calculus Method§

The index calculus method depends on our ability to solve discrete log problems (DLP) that satisfies the statement:

$$ \begin{equation*} \exists B \forall \ell \in \mathbb{P}_{\leq B},\ g^x \equiv_p \ell. \tag*{(\P)} \end{equation*} $$

Index Calculus

First, we compute the values

$$ h \cdot g^{-k} \pmod{p}, k \in \mathbb{N}, $$

and stopping when we find a $k$ such that $h \cdot g^{-k} \pmod{p}$ is $B$-smooth, then for some $e_{\ell}$

$$ h \cdot g^{-k} \pmod{p} \equiv_p \prod_{\ell \in \mathbb{P}_{\leq B}} \ell^{e_\ell}. $$

Finally, we get that

$$ x = \log_g{h} \equiv_p k + \sum_{\ell \in \mathbb{P}_{\leq B}}\left[e_{\ell}\log_g(\ell)\right]. $$

Where algorithm ($\text{\P}$) is used to solve for all the $\log_g(\ell)$ terms.[^1]

Algorithm ($\text{\P}$)

Again, we want to solve DLPs of the form

$$ \forall\ell\in\mathbb{P}_{\leq B},\ g^x \equiv_p \ell. $$

One method is to compute for many random selections of exponents $i$ the values

$$ g_i \equiv_p g^i. $$

Keeping only the values of $g_i$ that are $B$-smooth. Then, we get a get a number of linear equations in the unknown variables $\log_g(\ell)$ from taking the logarithm of the equation

$$ g_i \equiv_p \prod_{\ell \in \mathbb{P}_{\leq B}} \ell^{u_{\ell}(i)} $$

which take the form

$$ i \equiv \log_g(g_i) \equiv \sum_{\ell \in \mathbb{P}_{\leq B}}u_{\ell}(i)\log_g(\ell) \pmod{p - 1}. $$

To find the values of $\log_g(\ell)$ we must solve the linear system; we may choose a sufficiently large number of exponents $i$ to ensure we have enough linear equations to determine the logarithm values.