伪代码描述如下： // 通过求解 w^2 = 1 mod n, we get p=gcd(w-1, n)，有1/2概率求出非平凡因子p，一般2次即可 // k*phi = ed -1 = r * 2^s // a = rand(n) // w = a^r (mod n) // for ( j = 0 ; j < s ; j++) // if (w != 1) && (w != n-1 ) // if w^2 = 1 (mod n) // gcd(w-1,n) or gcd(w+1 ,n ) will have 1/2 chance to get p.q // 随机选择a,一般 2-3次, 即可求出p
///// method 1 ////////////
// find w^2 = 1 mod n, then gcd(w + 1, n) = p or gcd(w - 1, n) = p
printf("for p[5]， method 1 \n", tm);
tm = time(NULL);
ek973 = pow(e[5], 973);
ed = ek973 - 1; // k*phi = ed - 1
int s = 0;
while(ed % 2 == 0)
{
s++;
ed /= 2;
}
printf("s=%d, get: ed - 1 = r * 2^s \n", s);
find = 0;
for(int t = 2; t <= 7; t++) // try t=2, 3, 4, 5 ,...
{
w = pow(t, ed, n[5]);
int is = 0;
while(is < s)
{
is++;
w = pow(w, 2, n[5]);
Big p = gcd(w + 1, n[5]);
if(p > 1)
{
char buf[1024] = {0};
printf("try t =%d, s = %d ,get p\n", t, s);
buf << p;
printf("%s\n", buf);
find = 1;
break;
}
}
if(find == 1)
break;
}
tm = time(NULL) - tm;
printf("method 1, time cost: %d seconds\n\n", tm);
for p[5]， method 1 s=6, get: ed - 1 = r * 2^s try t =2, s = 6 ,get p CCAF369F85A28753B04A2281DB60A6D7E242F58429F0746D88CCFB0738DEE49B542655F6ACA3952CFA99A14FCB5C198D method 1, time cost: 15 seconds
// m^(e^973) = m mod n
// e^973 = 1 (mod phi)
// d = e^972 (mod phi)
// (m^e)^(e^972) = m mod n
// gcd(m^e - m, n) = p or gcd ( m^(e-1) - 1, n) = p
printf("for p[5]， method 2, Begin gcd \n", tm);
tm = time(NULL);
srand(tm);
Big m1, m2, mp, np, one = 1;
maxk = 973;
m1 = 2;
for(i = 1; i < maxk; i++)
{
m2 = pow(m1, e[5], n[5]);
mp = m2 - m1;
m1 = m2;
if((mp == n[5]) || (mp == 0))
{
printf("bug m2 == m1, i = %d !\n", i);
break;
}
np = gcd(mp, n[5]);
if(np > one)
{
char buf[1024] = {0};
printf("try i =%d, get p\n", i);
buf << np;
printf("%s\n", buf);
break;
}
}
tm = time(NULL) - tm;
printf("method 2, gcd time cost: %d seconds\n\n", tm);
for p[5]， method 2, Begin gcd try i =1, get p CCAF369F85A28753B04A2281DB60A6D7E242F58429F0746D88CCFB0738DEE49B542655F6ACA3952CFA99A14FCB5C198D method 2, gcd time cost: 0 seconds
