CC

自然万物都趋向从有序变得无序

0%

Prime Test POJ - 1811 miller素数判断&pollar_rho大数分解

发表于 更新于 分类于 Valine：

题目链接

题目

Given a big integer number, you are required to find out whether it's a prime number.

Input

The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 2 54).

Output

For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.

Sample Input

2
5
10

Sample Output

Prime
2

题意:

判断一个大整数是否是素数.

思路:

miller素数判断 & pollar_rho大数分解:

Miller-Rabin素数测试基于费马小定理：假如n是素数且gcd(a,n)=1，那么a^(n-1)≡1（mod n）.如果a^(n-1)≡1（mod n）(a为任意小于n的正整数),则可近似认为n为素数，取多个底进行试验，次数越多，n为素数的概率越大。

定义卡迈克尔数：一个合数n，若对于所有满足gcd(b,n)=1的正整数b都有b^(n-1)≡1（mod n）成立，则称之为卡迈克尔数.

为了排除卡迈克尔数导致Miller-Rabin测试出现错误，我们引进二次探测定理：如果p是素数且0<x<p，则方程x^2%p=1的解为x=1或x=p-1.这个比较难以理解,

Pollard_rho算法的大致流程是 先判断当前数是否是素数（Miller_rabin）了，如果是则直接返回。如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。

那么自然的疑问就是，怎么找到当前数n的一个因子？当然不是一个一个慢慢试验，而是一种神奇的想法。其实这个找因子的过程我理解的不是非常透彻，感觉还是有一点儿试的意味，但不是盲目的枚举，而是一种随机化算法。我们假设要找的因子为p，他是随机取一个x1，由x1构造x2，使得｛p可以整除x1-x2 && x1-x2不能整除n｝则p=gcd（x1-x2，n），结果可能是1也可能不是1。如果不是1就找寻成功了一个因子，返回因子；如果是1就寻找失败，那么我们就要不断调整x2，具体的办法通常是x2=x2*x2+c（c是自己定的）直到出现x2出现了循环==x1了表示x1选取失败重新选取x1重复上述过程

代码:

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long LL;
int pri[] = {2,3,5,7,11,13,17,19,23,29,31};
LL minfacotr;

LL mult(LL a, LL b, LL mod){//大数乘法.
    LL ans = 0;
    while(b){
        if (b&1){
            ans+= a;
            if (ans >= mod) ans -= mod;
        }
        b >>= 1;
        a <<= 1;
        if (a >= mod) a-= mod;
    }return ans;
}

LL qpow(LL x, LL n, LL mod){
    LL ans = 1;
    while(n){
        if (n&1) ans = mult(ans, x, mod);
        x = mult(x, x, mod);
        n >>= 1;
    }return ans;
}

bool wintness(LL n, LL a){
    LL p = qpow(a, n-1, n);
    if(p != 1) return false;
    LL s = n - 1;
    while(!(s&1)&& p == 1){//二次探测定理
        s >>= 1;
        p = qpow(a, s, n);
    }if (p == 1 || p == n - 1) return true;
    return false;
}

bool miller_rabin(LL n){
    if (n < 32){
        for(int i = 0; i < 11; ++i)
            if(n == pri[i])
                return true;
        return false;
    }for(int  i = 0 ;i < 10; ++i)
        if(!wintness(n,pri[i])) return false;
    return true;

}

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

LL pollard_rho(LL n, LL c){
    //随机生成x, 
    LL x= rand() % n, y = x, i = 1, k = 2, d;
    while(1){
        i++;
        x =(mult(x, x, n) + 10) % n;//构造另一个x.
        d = gcd(y-x+n,n);
        if(d > 1 && d < n) return d;//如果找到因子则返回,
        if(y == x) return n;//出现循环
        if (i == k) {//一个优化,不是很懂,
            y = x;
            k <<= 1;
        }
    }
}

void findfactor(LL n){
    if(miller_rabin(n)){//如果当前数是素数,则更新最小因子
        minfacotr = min(minfacotr,n);
        return ;
    }
    LL p = n;
    while(p >= n)  p = pollard_rho(n, rand() % (n - 1) + 1);//找到一个n的因子
    findfactor(p);//递归求解
    findfactor(n / p);

}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        LL n;
        scanf("%lld", &n);
        if(miller_rabin(n))
            printf("Prime\n");
        else {
            minfacotr = n;
            findfactor(n);
            printf("%lld\n",minfacotr);
        }
    }return 0;
}