谁懂分布式计算 多台计算机共同计算大素数

DSA素数生成
密码学家Lentra和Haber指出DSA的一些模是容易攻破的。如果一些网络用户使用这样的模，那么他的签名就会被伪造。但是这些模很容易被检测，而且数目很少，以至于选择这样的模的概率很小。
NIST学会推荐生成两个素数p、q的一个特别的方法，其中q能整除p-1，p 长度为L比特，L范围是512比特到1024比特之间，并且是64的整数倍。素数q长度是160比特。令L-1 =160n + b，其中L是p的长度，n和b是两个数，b<160。DSA素数生成步骤如下：
1）  选择至少有160比特的任意序列，称之为S。令g是S的比特长度；
2）  计算U = SHA(S)⊕SHA((S+1) mod 2^g，其中，SHA是安全哈希算法；
3）  设置U的最高有效位和最低有效位为1，形成q；
4）  检查q是否是素数；
5）  如果q不是素数，则转会步骤1；
6）  令C = 0且N = 2；
7）  对应k = 0，1，2，…，n，令Vk = SHA( ( S + N + k ) mod 2^g )；
8）  令W是一个整数
W = V0 + (2^160)*V1 + …+(2^160(n-1))*Vn-1 + (2^160n)*Vn( mod 2^g)
并且令X = W + 2L+1；
9） 令p = X – ((X mod 2q) – 1)，要求p mod 2q = 1；
10） 如果p<2^(L-1)则转到步骤13；
11）检查p是否是素数；
12）如果p是素数，则转到步骤15；
13）令C = C +1且N = N +n +1；
14）如果C = 4096，则转到步骤1，否则转到步骤7；
15）存储S和C的值，用于生成p和q。
上式中，变量S称作“种子”，C称作“计数器”，N称作“偏移量”。
(注：2^g表示2的g次方，其它^以此类推)