Factor base discrete logarithms in Kummer extensions
type: Item
instance of: scholarly article
title: Factor base discrete logarithms in Kummer extensions
zbMATH Open document ID: 1435.11143
author: Dianyan Xiao
author: Jincheng Zhuang
author: Qi Cheng
published in: Finite Fields and their Applications
publication date: 2018-08-08T00:00:00Z
review text: 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 …
reviewed by: Jens Zumbrägel
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 6914851
zbMATH Keywords: discrete logarithms
zbMATH Keywords: finite fields
zbMATH Keywords: Kummer extension
zbMATH Keywords: character sum
MaRDI profile type: Publication
full work available at URL: j.ffa.2018.06.008
OpenAlex ID: W2810640119
cites work: Q4474168
cites work: A taxonomy of pairing-friendly elliptic curves
cites work: A Brief History of Pairings
cites work: On the Function Field Sieve and the Impact of Higher Splitting Probabilities
cites work: Faster Index Calculus for the Medium Prime Case Application to 1175-bit and 1425-bit Finite Fields
cites work: A New Index Calculus Algorithm with Complexity $$L(1/4+o(1))$$ in Small Characteristic
cites work: A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic
cites work: Q4847920
cites work: Q4213392
cites work: Finding primitive elements in finite fields of small characteristic
cites work: Q2712109
cites work: Q5743490
cites work: ELEMENTS OF HIGH ORDER ON FINITE FIELDS FROM ELLIPTIC CURVES
cites work: Searching for Primitive Roots in Finite Fields
cites work: Generators and irreducible polynomials over finite fields
cites work: On the multiplicative order of elements in Wiedemann's towers of finite fields
cites work: On the discrete logarithm problem in finite fields of fixed characteristic
cites work: Primitive Polynomials Over Finite Fields
cites work: Traps to the BGJT-algorithm for discrete logarithms
cites work: Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms
cites work: An improved algorithm for computing logarithms over&lt;tex&gt;GF(p)&lt;/tex&gt;and its cryptographic significance (Corresp.)
cites work: Diameters and Eigenvalues
cites work: Q4227352
cites work: Matrix multiplication via arithmetic progressions
cites work: Q5341769
DOI: 10.1016/J.FFA.2018.06.008
description: scientific article; zbMATH DE number 6914851