|
楼主 |
发表于 2009-9-14 22:23:03
|
显示全部楼层
我也不知道具体该给出哪些资料,我大致了解的有大数分解目前主要应用在公钥密码方面,
还有这个项目现在使用的方法是SNFS(Special Number Field Sieve)分解比较特殊的一类合数,
而RSA中的那种一般形式的合数需要使用GNFS(General Number Field Sieve),二者的区别主要在多项式的选择不同。
分解的基本思想是寻找整数x和y使得x^2=y^2 (mod n),这里的n是需要分解的合数。
x和y的寻找过程又分一些小的步骤,这里会用到一些数论方面的知识,
开始需选择一个多项式f(x)=x^d + c_{d-1} * x^(d-1) + ... + c_{0}
这里的c_{d-1}表示的是x^(d-1)这一项的系数,c_{0}是常数项。
α是f(x)=0的一个复数根,
定义φ(a_{0}+a_{1} * α + ... + a_{d-1} * α^(d-1)) = a_{0}+a_{1} * m + ... + a_{d-1} * m^(d-1) (mod n)。
可以知道φ是从Z[α]到Z_{n}的同态。
还有一个参数m,使得f(m)=0 (mod n).
由于使用的是SNFS,所以这几个参数实现可以比较简单的求得。
再设
F(x,y)=x^d + c_{d-1} * x^(d-1) * y + ... + c_{0} * y^d
G(x,y)=x - my
寻找向量对(a,b)使得F(a,b)*G(a,b)的所有因子都比较小,
最后寻找到足够多的向量对之后就可以寻找到其中的一些构成集合S,使得
∏ (a - b * m) = v^2 (mod n)
(a,b)∈S
以及
f'(α) * ∏ (a - b * α) = γ^2
(a,b)∈S
计算u=φ(γ);
gcd(u-f'(m)*v, n)即可得到n的一个因子。
寻找向量对(a,b)的阶段称作sieve,这个阶段便是SNF@Home所做的。
每个包完成大概需要1个小时,上传的数据在1M左右。
接下来的寻找集合S的过程称作matrix,Square root这个阶段主要就是寻找u和v,
这个过程现在是由Greg完成,
比如刚分解的2,2214L sieve阶段花了大约5天,余下部分花了2天。
项目负责人是Greg Childers,他貌似是一个大学的教授。 |
评分
-
查看全部评分
|