数域筛算法中的多项式优化问题

摘要

一般数域筛算法(GNFS)是目前大整数分解最高效的算法,多项式选择是数域筛算法中的重要步骤.多项式的大小是影响数域筛算法效率的关键因素之一.本文将多项式的大小优化问题归结为高维空间中格(Lattice)上的优化问题,并将该问题降维至二维平面上的优化问题.最后,本文提出了对多项式的大小进行优化的新算法,并对该算法进行了实验.实验结果表明:与原有算法相比,新算法对五次和六次多项式的优化质量都有明显的提高.