Factor base discrete logarithms in Kummer extensions (Q1654504)

The discrete logarithm problem (DLP) is considered, for a prime power \(q\), in a finite field of size \(q^{2 (q-1)}\) given as a Kummer extension \(\mathbb F_{q^2}[x] / (x^{q-1} \!-\! A)\). In particular, the linear algebra phase of a DLP algorithm is investigated, during which the discrete logarithms of all factor base elements \(x \!+\! h\), where \(h \in \mathbb F_{q^2}^*\), are computed by solving a linear system. Three variants of such a system, each represented by a square matrix, are considered. The relations producing these matrices are obtained by applying Möbius transforms to the systematic equation \[ \prod_{\alpha \in \mathbb F_q}(x - \alpha) = x^q - x, \] which results in the identity \[ (cx + d) \prod_{\alpha \in \mathbb F_q} \big( (a x + b) - \alpha (cx + d) \big) = (a^q x^q + b^q) (c x + d) - (a x + b) (c^q x^q + d^q), \] and substituting \(x^q = A x\), for \(a, b, c, d \in \mathbb F_{q^2}\). Avoiding duplicate relations suggests to restrict the parameters, say to \(c = 0\), \(d = 1\) and \(b = g\) a specified generator. The first square matrix of dimension \(q^2 - 1\) is given by the \(q^2 - 1\) relations from \(a \in \mathbb F_{q^2}^*\). Then, incorporating \(q + 1\) extra relations for \(b = 0\) and representatives \(a\) of \(\mathbb F_{q^2}^* / \mathbb F_q^*\) yields a second matrix of dimension \(q^2 - q - 2\). Moreover, applying the Galois group generated by the \(q^2\)-Frobenius results in a third, much smaller matrix of dimension \(q + 1\). The paper employs a thorough eigenvalue analysis of the matrices (over the complex numbers) to obtain results or conjectures on the unique solvability of the corresponding linear systems. It is argued that the first system has a solution space of rank at least \((q - 1)/ 2\) and is therefore insufficient for extracting the factor base logarithms. Also, for the second matrix it is shown by example that the solution space may be still too large. Regarding the third matrix, it is conjectured that a solution modulo the large prime factors of the target group order is uniquely determined. Evidence is based on numerical experiments and on a heuristic argument involving eigenvalues proving that a certain lattice determinant is relatively small. Furthermore, provided the conjecture holds true, the authors show that discrete logarithms of factor base elements can be computed in \(O(q^{\vartheta})\) bit operations, where \(\vartheta < 3.38\). In an appendix, it is also shown how to obtain the logarithms of about \(q^3 / 2\) quadratic polynomials.