POJ 1811 Prime Test /Miller-Rabin素数测试+Pollard Rho 大整数分解

发表于 | 分类于 | 阅读次数:
字数统计: 817 字

题目连接：http://poj.org/problem?id=1811

Miller-Rabin素数测试

该算法是随机算法，可以用来检测一个很大的数字（2^64范围)是不是素数。主要基于两个定理：费马小定理和二次探测定理
学习链接：
Miller-Rabin素数测试学习小计
Miller-Rabin素数测试学习笔记
kuangbin 模板

Pollard Rho 大整数分解

该算法是试除法和筛选法之外对比较大的整数的分解算法
学习链接：
Pollard Rho 大整数分解

题意

给出一个非常大的数（2^54范围），如果这个数是素数，则输出Prime ，否则输出其最小的素因子

题解

套用Miller-Rabin算法和Pollard-rho算法的模板题

代码（模板）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数

const int S=20; //随机算法判定次数

//计算 (a*b)%c  加法快速幂
ll mul_mod(ll a,ll b,ll c)
{
	a%=c;
	b%=c;
	ll ret=0;
	while(b)
	{
		if(b&1)
			ret+=a,ret%=c;
		a<<=1;
		if(a>=c)a%=c;
		b>>=1;
	}
	return ret;
}

// 计算x^n %c
ll pow_mod(ll x,ll n,ll mod)
{
	if(n==1) return x%mod;
	x%=mod;
	ll tmp=x;
	ll ret=1;
	while(n)
	{
		if(n&1) ret=mul_mod(ret,tmp,mod);
		tmp=mul_mod(tmp,tmp,mod);
		n>>=1;
	}
	return ret;
}

//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(ll a,ll n,ll x,ll t)
{
	ll ret=pow_mod(a,x,n);
	ll last=ret;
	for(int i=1;i<=t;i++)
	{
		ret=mul_mod(ret,ret,n);
		if(ret==1 && last!=1 && last!=n-1) return true;
		last=ret;
	}
	if(ret!=1) return true;
	return false;
}

// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;
bool Miller_Rabin(ll n)
{
	if(n<2) return false;
	if(n==2) return true;
	if((n&1)==0) return false;   //偶数
	ll x=n-1,t=0;
	while(!(x&1)) 
	{
		x>>=1;
		t++;
	}
	for(int i=0;i<S;i++)
	{
		ll a=rand()%(n-1)+1;
		if(check(a,n,x,t))
			return false;
	}
	return true;
}


// pollard_rho 算法进行质因数分解
ll factor[100];   //分解结果
int tol;    //分解个数

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

ll Pollard_rho(ll x,ll c)
{
	ll i=1,k=2;
	ll x0=rand()%x;
	ll y=x0;
	while(1)
	{
		i++;
        x0=(mul_mod(x0,x0,x)+c)%x;
        ll d=gcd(y-x0,x);
        if(d!=1&&d!=x) return d;
        if(y==x0) return x;
        if(i==k){y=x0;k+=k;}
	}
}

//对n进行素因子分解
void findfac(ll n)
{
	if(Miller_Rabin(n))
	{
		factor[tol++]=n;
		return;
	}
	ll p=n;
    while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
    findfac(p);
    findfac(n/p);
}

void solve()
{
	int t;
	ll n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		if(Miller_Rabin(n))
		{
			printf("Prime\n");
			continue;
		}
		tol=0;
		findfac(n);
		ll ans=factor[0];
		for(int i=1;i<tol;i++)
			ans=min(ans,factor[i]);
		printf("%lld\n",ans);
	}
}