**Faster individual discrete logarithms with the QPA and NFS variants**

*Aurore Guillevic*

**Abstract: **Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms known are the Number Field Sieve and its variants (special, high-degree, tower) in large and medium characteristic fields (e.g. $\mathrm{GF}(p^2)$, $\mathrm{GF}(p^{12})$); the Function Field Sieve and the Quasi Polynomial-time Algorithm in small characteristic finite fields (e.g. $\mathrm{GF}(3^{6 \cdot 509})$). The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains of same difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any non-prime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step with QPA. Moreover it reduces the width and the height of the subsequent descent tree.

**Category / Keywords: **public-key cryptography / Finite field, discrete logarithm, number field sieve, function field sieve, QPA

**Date: **received 7 Jul 2016, last revised 6 Aug 2017

**Contact author: **aurore guillevic at inria fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20170806:184336 (All versions of this report)

**Short URL: **ia.cr/2016/684

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]