米勒-洛尔方法（Miller-Rabin primality test）是一种用于检测一个数是否为质数的概率性算法。它基于费马小定理和二次探测引理，通过随机选择的底数进行多次测试，以提高检测的准确性。

米勒-洛尔方法的步骤如下：

  1. 初始化参数：
  2. 设定所需的确定性水平（通常为5），即期望错误的次数。

  3. 选择一个随机整数 ( a )，其中 ( 1 < a < n-1 )，且 ( a ) 与 ( n-1 ) 互质（即 ( \gcd(a, n-1) = 1 )）。

  4. 计算 ( x )：

  5. 计算 ( x = a^d \mod n )，其中 ( d ) 是 ( n-1 ) 的二进制表示中最低位的 1 及其后面的所有 0 所对应的指数。

  6. 判断 ( x )：

  7. 如果 ( x = 1 ) 或 ( x = n-1 )，则继续进行下一轮测试。

  8. 否则，计算 ( x = x^2 \mod n )，并重复上述步骤，直到 ( x = 1 ) 或 ( x = n-1 ) 或达到预定的迭代次数。

  9. 判断是否为质数：

  10. 如果在预定的迭代次数内没有找到 ( x = 1 ) 或 ( x = n-1 )，则认为 ( n ) 是合数（非质数）。
  11. 如果找到了 ( x = 1 ) 或 ( x = n-1 )，则继续下一轮测试，直到达到预定的迭代次数。

米勒-洛尔方法的概率性体现在每次计算 ( x ) 和 ( x^2 \mod n ) 时都存在一定的误差，但通过多次测试可以降低错误的概率。通过增加测试次数，可以进一步提高检测的准确性。

需要注意的是，米勒-洛尔方法是一种概率性算法，不能保证 100% 的准确性。**，在实际应用中，通过增加测试次数，可以使其错误概率非常低。