Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms (Q6584318)

About ten years ago significant progress was made regarding the discrete logarithm problem in finite fields of small characteristic. This resulted in a series of practical record-breaking computations as well as quasi-polynomial asymptotic running times, first established heuristically and later provably. The tremendous speedup of the index calculus method was possible by an advantageous representation of the finite field. In fact, a field extension of \(\mathbb F_q\) could be defined by an element \(\vartheta\) satisfying \(\vartheta^q = \frac g h (\vartheta)\) for some low degree polynomials \(g, h\) (provided they exist which may be hard to prove).\N\NAnother representation that turns out to be helpful for provably efficient algorithms uses elliptic curves to define the field extension. Indeed, if \(P\) is an \(\mathbb F_q\)-rational point of order~\(k\) on an elliptic curve \(E\) with Frobenius map \(\pi\), and if \(F = (x_F, y_F)\) is any point on~\(E\) such that \(\pi(F) = F + P\), then \(\mathbb F_q[x_F, y_F]\) defines a field extension \(\mathbb F_{q^k}\). This has been used for notable recent work on provable quasi-polynomial time algorithms, while the practicality of this approach is now addressed by the paper at hand.\N\NIn order to use this representation for an efficient index calculus algorithm the elliptic curve is mapped into \(3\)-space by \(Q \mapsto (x_{Q - P}, x_Q, x_{Q + P})\), so that the coordinates \(U, V, W\) of the image of~\(F\) satisfy \(U^q = V\) and \(V^q = W\). This enables one to apply systematic equations \(\prod_{\alpha \in \mathbb P^1} (A - \alpha B) = A^q B - A B^q\) with \(A, B\) polynomials in \(U, V\). Using ideas from the Function Field Sieve the authors employ decompositions of divisors, which map to the target field~\(\mathbb F_{q^k}\) by evaluating at the point~\(F\), to set up the index calculus method.\N\NThe relation generation is explained in detail and it is shown how the algorithm can be improved by systematic factors to be practically competitive. It is also discussed how recent techniques like bilinear Gröbner basis descent or the zig-zag descent can be adapted to the situation at hand. Finally, the authors provide details of discrete logarithm computations in the finite field \(\mathbb F_{3^{1345}}\) along with Magma code for verification.