知识点简单总结——Pollard-Rho算法

MillerRabin算法

用于对较大(int64)范围内的数判定质数。

原理：费马小定理，二次探测定理。

二次探测定理：若 $ p $ 为奇素数且 $ x ^ 2 \equiv1 ( mod \ p ) $ ，则 $ x \equiv \pm1(mod \ p) $ 。

选取多个素数 $ p $ 对要判断的数 $ x $ 进行测试：

首先进行费马小定理判断 $ x^{p-1} \equiv 1 (mod \ p) $ ，不是的话返回非。

之后设 $ k=p-1 $ 。当 $ k $ 是 $ 2 $ 的倍数时，将 $ k $ 除以 $ 2 $ ，继续计算 $ x^{k} \equiv \pm 1 (mod \ p) $ 。

不是的话返回非，否则如果结果为 $ 1 $ 且 $ 2 | k $ ，则继续重复操作，否则当 $ x^{k} \equiv -1 (mod \ p) $ 或 $ k $ 不再可除，无法继续用这个质数进行判定，返回真。

质数表随便打个，我用的 $ 2,3,7,19,61,24251 $ 。

Pollard-Rho算法

对于分解一个大合数 $ n $ ，考虑每次随机找到一个约数 $ c $ ，将 $ n/c $ 和 $ c $ 两部分递归处理。

随机一个初始变化率 $ d $ 和一个初始值 $ a_{0} $ ，每次 $ a_{i} = ( a_{i-1}^{2} +d ) mod \ n $ 。

每次求 $ gcd( | a_{i} - a_{0} | , n) $ ，如果结果不为 $ 1 $ 或 $ n $ ，那么证明分解出了一个约数。

$ a $ 最终会成环，期望长度 $ \sqrt{n} $ ，成环时更换变化率重新计算即可。

但依然需要继续优化。

考虑路径倍长，统计 $ s = \prod { | a_{i} - a_{0} | } $，每隔 $ 2^{k} $ 次将 $ s $ 一起gcd，之后将 $ a_{0} $ 设置为 $ a_{ k^{ 2 } } $ 。

#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef __int128 llint;

struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};

template<typename TP>inline void read(TP &tar)

{

	TP ret=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}

	tar=ret*f;

}

namespace RKK

{

lint fpow(lint a,lint p,lint mo){lint ret=1;while(p){if(p&1ll) ret=(llint)ret*a%mo;a=(llint)a*a%mo,p>>=1;}return ret;}

lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}

lint base[6]={2,3,7,19,61,24251};

bool mr(lint n,lint bas)

{

	if(fpow(bas,n-1,n)!=1) return 0;

	lint p=n-1;

	while(!(p&1))

	{

		p>>=1;lint g=fpow(bas,p,n);

		if(g==n-1) return 1;

		else if(g!=1ll) return 0;

	}

	return 1;

}

bool mr(lint n)

{

	if(n<2) return 0;

	for(int i=0;i<6;i++)if(n==base[i]) return 1;

	for(int i=0;i<6;i++)if(!mr(n,base[i])) return 0;

	return 1;

}

lint pr(lint n)

{

	int i=1,len=1;lint p=1,d=rand()%(n-1)+1,x=0,y=0;

	while(1)

	{

		x=((llint)x*x+d)%n;

		p=(llint)p*abs(x-y)%n;

		if(!(i&127)){lint g=gcd(p,n);if(g>1) return g;}

		if(i==len)

		{

			lint g=gcd(p,n);if(g>1) return g;

			y=x,p=1,len<<=1,i=1;

		}else i++;

	}

}

vector<lint> ans;

void getfactor(lint n,vector<lint> &fac)

{

	if(n==1ll) return;if(mr(n)){fac.push_back(n);return;}

	lint p=n;while(p>=n) p=pr(n);

	getfactor(p,fac),getfactor(n/p,fac);

}

int main()

{

	int TAT;llint n;read(TAT);while(TAT--)

	{

		srand(time(NULL));

		ans.clear();

		read(n);getfactor(n,ans),sort(ans.begin(),ans.end());

		if(ans.size()==1) puts("Prime");

		else printf("%lld\n",ans[ans.size()-1]);

	}

	return 0;

}

}

int main(){return RKK::main();}

应用

不知道（？）

巴特西

知识点简单总结——Pollard-Rho算法