Miller Rabin Test

Miller-Rabin测试是一种用于检测一个数是否为素数的概率性算法。它基于米勒-拉宾定理，该定理描述了一种方法来验证一个给定的数是否为素数。

该算法的基本思想是通过进行多次的随机测试来判断一个数是否为合数。如果该数通过所有的测试，那么它很有可能是一个素数。

具体来说，Miller-Rabin测试的步骤如下：
1. 将待测数 n-1 分解为 2^r * d，其中 r >= 1，d 是一个奇数。
2. 随机选择一个整数 a，满足 1 < a < n-1。
3. 计算 a^d mod n，如果结果为 1 或 n-1，则可能是一个素数。
4. 重复步骤 3 共 r 次，每次计算的结果都与前一次不同。
5. 如果所有的计算结果都不等于 1 或 n-1，则 n 是合数。

重复执行上述步骤多次可以提高测试的准确性，但无法保证绝对的正确性。因此，Miller-Rabin测试是一种概率性算法，有一定的误判率，但在实践中被广泛使用，并且效果良好。

需要注意的是，对于特别大的数或特定情况下的边界情况，Miller-Rabin测试可能需要更多的迭代次数来获得较高的准确性。