二次筛选法中大型稀疏矩阵规模缩减算法

Algorithm of large sparse matrices reduction in quadratic sieve

利用二次筛选法分解RSA的模数时,矩阵规模对算法性能有着重要的影响,缩减矩阵的规模可以有效地缩短算法的运行时间。根据二次筛选法的原理,给出了3种缩减矩阵规模的方法,结合二次筛选中的稀疏矩阵的存储结构,提出了相应的3种缩减算法。最后实现了这3种缩减算法,并在二次筛选法分解70位十进制大数程序中进行了成功的应用,给出了实验的结果。

Matrices are related to efficiency of quadratic sieve to factor RSA modulus, runtime of the algorithm can be decreased by reduction of the large sparse matrices. Three methods of reduction of the large sparse matrices are given by principles of quadratic sieve. With a sparse matrices data structure storing sparse matrices in quadratic sieve, three algorithms of matrices reduction are presented. The algorithms are implemented, It is applied in factoring 70-digits large number using quadratic sieve, and the experimental result is obtained.