Paper 2016/684
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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Finite fielddiscrete logarithmnumber field sievefunction field sieveQPA
- Contact author(s)
- aurore guillevic @ inria fr
- History
- 2018-09-17: last of 3 revisions
- 2016-07-12: received
- See all versions
- Short URL
- https://ia.cr/2016/684
- License
-
CC BY