Factor base discrete logarithms in Kummer extensions
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.
- On the discrete logarithm problem in finite fields of fixed characteristic
- Computation of discrete logarithms in an arbitrary finite field
- The index calculus method using non-smooth polynomials
- Study of the discrete logarithm problem in \(\mathbb{F}_{p^ 3}\)
- A subexponential-time algorithm for computing discrete logarithms over<tex>GF(p^2)</tex>
- A brief history of pairings
- A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
- A new index calculus algorithm with complexity L(1/4+o(1)) in small characteristic
- A taxonomy of pairing-friendly elliptic curves
- An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
- Constructing high order elements through subspace polynomials
- Diameters and Eigenvalues
- Elements of high order on finite fields from elliptic curves
- Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields
- Finding primitive elements in finite fields of small characteristic
- Generators and irreducible polynomials over finite fields
- scientific article; zbMATH DE number 1594292 (Why is no real title available?)
- scientific article; zbMATH DE number 1210375 (Why is no real title available?)
- scientific article; zbMATH DE number 1254302 (Why is no real title available?)
- scientific article; zbMATH DE number 2081061 (Why is no real title available?)
- scientific article; zbMATH DE number 799769 (Why is no real title available?)
- scientific article; zbMATH DE number 3214560 (Why is no real title available?)
- Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
- Matrix multiplication via arithmetic progressions
- On the discrete logarithm problem in finite fields of fixed characteristic
- On the function field sieve and the impact of higher splitting probabilities. Application to discrete logarithms in \(\mathbb{F}_{2^{1971}}\) and \(\mathbb{F}_{2^{3164}}\)
- On the multiplicative order of elements in Wiedemann's towers of finite fields
- Primitive Polynomials Over Finite Fields
- Searching for Primitive Roots in Finite Fields
- Traps to the BGJT-algorithm for discrete logarithms
- Traps to the BGJT-algorithm for discrete logarithms
- A new index calculus algorithm with complexity L(1/4+o(1)) in small characteristic
- On the Bounded Sum-of-Digits Discrete Logarithm Problem in Finite Fields
- A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
- Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
This page was built for publication: Factor base discrete logarithms in Kummer extensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1654504)
