数域筛法分解r^e±s型大整数时多项式的选取  

POLYNOMIAL SELECTIONS IN FACTORING r^e±s WITH NFS

作　　者：张鹏[1] 李超[1] 

机构地区：[1]国防科技大学数学与系统科学系,湖南长沙410073

出　　处：《计算机应用与软件》2009年第4期28-30,共3页Computer Applications and Software

基　　金：国家自然科学基金项目(60573028)。

摘　　要：数域筛法是目前最有效的大整数分解算法,多项式的选取是该算法中的一个重要环节,它关系到整个算法的运算速度和所耗时间。对数域筛法分解re±s型大整数时的多项式选取问题进行了研究,这里r、s分别为绝对值较小的整数。通过理论分析和数值计算,给出了选取多项式的一个新的原则—多项式次数在不同情况下的取值范围。Number field sieve （NFS） is the most effective algorithm to factor larger integers so far. Polynomial selection plays an important rule in the algorithm, which affects the speed and the running time of the whole algorithm. In this paper, we studied the polynomial selections in factoring larger integers of the form r^e ± s for smaller absolute value integer r and s, and presented a new principle about the degree range of the polynomial in different situations by theoretical analysis and numerical calculation.

关 键 词：数域筛法 特殊大整数 多项式的选取次数 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] O156[自动化与计算机技术—计算机科学与技术]