使用三个数域的数域筛算法

大整数分解难题是RSA密码的数学安全基础.目前数域筛算法是分解365比特以上大整数的最有效方法,然而它的时间复杂度仍然是亚指数的.对于目前普遍使用的1024比特以上大整数,数域筛算法还不能分解,所以研究数域筛算法具有重要的意义.现有的一般数域筛算法普遍使用两个数域,对多个数域的研究极少.一般数域筛算法经过修改可以使用三个数域,即两个代数数域和一个有理数域.分析表明:修改后的数域筛算法与原来的一般数域筛算法在时间复杂度上处于同一量级.但修改后的数域筛算法有更多地方可以合并计算,所以计算速度更快了.通过两个实验也验证了这一结论.

The number field sieve with three number fields

The mathematical security of the RSA cryptosystem is based on the problem of factoring large integers.At present,the number field sieve is the most efficient algorithm known for factoring integers larger than 365 bits,while its time complexity is still sub-exponential.Integers larger than 1024 bits,which are widely used in RSA cryptosystem,cannot be factored by means of the number field sieve.So it is significant to study the number field sieve.Now,the general number field sieve often uses two number fields,while multiple number fields are seldom considered.The general number field sieve,through adaptation,can use three number fields,i.e.two algebraic number fields and one rational number field.Analysis shows that the time complexity of the modified number field sieve and the general number field sieve are at the same level.However,the modified number field sieve can combine more computation,so it can save more time in practice.Finally,the result is verified by two experiments.