大数的素性判断与因数分解

为什么要进行大整数的因数分解

• RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

• 著名的RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

• RSA的安全性是基于大整数分解的困难性假定。n=pq，目前分解一个大整数仍然是 一个公认的难题，还没能证明大整数分解是NP问题，也许是目前还没发现多项目时间的分解算法

如何进行大整数的因数分解

先用Miller-Rabin算法进行素数判断，若不是素数，再使用Pollard-rho算法找出最小的质因数。

素数判断：Miller-Rabin算法

• 1976年，Miller提出了一个基于广义黎曼猜想的判断一个数是素数的确定性算法

• 1980年，Rabin把上述算法改成不需要基于任何猜想的概率算法

二次探测定理

若n是一个素数，且$0 < x < n$，则方程$x^2 \equiv 1(mod n)$ 的解为$x=1$ 或 $x=n-1$

引理

设一个奇素数$n=2^s \cdot d+1$ ，其中d为奇数，s为正整数，对于任意a,要么满足$a^d \equiv 1({mod }n)$ ,

要么满足$a^{{2^r} \cdot d} \equiv -1(mod n)$ 对于$0 \le r \le s-1$ 都成立。

二次探测定理引理的逆否命题

设大于2的一个奇数$n=2^s \cdot d+1$ ，其中d为奇数，s为正整数，若我们能找到一个a满足$a^d \ne 1(mod n)$ ，

且$a^{{2^r} \cdot d} \ne -1(mod n)$ 对于$0 \le r \le s-1$ 都成立，那么n不是素数。

• 每次随机检测的错误概率为25%

• 那么执行k次测试后，检测错误的概率为$ \cfrac{1}{4^k}$ 。

• 对于64位以内的奇数

  n <18,446,744,073,709,551,616 = 264,只需要选取 a = 2, 3, 5, 7, 11, 13, 17, 19, 23,
  29, 31, 以及37(40以内的素数)即可100%确定素数。

复杂度

设测试次数为k，要测试的数为n

那么一般高精度乘法的复杂度为$O(klog_2^3n)$ ，

使用FFT来实现高精度乘法后的复杂度为$O(klog_2^2n)$ 。

代码

//快速乘取模，利用二进制
long long mult_mod(long long a,long long b,long long c)
{
    a %= c; b %= c;
    long long ret = 0;
    long long tmp = a;


    while(b)
    {
        if(b & 1)
        {
            ret += tmp;
            if(ret > c)ret -= c;//直接取模慢很多
        }
        tmp <<= 1;
        if(tmp > c)tmp -= c; b >>= 1;
    }    
    return ret;
}

//快速幂取模，利用二进制
// 计算 ret = (a^n)%mod
long long pow_mod(long long a,long long n,long long mod)
{
    long long ret = 1;
    long long temp = a%mod;
    while(n)
    {
        if(n & 1)ret = mult_mod(ret,temp,mod); temp = mult_mod(temp,temp,mod);
        n >>= 1;
    }
    return ret;
}

// 通过 a^(n-1)=1(mod n)来判断n是不是素数
// n-1 = x*2^t 中间使用二次判断
// 是合数返回true, 不一定是合数返回false
bool check(long long a,long long n,long long x,long long t)
{
    long long ret = pow_mod(a,x,n);
    long long last = ret;
    for(int i = 1;i <= t;i++)
    {
        ret = mult_mod(ret,ret,n);
        if(ret == 1 && last != 1 && last != n-1)return true;//合数
        last = ret;
    }
    if(ret != 1)return true; 
    else return false;
}
//**************************************************
// Miller_Rabin算法
// 是素数返回true,(可能是伪素数)
// 不是素数返回false
//**************************************************
bool Miller_Rabin(long long n)
{
    if( n < 2)return false; if( n == 2)return true;
    if( (n&1) == 0)return false;//偶数
    long long x = n - 1;
    long long t = 0;
    while( (x&1)==0 ){x >>= 1; t++;}


//    srand(time(NULL));/* *************** */

    for(int i = 0;i < S;i++)
    {
        long long a  = rand()%(n-1) + 1;
        if( check(a,n,x,t) )
    return false;
    }
    return true;
}

因数分解：Pollard-rho算法

• 1975年由John Pollard提出的一个用于求给定合数的最小质因子的算法。

算法思路

若存在两个整数$x_1,x_2$ ，且n不是$x_1-x_2$的因数，
则$x_1-x_2$的其中一个因子$p=gcd(x_1-x_2,n)$也是n的一个因子。

寻找$x_1,x_2$:

1. 随机选取一个$x_1$
2. 利用一个设计好的函数f(x)计算$x_2=f(x_1)$ ，通常使用$f(x)=x^2+c$ (c是一个常数)
3. 计算$d=gcd(x_1-x_2,n)$ ，若d不是1，则d是n的一个因数，否则，令$x_1=x_2$ ，返回步骤1

找到一个因子p后

• 对p和n/p递归使用Pollard-rho算法，直到都是素数。

代码

long long factor[10000];//质因素分解结果（刚返回时时无序的）
int tol;//质因素的个数，编号0~tol-1

long long gcd(long long a,long long b)
{
    long long t;
    while(b)
    {
        t = a; a = b;
        b = t%b;
    }
    if(a >= 0)return a;
    else return -a;
}

//找出一个因子
long long pollard_rho(long long x,long long c)
{
    long long i = 1, k = 2;
//    srand(time(NULL));
    long long x0 = rand()%(x-1) + 1;
    long long y = x0;
    while(1)
    {
        i ++;
        x0 = (mult_mod(x0,x0,x) + c)%x;
         long long 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进行素因子分解，存入factor. k设置为107左右即可
void findfac(long long n,int k)
{
    if(n == 1)return;
    if(Miller_Rabin(n))
    {
        factor[tol++] = n;
        return;
    }

    long long p = n; int c = k; 
    while( p >= n)
    p = pollard_rho(p,c--);//值变化，防止死循环k
    findfac(p,k); 
    findfac(n/p,k);
}

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法