rho

bigint pollard_rho(bigint C, bigint N) //返回一个平凡因子

{

    bigint I, X, Y, K, D;

    I = 1;

    X = Y = rand() % N;

    K = 2;

    do

    {

        I++;

        D = gcd(N + Y - X, N);//这里为了防止负数，先加上一个N

        if (D > 1 && D < N) return D;//如果D不是非平凡因子

        if (I == K) Y = X, K <<= 1;

        X = (product_mod(X, X, N) + N - C) % N;//随机一个增量来求X,Y，使得gcd(Y - X,N)不是非平凡因子(不是1，跟N)

    }

    while (Y != X);

    return N;

}