pollard.cpp

pollard算法

#include <iostream>
#include <ctime>
using namespace std;
#define LL __int64

// 返回a、b的最公约数(a, b)
LL euclid(LL a, LL b)
{
	if(b == 0)
		return a;
	else
		return euclid(b, a % b);
}

// a*b mod n
LL modMul(LL a, LL b, LL n)
{
	if(a == 0 || b == 0)
		return 0;
	return (((a & 1) * b) % n + (modMul(a >> 1, b, n) << 1) % n) % n;
}

// a^b mod n
LL modExp(LL a, LL b, LL n)
{
    LL ret = 1;
    while(b)
    {
		if(b & 1)
			ret = modMul(ret, a, n);
		a = modMul(a, a, n);
		b >>= 1;
	}
    return ret;
}

LL rand64()
{
	return (LL)rand() ^ ((LL)rand() << 15) ^ ((LL)rand() << 30) ^ ((LL)rand() << 45) ^ ((LL)(rand() & 7) << 60);
}

// 求整数的一个因子,O(n^1/4)
LL pollard(LL n)
{
	int i = 1, k = 2;
	LL x = rand64() % n;
	LL y = x;
	LL c = rand64() % n;
	if(c == 0 || c == 2)
		c = 1;
	while(true)
	{
		i++;
		x = modMul(x, x, n) - c;
		if(x < 0)
			x += n;
		x %= n;
		LL a = y - x;
		if(a < 0)
			a += n;
		LL d = euclid(a, n);
		if(d > 1 && d < n)
			return d;
		if(i == k)
		{
			y = x;
			k <<= 1;
		}
	}
}

int main()
{
	srand(time(0));
	return 0;
}