费马素性检验

1. 引言

质数在数学领域一直备受关注，如今在计算机科学和密码学中也扮演着至关重要的角色。

判断一个数 是否为质数的最朴素方法是检查它是否能被 2 到 之间的任意数整除。这种方法虽然简单，但效率低下。

更高效的方法包括“埃拉托斯特尼筛法”（Sieve of Eratosthenes），以及一些更现代的判定质数的算法。然而，这些方法在处理大数时依然开销较大。在某些场景中，我们可以使用伪素数（pseudoprime）来替代真素数。

在本文中，我们将介绍费马小定理和费马素性检验。 这些方法可以快速识别一些非素数。

---

2. 费马小定理

费马小定理指出：如果一个数 是素数，那么对于任意 属于区间 ，都有如下等式成立：

$$ a^{n-1} \equiv 1 \pmod{n} $$

上式中，mod 表示模运算。我们读作“ 在模 意义下与 1 同余”，即当 除以 时，余数为 1。

如果对于某个 ，这个等式不成立，那么 必然是合数。

例如，判断 23 是否为质数：

我们验证：

$$ a^{22} \equiv 1 \pmod{23} $$

选择 ，计算：

$$ 2^{22} \equiv 1 \pmod{23} $$

再试 ：

$$ 9^{22} \equiv 1 \pmod{23} $$

在这个例子中，无论选哪个 ，结果都成立，说明 23 是质数。

⚠️ 但要注意：有些合数也能通过费马检验。

例如，561 就是一个典型的“卡迈克尔数（Carmichael number）”，它满足：

$$ a^{560} \equiv 1 \pmod{561} $$

但 561 实际上是合数，因为：

$$ 3 \times 11 \times 17 = 561 $$

这类数虽然不是质数，但能通过所有费马测试，因此被称为“伪素数”。

尽管如此，费马检验仍被广泛用于快速判断一个数是否是“可能的质数”。对于大数，我们只需随机测试几个 值，若全部通过，则认为它可能是质数。

---

3. 费马素性检验算法

实现费马素性检验的关键在于：我们无法对所有可能的 值进行测试，否则效率太低。我们只随机选取几个 值进行测试，若都通过，则认为该数是“伪素数”。

以下是算法伪代码：

algorithm IsPrime(n, k):
    // INPUT
    //    n = number to be tested for primality
    //    k = number of times the test will be repeated
    // OUTPUT
    //    Returns "Composite" if n is found to be composite, 
    //    "Pseudoprime" otherwise
    i <- 1
    while i <= k:
        a <- uniform random number between 2 and n - 1
        
        if a^(n - 1) != 1 (mod n):
            return "Composite"
        
        i <- i + 1
    
    return "Pseudoprime"

我们对 个不同的随机 值执行测试。其中计算 的效率非常关键。

✅ 推荐使用快速幂（binary exponentiation）来实现模幂运算，而不是直接调用幂函数。

以下是快速幂的实现：

algorithm Power(x, e, m):
    // INPUT
    //    x = exponentiation base
    //    e = exponent
    //    m = modular operand
    // OUTPUT
    //    Returns the residual of x^e mod m
    result <- 1
    while e > 0:
        if e is odd:
            result <- (result * x) mod m
            e <- e - 1
        else:
            x <- (x * x) mod m
            e <- e / 2
    
    return result

使用快速幂算法，计算 的时间复杂度约为：

$$ \mathcal{O}(\log^2 n \times \log n) = \mathcal{O}(k \log^3 n) $$

---

4. Java 实现

下面是一个 Java 实现的费马素性检验器，包含边缘情况处理和快速幂运算：

public class FPT {

    static int mPower(int x, int e, int m) {
        int res = 1;

        while (e > 0) {
            if ((e % 2) == 1) {
                res = (res * x) % m;
                e--;
            } else {
                x = (x * x) % m;
                e = e / 2;
            }
        }
        return res;
    }

    static boolean isPrime(int n, int k) {
        if (n % 2 == 0 && n != 2)  {
            return false;
        }

        if (n <= 3)  {
            return true;
        }

        while (k > 0) {
            int a = (int) Math.random() * (n - 3) + 2;
            if (mPower(a, n - 1, n) != 1) {
                return false;
            }

            k--;
        }

        return true;
    }
}

⚠️ 注意：

• 该实现未处理非常大的数，如需支持大整数，建议使用 BigInteger。
• 随机数生成方式简单，实际应用中应使用更安全的随机源。
• 对于卡迈克尔数（如 561），该测试可能会误判为质数。

---

5. 小结

• ✅ 费马小定理提供了一个快速判断素数的方法。
• ❌ 但存在“卡迈克尔数”这类伪素数，会通过所有费马测试。
• ⚠️ 费马检验不是确定性算法，只能判断一个数是否是“可能的质数”。
• ✅ 适用于需要快速筛选质数的场景，如公钥加密中的密钥生成阶段。

总结一句话：
费马素性检验是一种概率性素数检测方法，速度快但存在误判风险，适合用作初步筛选。