[Paper Review] A new index calculus algorithm with complexity $L(1/4 + o(1))$ in small characteristic.

Scientific breakthroughs are rare events. And I can not directly judge if this is indeed a breakthrough or not, but there are people out there, which do so.

It is the paper from Antoine Joux. It introduces a new techniques for the index calculus algorithm and improves the running time to $L(1/4+o(1))$. And it is also the follow up paper by Razvan Barbulescu, Pierrick Gaudry, Antoine Joux and Emmanuel Thomé. The later improves (heuristically) the running time even to quasi-polynomial complexity, i.e., $n^{\mathcal{O}(\log n)}$.

# The Idea of the Index Calculus Algorithm #

The idea of the index calculus algorithm is, in order to find the discrete logarithm of the group element $X$ to the base $G$, to

1. build a factor-base of size $s$. That is, a set of small integers or low degree polynomials. Then random group elements $X_r$ are generated via $G^r = X_r$ (hence their logarithm is known). Then these $X_r$ elements are tried to be factored completely within the factor base only. (Hence the $X_r$ have a smooth factorization).
2. If $s$ independent elements are found, that are successfully factored within the factor base, $s$ equations can be build:
   \begin{align*}
   G^{r_1} & = b_1^{e_{1,1}}b_2^{e_{1,2}}...b_s^{e_{1,s}}\\
   G^{r_2} & = b_1^{e_{2,1}}b_2^{e_{2,2}}...b_s^{e_{2,s}}\\
   ... &\\
   G^{r_s} & = b_1^{e_{s,1}}b_2^{e_{s,2}}...b_s^{e_{s,s}}
   \end{align*}
   Writing this in terms of logarithms to the base $G$, we get $s$ equations and $s$ unknown
   \begin{align*}
   r_1 & = e_{1,1}\log_G b_1 + e_{1,2}\log_G b_2 + ... + e_{1,s}\log_G \\
   r_2 & = e_{2,1}\log_G b_1 + e_{2,2}\log_G b_2 + ... + e_{2,s}\log_G \\
   ... &\\
   r_s & = e_{s,1}\log_G b_1 + e_{s,2}\log_G b_2 + ... + e_{s,s}\log_G \\
   \end{align*}
   which can be solved for the $s$ unknowns $\log_G b_i$. So, one gets the discrete logarithm for each element from the factor base.
3. Pick a random integer $h$ and compute $g^hX$ until this could be factored completely within the factor-base $$g^hX = b_1^{f_1}b_2^{f_2}...b_s^{f_2}$$ the algorithm succeeded and returns the logarithm of $X$ by
   \begin{align*}
   \log_G X = f_1\log_G b_1 + f_2\log_G b_2 + ... + f_s\log_G b_s - h
   \end{align*}

Sidenote: Since points on elliptic curves can not be factored into prime elements, step 1 of the index calculus algorithm fails and hence the algorithm can not be applied to general elliptic curves.

# Improvements #

I will not cover all details here, but i want to describe what are the main reasons for the improvement.

The first improvement of Joux et al. is about phase 1) of the index calculus algorithm. He found a more efficient way to generate elements $G^r = X_r$, such that $X_r$ can be factored into small elements, i.e., elements from the factor-base.
Instead of choosing at first a factor base and then trying to find elements $X_r = G^r$, that could be factored within that factor base, Joux idea is to start with a polynomial $f$, that is already known or constructed that way, that it can be factored in many small irreducible polynomials.
He then applies Homographies to $f$, that is a change of the polynomial that preserves the property of having many irreducible factors. In particular he uses $$f(X) \rightarrow F_{abcd}(X) = (cX+d)^{\text{deg}f}f\left(\frac{aX+b}{cX+d}\right)$$ The additional term $(cX+d)^{\text{deg}f}$ is responsible to make $F_{abcd}(X)$ indeed a polynomial, i.e., not to contain fraction terms.

