## 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.