素数测试算法：Wilson定理、费尔马小定理与二次探测

"素数测试-算法设计与分析" 在计算机科学和数学中，素数测试是一种确定一个给定正整数是否为素数（质数）的算法。本资源主要探讨了三种不同的素数测试方法：Wilson定理、费尔马小定理以及基于二次探测的算法，并提供了一个Java实现的蒙特卡罗素数测试算法。 1. **Wilson定理**：这是判定一个正整数n是否为素数的理论依据。根据Wilson定理，如果n是一个素数，那么(n-1)! 除以n的余数等于-1。换言之，所有小于n且不等于1的正整数相乘，然后减去1，结果能被n整除，那么n就是一个素数。这个定理是理论上的，实际应用中计算(n-1)! 的阶乘过于复杂。 2. **费尔马小定理**：费尔马小定理是另一个用于素数测试的重要工具。它表明，如果p是素数，而a是任意一个0<a<p的整数，那么a的(p-1)次幂除以p的余数总是1。这个定理常用于简化素数测试，例如在RSA加密算法中。 3. **二次探测定理**：在模运算下，如果p是素数，那么方程x^2 ≡ 1 (mod p) 只有解x=1和x=p-1。这意味着如果存在其他解，那么p就不是素数。在提供的Java代码中，`power`函数利用了这一点，通过计算ap^2模n的结果来辅助素数检测。 4. **Java实现的蒙特卡罗素数测试算法**：`prime`函数是一个随机性较强的测试方法，它基于概率论。它首先创建一个随机数a（范围在2到n-3之间），然后计算a的(n-1)次幂模n的结果。如果结果不等于1或n-1，或者在中间过程中发现一个数的平方模n等于1但本身不等于1或n-1，那么标记n为合数。否则，认为n可能是素数。这个算法在多次重复运行后，错误概率会显著降低。 5. **算法的正确性和效率**：`prime`算法被描述为一个偏假3/4正确的蒙特卡罗算法，意味着在最坏情况下，错误率最多为1/4。然而，实际运行时，由于随机数的性质，这个错误率通常会更低。通过增加测试次数，可以进一步提高确定性的程度。 这些算法在处理大整数时特别有用，因为它们提供了比朴素的逐个检查因数更高效的测试方法。在密码学、编码和数据安全等领域，快速有效的素数检测是至关重要的。