Discrete Logarithm in $\mathbb{F}_p$: Index Calculus Method

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]

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.