论文标题
数量场筛的渐近复杂性的精致分析
Refined Analysis of the Asymptotic Complexity of the Number Field Sieve
论文作者
论文摘要
数字字段筛（NFS）的经典启发式复杂性是涉及未知功能的优化问题的解决方案，通常在本文中称为$ O（1）$，称为$ O（1）$，随着条目$ n $的成长，它往往为零。本文的目的是找到NFS参数的最佳渐近选择，以最大程度地减少其启发式渐近计算成本。这相当于最大程度地减少NFS参数的函数，并由非线性约束结合在一起。我们提供了该优化问题最小化器的精确渐近估计，该估计值对NFS的渐近复杂性产生了精致的公式。该分析的主要结果之一是$ξ（n）$的收敛速度非常缓慢：我们证明它等于$ 4 {\ log} {\ log} {\ log} {\ log} {\ log} {\ n/（3 {\ log} {\ log} {\ log} {\ log}} {\ \ \，n）$。此外，对于复杂性的实际估计，$ξ（n）$具有不可预测的行为。确实，我们提供了$ξ$的渐近系列扩展，数值实验表明，该系列仅对$ n> \ exp（\ exp（25））$开始收敛，远远超出了NFS的实际范围。这引起了对基于渐近公式中设置$ξ= 0 $的NFS运行时间估计的相关性的怀疑。
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 $ξ(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 $ξ(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, $ξ(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $ξ$ 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 $ξ=0$ in the asymptotic formula.
