Notes Cryptography Index Calculus Method

Index Calculus Method

17 Dec 2021

§ Motivation

Under special cases, the discrete logarithm problem (DLP) becomes easier to solve, i.e. ordp(g)\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:

∃B ∀(ℓ∈P≤B), gx≡pℓ.\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⋅g−k(modp),k∈N,h \cdot g^{-k} \pmod{p}, k \in \mathbb{N},

and stopping when we find a kk such that h⋅g−k(modp)h \cdot g^{-k} \pmod{p} is BB-smooth, then for some eℓe_{\ell}

h⋅g−k(modp)≡p∏ℓ∈P≤Bℓeℓ.h \cdot g^{-k} \pmod{p} \equiv_p \prod_{\ell \in \mathbb{P}_{\leq B}} \ell^{e_\ell}.

Finally, we get that

x=log⁡gh≡pk+∑ℓ∈P≤B[eℓlog⁡g(ℓ)].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(ℓ)\log_g(\ell) terms.[1]

Algorithm (\text{\P})

Again, we want to solve DLPs of the form

∀ℓ∈P≤B, gx≡pℓ.\forall\ell\in\mathbb{P}_{\leq B},\ g^x \equiv_p \ell.

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

gi≡pgi.g_i \equiv_p g^i.

Keeping only the values of gig_i that are BB-smooth. Then, we get a get a number of linear equations in the unknown variables log⁡g(ℓ)\log_g(\ell) from taking the logarithm of the equation

gi≡p∏ℓ∈P≤Bℓuℓ(i)g_i \equiv_p \prod_{\ell \in \mathbb{P}_{\leq B}} \ell^{u_{\ell}(i)}

which take the form

i≡log⁡g(gi)≡∑ℓ∈P≤Buℓ(i)log⁡g(ℓ)(modp−1).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(ℓ)\log_g(\ell) we must solve the linear system; we may choose a sufficiently large number of exponents ii to ensure we have enough linear equations to determine the logarithm values.

  1. In most texts, algorithm (\text{\P}) is just a subroutine of the Index Calculus Method; however, I felt it was clearer to separate the two algorithms due to the amount of notation. ↩︎