RSA大数运算实现（1024位n）（6）Miller-Rabin素性检测

简介

??在(1)中，素性检验使用的是费马小定理，对于待检测的数n，如果a^n-1≡1(mod n)，则认为n是素数，为了运算更快，a不是取随机的，而是取2、3、5、7。这样做不是很严谨，即便随机取a，费马检测对于一些伪素数也会失效，如561【对所有的正整数x，1<x<n，若x^n-1≡1(mod n)，但是n是一个合数，这样的n成为Carmichael数】。
??而Miller-Rabin素性检验，每做一次，出错概率至多为1/4，对于同一个数，多次检验，就能够在概率上保证一个数是素数。如果对一个数n，选25个不同的x进行Miller-Rabin检测，若每次都判定为n是素数，则n是合数的概率小于10¹⁵分之一。

算法描述

输入：奇整数n，n=1+2^k·q
输出：1(n是素数) 或 0(n是合数)

1. 随机选取x，使得1<x<n。
2. 令j=0，计算y=x^q(mod n)。
3. 如果y=n-1，或者y=1且j=0，结束算法，返回1；如果y=1且j>0，进入步骤5（否则，进入步骤4）。
4. j=j+1，如果j<k，计算y=y²(mod n)，进入步骤3。
5. 返回0。

代码

int miller_b(BN n,int t=3)
{
    if ((n[1] & 1U) == 0)return 0;srand((unsigned)time(NULL));BN n_1 = {
     0 }, q = {
     0 }, temp = {
     0 };BN x = {
     0 };//x是随机获得的BN y = {
     0 };int flag = 1;//假设是素数cpy_b(n_1, n);n_1[1] = n_1[1] - 1U;//n-1int bits = getbits_b(n_1);int k = 0;cpy_b(q, n_1);for (int i = 1; i < bits; i++){
    if (uint32_t(q[1] & 1U) == 0U){
    k++;shr_b(q);}elsebreak;}for (int times = 0; times < t; times++)//默认做3次检验{
    memset(x, 0U, sizeof(x));randBN(x, getbits_b(n));if (cmp_b(x, n))shr_b(x);//cout << "x = " << bn2str(x)<<endl;//cout << "x 有 " << getbits_b(x) << "位" << endl;//cout << "q= " << bn2str(q) << endl;//cout << "k= " << k << endl << endl;modexp_b(x, q, n, y);//y=x^q(mod n)if ((y[0] == 1U && y[1] == 1U) || !cmp_b(y, n_1))continue;for (int j = 1; j < k; j++){
    modmul(y, y, n, temp);if (temp[0] == 1U && temp[1] == 1U)break;else if (!cmp_b(temp, n_1))goto prime;cpy_b(y, temp);}flag=0;//是合数break;prime://素数;}return flag;
}

运行结果

运行速度并不是很慢，一次十几毫秒。找素数比openssl慢不少，openssl产生一个2048位的素数只需要不超过3秒。