Pollard-Rho 总结

将一个大数\(N\)分解质因子。

试除法，暴力枚举\(1～\sqrt{N}\)的数。时间复杂度：\(O(\sqrt{N})\)。

通常，这个复杂度够了，但有时，\(N\leq10^{18}\)。

这就需要Pollard-Rho了。

首先，考虑一种简单情况。设\(N=p*q（p<q）\)。

有一种糟糕的做法：随机法。随机一个\(1～\sqrt{N}\)的数x，判断能否整除。期望需要\(\sqrt{N}\)次。

我们发现，随机的数x并不一定要等于p，只要是p的倍数即可，即\(gcd(N,x)=p\)。

然而，这样每次的概率仍只有\(\frac{1}{\sqrt{N}}\)。

我们来考虑这样一种情况：在[1,1000]里面取一个数，取到我们想要的数(比如说,42)，成功的概率是多少呢？显然是1/1000。

一个不行就取两个吧：随便在[1,1000]里面取两个数我们想办法提高准确率，就取两个数的差值绝对值。

也就是说,在[1,1000]里面任意选取两个数\(i,j\)，问\(∣i−j∣=42\)的概率是多大？答案会扩大到1/500。

我们可以取\(\sqrt{p}\)，即\(N^{0.25}\)个数，两两做差并与N求gcd。

但我们需要两两做差，复杂度会回去。

若\(gcd(|a-b|,N)=p\)，则\(a=b (mod p)\)。（a不等于b）

然后，我们可以随机生成一个序列，看看里面是否有模p意义下相等的两个数。

但是，我们不知道p，我们只能通过求\(gcd(|a-b|,N)\)的方法来判断\(a=b (mod p)\)是否成立。就是说，我们只能判断\(a=b (mod p)\)是否成立，不能知道\(a\%p\)的值。

这个序列，我们显然可以\(rand\)，但有一种更好的方法：

设序列\(A_i=f(A_{i-1})\)，其中\(f(x)=x^2+y\)（y为定值）。那么，若\(a=b (mod p)，f(a) mod p\)一定等于\(f(b) mod p\)。但rand就没有这个性质。

换句话说，就是mod p后的数列出现了循环（原数列没有循环）。

这样，只要找到mod p后的数列的循环即可。（若用rand（），就需要等到原数列循环，复杂度就会退化为\(\sqrt{N}\)）

找循环可以用Floyd判圈，而这个算法正好是对两个进行比较的。

但是，可能原数列循环后，都没有找到解。

所以，在判圈的时候，如果原数列循环，则退出，换一个新的y计算。

根据“生日悖论”，只要选\(\sqrt{p}\)个小于p的数，就有相等的。

由于模数是\(10^{18}\)级别的，要用快速乘。

时间复杂度：\(O(N^{0.25}*logN)\)。

代码：

int sed[4]={13131,4649,65537,28627},se;

ll n;

ll gcd(ll a,ll b)

{

	while(b!=0)

	{

		ll t=a%b;

		a=b;

		b=t;

	}

	return a;

}

ll f(ll x)

{

	return (ksc(x,x,n)+se)%n;

}

ll ksc(ll a,ll b,ll md)

{

	ll jg=0;

	while(b>0)

	{

		if(b&1)

			jg=(jg+a)%md;

		a=(a+a)%md;

		b=(b>>1);

	}

	return jg;

}

ll rho()

{

	while(1)

	{

		se=sed[rand()%4];

		ll z1=1,z2=f(z1);

		while(z1!=z2)

		{

			ll t=z1-z2;

			if(t<0)

				t=-t;

			ll g=gcd(t,n);

			if(g!=1&&g!=n)

				return g;

			z1=f(z1);

			z2=f(f(z2));

		}

	}

}

巴特西

Pollard-Rho 总结

最新文章

热门文章