[Miller-Rabin & Pollard-rho]【学习笔记】

Miller-Rabin & Pollard-rho

很久之前就学过了...今天重学一遍

---

利用费马小定理，但不能判断伪素数的情况

基于a的伪素数n：

\(a^{n-1} \equiv 1 \pmod n\)

如果对于所有与n互质的数都成立，则n为Carmichael数




定理：

对于质数\(p\)和\(e \ge 1\)

\[x^2 \equiv 1 \pmod p^e
\]

只有两个解\(x=1,\ x=-1\)

分解$n=u*2^t$,反复平方的时候如果存在非平凡平方根则不是质数
可以证明Carmicheal数一定不是$p^e$


Pollard-rho启发式因子分解期望$O(\sqrt{p})$找到一个为p的质因子

快速乘要用long double黑科技

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline ll read(){

	char c=getchar();ll x=0,f=1;

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

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

	return x*f;

}

ll n;

ll Mul(ll a, ll b, ll P) {

	ll t = (a*b - (ll)((long double)a/P*b+1e-8)*P);

	return t<0 ? t+P : t;

}

ll Pow(ll a, ll b, ll P) {

	ll ans=1; a%=P;

	for(; b; b>>=1, a=Mul(a, a, P))

		if(b&1) ans=Mul(ans, a, P);

	return ans;

}

bool witness(ll a, ll n, ll u, int t) {

	ll x=Pow(a, u, n), y=x;

	for(int i=1; i<=t; i++) {

		x=Mul(x, x, n);

		if(x==1 && y!=1 && y!=n-1) return true;

		y=x;

	}

	return x!=1;

}

bool MillerRabin(ll n) {

	if(n==2) return true;

	if(n<=1 || !(n&1)) return false;

	ll u=n-1, t=0;

	while(!(u&1)) u>>=1, t++;

	for(int i=1; i<=10; i++)

		if(witness(rand()%(n-1)+1, n, u, t)) return false;

	return true;

}

ll gcd(ll a, ll b) {return b==0?a:gcd(b, a%b);}

ll rho(ll n, ll c) {

	int k=2; ll x=rand()%n, y=x, d=1;

	for(int i=1; d==1; i++) {

		x=(Mul(x,x,n)+c)%n;

		d=gcd(n, y>x?y-x:x-y);

		if(i==k) y=x, k<<=1;

	}

	return d;

}

ll Max;

void solve(ll n) {

	if(n==1) return;

	if(MillerRabin(n)) {Max=max(Max, n); return;}

	ll t=n;

	while(t==n) t=rho(n, rand()%(n-1)+1);

	solve(t); solve(n/t);

}

int main() {

	freopen("in","r",stdin);

	srand(317);

	int T=read();

	while(T--) {

		n=read();

		Max=0;

		solve(n);

		if(Max==n) puts("Prime");

		else printf("%lld\n",Max);

	}

}