miller-rabin matlab,Miller-Rabin素数判断算法-白红宇

miller-rabin matlab,Miller-Rabin素数判断算法

阅读量：793 次

发布时间：2023-02-09

本文共 1508 字，大约阅读时间需要 5 分钟。

Miller-Rabin素数判断算法是现代密码学中广泛应用的素数测试方法。该算法通过将奇数n表示为n=1+d*2^s的形式，然后测试随机选择的数a是否满足特定模运算条件来判断n是否为素数。

具体步骤如下：

将n分解为n=1+d*2^s的形式，并初始化s和d。

生成区间[2, n-2]内的随机数a。

计算a^d mod n的值，记为x。

如果x=1或x=n-1，则a通过测试，继续下一个随机数。

否则，对每个r=0到s-1，计算x = x^2 mod n：

如果x=n-1，则a通过测试，继续下一个随机数。

如果x≠n-1且x≠1，则n不是素数。

如果所有a都通过测试，则n是素数。

代码实现如下：

#include 
   
    #include 
    
      // rand()#include 
     
        // srand()using namespace std;void Reduce(int nn, int &s, int &d) {    while (d % 2 == 0) {        d /= 2;        s++;    }}bool Witness(int n, int x, int a, int d, int s) {    if (x != 1 && x != n - 1) {        for (int r = 0; r < s; r++) {            x = (x * x) % n;            if (x == n - 1) {                return true;            }        }        return false;    }    return true;}int mod_power(int M, int N, int n) {    int R = 1;    for (int i = 0; i < N; R = (R * M) % n) {        ;    }    return R;}bool Re_loop(int n, int K, int d, int s) {    for (int j = 0; j < K; j++) {        int a = 2 + rand() % (n - 3);        int x = mod_power(a, d, n);        if (x == 1 || x == n - 1) {            continue;        }        if (!Witness(n, x, a, d, s)) {            return false;        }    }    return true;}int main() {    int n = 1221;    int s = 0, d = n - 1;    Reduce(n, s, d);    if (Re_loop(n, 7, d, s)) {        cout << "It is a prime in a chance 1-4^(-7)." << endl;    } else {        cout << "It is composite." << endl;    }    return 0;}

该实现通过模拟多次测试来提高准确性。每次测试选择不同的a值，减少了错误率。通过设置K次测试，错误概率被降低到10^-7，确保结果的准确性。

转载地址：http://azffk.baihongyu.com/

你可能感兴趣的文章