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

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