miller_rabbin素数判定。若不是，则pollard_rho分解质因子，找到最小即可。

Miller-rabin

Miller-rabin算法是一个用来快速判断一个正整数是否为素数的算法。它利用了费马小定理，即：如果p是质数，且a，p互质，那么a^(p-1) mod p恒等于1。也就是对于所有小于p的正整数a来说都应该符合a^(p-1) mod p恒等于1。那么根据逆否命题，对于一个p，我们只要举出一个a（a<p）不符合这个恒等式，则可判定p不是素数。Miller-rabin算法就是多次用不同的a来尝试p是否为素数。

增大a的数量可以减小出错概率，一般取s=100就足够了。

 #include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define maxTest 100

long long int Random(long long int n)

{

    return (long long int)((double)rand()/RAND_MAX*n+0.5);

}

long long int Modular_Exp(long long int a, long long int b, long long int n) // a^b mod n

{

    long long int ans;

    if(b == 0)

        return 1;

    if(b == 1)

        return a % n;

    ans = Modular_Exp(a, b/2, n);

    ans = ans * ans % n;

    if(b % 2)

        ans = ans * a % n;

    return ans;

}

bool Miller_Rabbin(long long int n)

{

    for(int i=1; i<=maxTest; ++i)//

    {

        long long int a = Random(n-2)+1;//生成小于等于n-1的随机数

        if(Modular_Exp(a, n-1, n) != 1)

            return false;

    }

    return true;

}

int main()

{

    srand(time(NULL));

    long long int n;

    while(scanf("%lld", &n) == 1) {

        if(Miller_Rabbin(n))

            printf("Primer\n\n");

        else

            printf("Not Prime\n\n");

    }

    return 0;

}

pollard-rho

这是一个用来快速对整数进行质因数分解的算法，需要与Miller-rabin共同使用。求n的质因子的基本过程是，先判断n是否为素数，如果不是则按照一个伪随机数生成过程来生成随机数序列，对于每个生成的随机数判断与n是否互质，如果互质则尝试下一个随机数。如果不互质则将其公因子记作p，递归求解p和n/p的因子。如果n是素数则直接返回n为其素因子。

至于这个随机数序列是如何生成的暂时还不能理解，而且也是有多种不同的方式。这个序列生成过程中会产生循环，遇到循环则立即退出。

math_RSA