The polynomial $f(X)$ is defined in $\mathbb{F}_q$, whereof the elements $a,b,c,d$ are taken from $\mathbb{F}_{q^2}$. As a natural choice for $f$, i.e., a polynomial that has many factors, he chooses $$f(X) = X^q - X$$ since every element from $F_q$ is a root of that polynomial. So we can write $$f(X) = \prod_{\alpha \in \mathbb{F}_q}(X-\alpha) = X^q - X$$ Now the homographie $X \rightarrow \frac{aX+b}{cX+d}, ad-bc \neq 0$ is applied, as well as multiplied with $(cX+d)^{q+1})$:
\begin{align*}
(1)\;\;(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) = (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right)
\end{align*}
The LHS of (1) can be simplified to
\begin{align*}
(cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b}{cX+d}-\alpha\right) & = (cX+d)^{q+1}\prod_{\alpha \in \mathbb{F}_q}\left(\frac{aX+b - \alpha cX - \alpha d}{cX+d}\right) \\
& = (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d))
\end{align*}
The RHS of (1) can be simplified to (using the fact that $(x+y)^q = x^q + y^q$)
\begin{align*}
& (cX+d)^{q+1}\left(\left(\frac{aX+b}{cX+d}\right)^q - \frac{aX+b}{cX+d}\right) = (cX+d)(aX+b)^q - (cX+d)^q(aX+b) \\
& = ca^qX^{q+1}+cb^qX  + da^qX^q + db^q - c^qaX^{q+1}-c^qbX^q - d^qaX-d^qb\\
& = (ca^q-c^qa)X^{q+1} + (da^q-d^qa)X^q + (cb^q-c^qb)X  + (db^q -d^qb)\\
\end{align*}
Next, two polynomials $h_0(X)$ and $h_1(X)$ are chosen, that have at most degree 2. Furthermore, they have the property $$X^q = \frac{h_0(X)}{h_1(X)}$$
as well as $$h_1(X)X^q - h_0(X)$$ as an irreducible factor $I(X)$ of degree $n$ (therewith it creates $\mathbb{F}_{q^n}$). Then the RHS could further be rewritten as
\begin{align*}
& = (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)}  + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*} So in total we have the equation
\begin{align*}
& (cX+d)\prod_{\alpha \in \mathbb{F}_q}((a- \alpha c)X + (b - \alpha d)) \\
& = \\
& (ca^q-c^qa)X\frac{h_0(X)}{h_1(X)} + (da^q-d^qa)\frac{h_0(X)}{h_1(X)}\\
&+ (cb^q-c^qb)X\frac{h_1(X)}{h_1(X)}  + (db^q -d^qb)\frac{h_1(X)}{h_1(X)}\pmod{I(X)}
\end{align*}
That is a relation between a product of linear polynomials on the left side and a fraction with low-degree numerator and constant denominator (consider $h_1(X)$ as an element of the factor base).

It can be proven that there exists $q^3+q$ different equations for random chosen values of $(a,b,c,d)$. Since $\mathcal{O}(q^2)$ quadruples (a,b,c,d) are sufficient, there are enough possibilities to choose from in order to get sufficient systems of relations.

However, Joux argues that linear polynomials are not sufficient to solve all discrete logarithms. He repeats his idea with another Homographie to get quadratic polynomials by $$X \rightarrow \frac{aX^2+bC+c}{dX^2+eX+f}$$.

So by simply picking random values for $(a,b,c,d)$ one gets enough relations and indeed one could compute the discrete logarithms for all the elements from the factor base in polynomial time (actually due to the small base field).

His second improvement is  about phase 3) of the index calculus algorithm. In the so called Descent Phase (or individual logarithm phase). And this is the point where, as far as i understood the algorithms, the original paper and the follow up paper with its quasi-polynomial runtime diverge.

The goal of the Descent Phase is to express a multiplicative of the residue in question, say $g^iZ$ for some $i$, as a linear combination of the factors from the factor base. The strategy is to first find a suitable representation of $Z$ with polynomial of low-degree. Then one tries to find recursively a representation of these polynomials of even lower degree until one ends with polynomials from the factor base.

So if $p(Z)$ is the polynomial that expresses $Z$, then we have to find a polynomial $t$ that expresses $g^iZ$. So the polynomial $t$ must 

1. be of lower degree
2. contain $p(Z)$ as a factor

In the classical descent phase (which is also used by Joux), one could find such polynomials if $q$ is again prime power of the form $q = p^l$ and $l \geq 2$. This gets impractical for large $p$ (which is the reason that this approach is only valid for small characteristics). And the classical descent phase can not reduce the degree of the involved polynomials sufficiently. The new ideas of the descent phase (which complements the classical one) are to find polynomials $k_1$ and $k_2$ such that $p(Z)$ divides $k_1^q(X)k_2(X) - k_1(X)k_2^q(X)\pmod{I(X)}$. Based on the arguments from the first improvement steps, this could be factored in small polynomials and contains $p(Z)$ as a factor. To find such polynomials $k_1$ and $k_2$ and has to solve a system of bilinear-equations. At the end, Joux made the statement:

"...given an oracle to solve bilinear systems, we could use a much faster descent from degree deg ? to ? ... would then give a quasi-polynomial complexity... Moreoever, this would get rid of the use of classical descent, together with the constraint of having $q=p^l$, with $l\geq 2$."

And this is what the follow up paper does in order to achieve quasi-polynomial runtime. But I guess i will cover the follow up paper in another post.