Miller-Rabin 素性测试算法 matlab

以下是 Miller-Rabin 素性测试算法的 Matlab 代码。

function is_prime = miller_rabin(n, k)
% MILLER_RABIN performs Miller-Rabin primality test on n
%   n: the integer to be tested
%   k: number of iterations
%   is_prime: boolean value indicating whether n is prime or not

if mod(n, 2) == 0
    is_prime = false;
    return
end

d = n-1;
r = 0;
while mod(d, 2) == 0
    d = d / 2;
    r = r + 1;
end

for i = 1:k
    a = randi([2, n-2]);
    x = mod_exp(a, d, n);
    if x == 1 || x == n-1
        continue
    end
    for j = 1:r-1
        x = mod(x^2, n);
        if x == n-1
            break
        end
    end
    if x ~= n-1
        is_prime = false;
        return
    end
end

is_prime = true;
end

function res = mod_exp(a, b, n)
% MOD_EXP computes a^b mod n using the square-and-multiply algorithm
%   a: base
%   b: exponent
%   n: modulus
%   res: result

res = 1;
while b > 0
    if mod(b, 2) == 1
        res = mod(res * a, n);
    end
    a = mod(a^2, n);
    b = b / 2;
end
end

其中，`miller_rabin` 函数接受两个参数：待测试的正整数 `n` 和测试次数 `k`，并返回一个布尔值，表示 `n` 是否为素数。该函数首先判断 `n` 是否为偶数，若是则直接返回 `false`，否则寻找整数 `d` 和 `r`，使得 `n-1 = 2^r * d`，其中 `d` 为奇数。然后对于 `k` 次随机选取的整数 `a`，利用 `mod_exp` 函数计算 `a^d mod n`，若结果为 1 或 `n-1` 则进行下一次测试，否则继续计算其平方取模的结果，直到结果为 `n-1` 或达到 `r-1` 次。如果仍然不满足，则 `n` 被判定为合数；若所有测试均通过，则 `n` 被判定为素数。

`mod_exp` 函数用于计算幂运算的结果，采用了平方-乘法算法，可以有效减少计算量。