TY - JOUR
AU - Le Gluher, Aude
AU - Spaenlehauer, Pierre-Jean
AU - ThomÃ©, Emmanuel
PY - 2021/06/22
Y2 - 2021/10/19
TI - Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
JF - Mathematical Cryptology
JA - mathcryptology
VL - 1
IS - 1
SE - Articles
DO -
UR - https://journals.flvc.org/mathcryptology/article/view/125488
SP - 71-88
AB - <pre>The classical heuristic complexity of the Number Field Sieve (NFS) involves an unknown function, usually noted o(1) and called xi(N) throughout this paper, <br>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 <br>its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint.<br>We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. <br>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 (4logloglog N)/(3loglog N). <br>Moreover, xi(N) has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of xi <br>and numerical experiments indicate that this series starts converging only for N>exp(exp(25)), far beyond the practical range of NFS. This raises<br>doubts on the relevance of NFS running time estimates that are based on setting xi=0 in the asymptotic formula.</pre>
ER -