Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
Authors:
Preprint
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.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment2020
- Rigorous analysis of a randomised number field sieveJournal of Number Theory, 2018
- Some mathematical remarks on the polynomial selection in NFSMathematics of Computation, 2016
- Selecting Cryptographic Key SizesJournal of Cryptology, 2001
- Factoring integers with the number field sieve1993
- On the number of positive integers ≦ x and free of prime factors > yJournal of Number Theory, 1986
- Solving sparse linear equations over finite fieldsIEEE Transactions on Information Theory, 1986
- On a problem of Oppenheim concerning “factorisatio numerorum”Journal of Number Theory, 1983
- On The Number of Positive Integers ≤ x and Free of Prime Factors > yIndagationes Mathematicae, 1951