针对小规模整数的MPQS算法  

MPQS ALGORITHM TARGETED AT SMALL-SCALE INTEGERS

作　　者：袁欣辉 漆锋滨[1] 

机构地区：[1]江南计算技术研究所,江苏无锡214083

出　　处：《计算机应用与软件》2015年第4期261-265,308,共6页Computer Applications and Software

基　　金：国家高技术研究发展计划项目(2012A A010903)

摘　　要：数域筛法是目前最有效的大整数分解算法,其中候选关系的光滑性判断需要对大量规模不大的余因子做分解,MPQS作为110-digits以下最快的分解算法得到广泛的应用。但现有的MPQS软件包针对96 bit以下的整数优化不足,未充分挖掘整数规模对MPQS性能的影响。针对小规模整数的MPQS算法提出新多项式系数选取和循环拷贝筛两种优化方法,新的系数方案配合参数选取和中间结果规模控制可以尽量避免使用多精度函数;循环拷贝筛法根据筛法定理与周期函数的周期性,利用循环拷贝替代小素因子的筛法,解决了小素因子筛法成本过高和部分因子基筛法筛选效果差的问题。在神威蓝光国产CPU平台上进行的实验测试表明,两种优化方法可使MPQS性能提高30%以上。NFS （number field sieve）is the most efficient algorithm in large number factorisation,in which the factorisation needs to be exerted on a lot of small-scale cofactors to determine whether the candidate relations are smooth,and MPQS is widely used as it is the fastest factorisation method for factor numbers less than 1 1 0-digits.However,existing MPQS software packages are not fully optimised for integers with number less than 96 bits,and don’t fully exploit the influence of integer number scale on MPQS performance as well.We propose a new polynomial coefficients selection method and circulating copy sieve method for small-scale integer MPQS algorithm.The new coefficients selection scheme,working in concert with parameter selection and middle-results scale control,can avoid the multiple-precision functions in use as much as possible;The circulating copy sieve,according to sieving theorem and the periodicity of periodic function,replaces small prime factors’sieve with circulating copy operation and solves the problems of high cost in small primes sieve and the poor screening effect in partial factor base sieve.Experimental test on Shenwei domestic CPU platform show that these two methods can improve MPQS performance by 30% and higher.

关 键 词：MPQS 筛法 多项式系数 循环拷贝筛 神威 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]