TY - JOUR AU - Le Gluher, Aude AU - Spaenlehauer, Pierre-Jean AU - Thomé, Emmanuel PY - 2021/06/22 Y2 - 2024/03/28 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&gt;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 -