Paper 2020/829

Refined Analysis of the Asymptotic Complexity of the Number Field Sieve

Aude Le Gluher, Pierre-Jean Spaenlehauer, and Emmanuel Thomé

Abstract

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $\xi(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $\xi(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $\xi(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $\xi$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $\xi=0$ in the asymptotic formula.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Mathematical Cryptology
Keywords
ComplexityAsymptotic optimizationNumber Field Sieve
Contact author(s)
aude le-gluher @ loria fr
pierre-jean spaenlehauer @ inria fr
emmanuel thome @ inria fr
History
2021-06-22: last of 2 revisions
2020-07-07: received
See all versions
Short URL
https://ia.cr/2020/829
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/829,
      author = {Aude Le Gluher and Pierre-Jean Spaenlehauer and Emmanuel Thomé},
      title = {Refined Analysis of the Asymptotic Complexity of the Number Field Sieve},
      howpublished = {Cryptology ePrint Archive, Paper 2020/829},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/829}},
      url = {https://eprint.iacr.org/2020/829}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.