计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2015年
4期
261-265,308
,共6页
MPQS%筛法%多项式系数%循环拷贝筛%神威
MPQS%篩法%多項式繫數%循環拷貝篩%神威
MPQS%사법%다항식계수%순배고패사%신위
MPQS%Sieving%Polynomial coefficient%Circulating copy sieve%Shenwei
数域筛法是目前最有效的大整数分解算法，其中候选关系的光滑性判断需要对大量规模不大的余因子做分解，MPQS作为110-digits以下最快的分解算法得到广泛的应用。但现有的MPQS软件包针对96 bit以下的整数优化不足，未充分挖掘整数规模对MPQS性能的影响。针对小规模整数的MPQS算法提出新多项式系数选取和循环拷贝筛两种优化方法，新的系数方案配合参数选取和中间结果规模控制可以尽量避免使用多精度函数；循环拷贝筛法根据筛法定理与周期函数的周期性，利用循环拷贝替代小素因子的筛法，解决了小素因子筛法成本过高和部分因子基筛法筛选效果差的问题。在神威蓝光国产CPU平台上进行的实验测试表明，两种优化方法可使MPQS性能提高30％以上。
數域篩法是目前最有效的大整數分解算法，其中候選關繫的光滑性判斷需要對大量規模不大的餘因子做分解，MPQS作為110-digits以下最快的分解算法得到廣汎的應用。但現有的MPQS軟件包針對96 bit以下的整數優化不足，未充分挖掘整數規模對MPQS性能的影響。針對小規模整數的MPQS算法提齣新多項式繫數選取和循環拷貝篩兩種優化方法，新的繫數方案配閤參數選取和中間結果規模控製可以儘量避免使用多精度函數；循環拷貝篩法根據篩法定理與週期函數的週期性，利用循環拷貝替代小素因子的篩法，解決瞭小素因子篩法成本過高和部分因子基篩法篩選效果差的問題。在神威藍光國產CPU平檯上進行的實驗測試錶明，兩種優化方法可使MPQS性能提高30％以上。
수역사법시목전최유효적대정수분해산법，기중후선관계적광활성판단수요대대량규모불대적여인자주분해，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.
