选取随机数\(ａ\) 随机数\(ｂ\)，检查\(gcd(a - b, n)\)是否大于１，若大于１则\(a - b\)是\(ｎ\)的一个因数

实现１：floyd判环

利用多项式\(f(x)\)迭代出\({x_0, x_1, \dots, x_k}\)

设定\(x = y = x_0\)的初始值，选用多项式进行迭代，每次：\(x = f(x)\), \(y = f(f(y))\)，即：\(x = x_k, y = x_{2k}\)当\(x == y\)时出现循环

设\(x = y = 2\)，\(f(n) = n^2 + a\)

typedef long long ll;ll mul_mod(ll a, ll b, ll m){    ll ans = 0, exp = a;    while(a >= m) a -= m;    while(b){        if(b & 1){            ans += exp;            while(ans >= m) ans -= m;        }        exp += exp;        while(exp >= m) exp -= m;        b >>= 1;    }    return ans;}ll pollard_rho(ll n, int a){    ll x = 2, y = 2, d = 1;    while(d == 1){        x = mul_mod(x, x, n) + a;        y = mul_mod(y, y, n) + a;        y = mul_mod(y, y, n) + a;        d = __gcd((x >= y ? x - y : y - x), n);    }    if(d == n) return pollard_rho(n, a + 1);    return d;}

实现２: brent判环（更高效）

不同于floyd每次计算\(x_k, x_{2k}\)进行判断,brent每次只计算\(x_k\),当ｋ是2的方幂时,\(y = x_k\),每次计算\(d = gcd(x_k - y, n)\)

typedef long long ll;ll mul_mod(ll a, ll b, ll m){    ll ans = 0, exp = a;    while(a >= m) a -= m;    while(b){        if(b & 1){            ans += exp;            while(ans >= m) ans -= m;        }        exp += exp;        while(exp >= m) exp -= m;        b >>= 1;    }    return ans;}ll pollard_rho(ll n, int a){    ll x = 2, y = 2, d = 1, k = 0, i = 1;    while(d == 1){        ++k;        x = mul_mod(x, x, n) + a;        d = __gcd(x >= y ? x - y : y - x, n);        if(k == i){            y = x;            i <<= 1;        }    }    if(d == n) return pollard_rho(n, a + 1);    return d;}