On the alpha value of polynomials in the tower number field sieve algorithm

Aurore Guillevic; Shashank Singh

Paper 2019/885

On the alpha value of polynomials in the tower number field sieve algorithm

Aurore Guillevic and Shashank Singh

Abstract

In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size. We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalisation of Murphy's E function, and finally the total amount of operations needed to compute a discrete logarithm with TNFS algorithm in the targeted fields. This is an improvement of the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to a wide size range of finite fields GF(p^n), for small composite n = 12, 16, 18, 24, that are target fields of pairing-friendly curves.

Note: Implementation available at https://gitlab.inria.fr/tnfs-alpha/alpha Published paper available at https://journals.flvc.org/mathcryptology/article/view/125142

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Mathematical Cryptology
Keywords: number field sieve discrete logarithm pairing-friendly curve
Contact author(s): aurore guillevic @ inria fr
shashank @ iiserb ac in
History: 2021-02-22: last of 2 revisions; 2019-08-01: received; See all versions
Short URL: https://ia.cr/2019/885
License: CC BY-NC

BibTeX

@misc{cryptoeprint:2019/885,
      author = {Aurore Guillevic and Shashank Singh},
      title = {On the alpha value of polynomials in the tower number field sieve algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/885},
      year = {2019},
      url = {https://eprint.iacr.org/2019/885}
}