程序中的素性测试

由于近期忙于公司事务和新系统的架构设计工作，博客的文章已经停更了数月。近几个月对我个人来说产生了很大的变化，我很难讲清其中的具体，但这大概会在后续的博客文章更新中体现。

但我认为，停更并非好事，而是应当避免的，因此我也在有片刻闲暇的今日在已经停止更新五个月的博客的第一篇文章。

序言

数学是科学的基础，而素数是数学的基石之一。尽管素数的概念简单直观——只有 1 和自身两个正因数的自然数——但它们在数学和计算科学领域却扮演着重要角色。

素数并非我们独立发现的，它们在自然界中以复杂的规律存在。通过对素数的理解和应用，我们得以解决各种问题，从密码学的加密算法，到搜索引擎的数据结构，甚至到量子计算的未来发展。因此，有效地检测一个数字是否为素数，对于编程来说是至关重要的技能。

在本篇博客文章中，我们将深入探讨素数校验在程序设计中的实现。我们将先从基础的数学理论开始，逐渐深入到各种算法的优化。同时探讨不同的素数检验算法，从最基础的试除法到更复杂高效的算法（如 Miller–Rabin primality test），来感受算法的历史与更迭。

素数的基础知识

在我们深入讨论如何在程序中校验素数之前，我们需要先理解素数是什么，以及它们在计算机科学中为何如此重要。

素数是一种特殊的数字，它们只有两个因数：1 和它们自身。最简单的素数是 2，然后是 3，5，7，11，13，等等。在自然数的海洋中，素数像是散落的珍珠，等待着我们去发现和欣赏。

这些数字在数学中的重要性是毋庸置疑的，而在计算机科学中，它们的作用同样重大。许多计算机科学的领域，包括但不限于密码学，数据结构和并行计算，都广泛使用素数。例如，在密码学中，大素数被用于生成公钥和私钥，从而提供强大的安全性。而在数据结构中，素数常常被用作散列函数的参数，以提高散列的效率和减小冲突的可能性。

那么，如何确定一个数字是否是素数呢？这就是我们接下来要讨论的主题：在程序中校验素数。

穷举法

在我们深入探讨更为高效的素数检验算法之前，理解最基础和直观的素数检验方法——穷举法是必要的。这种方法虽然在时间和空间复杂度上并不出色，但其简单直白的逻辑使其成为理解素数的重要工具。

穷举法的核心思想是试除所有小于 $n$ 的正整数，以判断 $n$ 是否为素数。如果我们发现一个小于 $n$ 的正整数能整除 $n$ ，那么 $n$ 就不是素数；如果所有小于 $n$ 的正整数都不能整除 $n$ ，那么 $n$ 就是一个素数。

以下是一个示例：

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

在这段代码中，首先检查 $n$ 是否小于或等于 $1$ ，如果是，则直接返回 false，因为根据定义，素数必须大于 $1$ 。然后，代码循环试除从 $2$ 到 $n-1$ 的所有整数，检查 $n$ 是否能被其中的任何一个整数整除。如果能，那么 $n$ 就不是素数，返回 false；如果所有这些数都不能整除 $n$ ，那么 $n$ 就是素数，返回 true。

然而，穷举法的效率并不高。它的时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。在时间复杂度上，由于需要试除所有小于 $n$ 的正整数，因此当 $n$ 特别大时，这种方法的效率极低。

试除法

在理解了穷举法后，我们可以继续探讨一种更高效的素数检验方法——试除法。与穷举法相比，试除法通过减少需要试除的数来优化素数检验的过程，因此在计算复杂度上有显著的提升。

试除法的核心思想是：如果一个数 $n$ 是合数（即非素数），那么它必然有一个不大于其平方根的因数。因此，要判断一个数 $n$ 是否为素数，我们只需要试除 $2$ 到 $\sqrt{n}$ 之间的所有整数。如果所有这些数都不能整除 $n$ ，那么 $n$ 就是一个素数。

以下是一个示例：

#include <cmath>

bool is_prime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

这段代码首先检查 $n$ 是否小于或等于 $1$ 。如果是，那么直接返回 false，因为根据定义，素数必须大于 $1$ 。然后，程序循环试除从 $2$ 到 $\sqrt{n}$ 的所有整数，如果 $n$ 能被其中任一整数整除，那么 $n$ 就不是素数，返回 false；如果所有这些数都不能整除 $n$ ，那么 $n$ 就是素数，返回 true。

试除法在时间复杂度上的提升明显，它的时间复杂度为 $O(\sqrt{n})$ ，这意味着在处理大数时，试除法会比穷举法更高效。其空间复杂度仍为 $O(1)$ ，这是因为我们在算法执行过程中，只需要存储常数个变量。

虽然试除法相较于穷举法在时间复杂度上有所提升，但对于极大的数，其效率仍有待改进。为了在大数素性检验上取得更好的效率，科学家们提出了更为高效的算法，例如 Miller–Rabin 素性测试等。在接下来的章节中，我们将详细讨论这些更为高效的素数检验算法。

费马素性测试

在素数检验中，我们不仅可以通过试除来寻找一个数的因数，还可以利用数学理论来进行更高效的检验，费马素性测试就是这样一种利用费马小定理的素数检验方法。

费马小定理表明，如果 $p$ 是一个素数，且 $a$ 是小于 $p$ 的任意正整数，那么 $a^{p-1}$ 除以 $p$ 的余数等于 $1$ 。如果一个数 $n$ 不满足上述性质，我们可以确定 $n$ 不是素数；但反过来，如果一个数满足上述性质，我们不能确定它一定是素数，只能说它可能是素数。因此，费马素性测试并不能完全保证结果的正确性，但在实际应用中，它的错误率是可以接受的。

以下是一个示例：

#include <cmath>
#include <random>

/**
 * @brief 用于执行模数幂运算的函数
 *
 * @param int base 基数
 * @param int exponent 指数
 * @param int modulus 模数
 * @return int 返回 (base ^ exponent) mod modulus 的结果
 */
int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

/**
 * @brief 执行费马素性测试的函数
 *
 * @param int n 要进行素数检测的数
 * @param int iterations 进行素数检测的迭代次数，默认为5
 * @return bool 如果 n 可能是素数，返回 true；否则，返回 false
 */
bool is_prime(int n, int iterations = 5) {
    if (n < 4) return n == 2 || n == 3;

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(2, n-2);

    for (int i = 0; i < iterations; ++i) {
        int a = distribution(generator);
        if (modular_pow(a, n-1, n) != 1) {
            return false;
        }
    }
    return true;
}

在这段代码中，modular_pow 函数实现了模数幂的计算，即计算 $base^{exponent} \mod modulus$ 。is_prime 函数则实现了费马素性测试。它首先检查 $n$ 是否小于 $4$ ，如果是，则直接返回 $n$ 是否为 $2$ 或 $3$ 。而后，它在 $2$ 到 $n-2$ 之间随机选取一个整数 $a$ ，并计算 $a^{n-1} \mod n$ 。如果计算结果不等于 $1$ ，那么 $n$ 就不是素数，返回 false；如果在所有迭代中计算结果都等于 $1$ ，那么返回 true，表明 $n$ 可能是素数。

费马素性测试的时间复杂度为 $O(k \log^2 n \log \log n)$ ，其中 $k$ 是迭代次数， $n$ 是我们要检验的数。它的空间复杂度为 $O(1)$ 。相比于试除法，费马素性测试在时间复杂度上有显著的提升，尤其是当处理大数时。但需要注意的是，费马素性测试可能会返回假素数，即那些满足费马小定理但实际上不是素数的数。尽管如此，通过增加迭代次数，我们可以降低这种错误的概率，使其满足实际应用的需要。

接下来的章节中，我们将介绍另一种更为高效且结果更准确的素数检验方法—— Miller–Rabin 素性测试。

Miller–Rabin 素性测试

尽管费马素性测试在素数检验中已经相当有用，但它仍有一定的局限性，特别是在处理一些特定的“伪素数”时，可能会返回误判。为了改进这个问题，我们引入一种更为强大的素性测试算法——米勒-拉宾素性测试。

米勒-拉宾测试基于费马小定理，但更进一步引入了一种附加检验，以提高检验的准确性。该方法利用了一个数学事实：对于任意一个奇素数 $p$ 和 $p-1$ 的任意因数 $q$ ，如果我们选取一个随机整数 $a$ ，那么 $a^{q}$ 的值模 $p$ 要么为 $1$ ，要么为 $-1$ ，或者说在对 $a^{2^iq}$ 的连续平方过程中，存在某个结果为 $-1$ 。

以下是一个示例：

#include <cmath>
#include <random>

/**
 * @brief 计算模数幂
 * 
 * @param int base 基数
 * @param int exponent 指数
 * @param int modulus 模数
 * @return int 返回 (base ^ exponent) mod modulus 的结果
 */
int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) result = (result * base) % modulus;
        exponent >>= 1;
        base = (base * base) % modulus;
    }
    return result;
}

/**
 * @brief 执行米勒-拉宾素性测试的函数
 * 
 * @param int n 要进行素数检测的数
 * @param int iterations 进行素数检测的迭代次数，默认为5
 * @return bool 如果 n 可能是素数，返回 true；否则，返回 false
 */
bool miller_rabin(int n, int iterations = 5) {
    if (n < 4) return n == 2 || n == 3;

    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(2, n-2);

    int r = 0;
    int d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
        ++r;
    }

    for (int i = 0; i < iterations; ++i) {
        int a = distribution(generator);
        int x = modular_pow(a, d, n);
        if (x == 1  x == n - 1) continue;
        for (int j = 0; j < r - 1; ++j) {
            x = modular_pow(x, 2, n);
            if (x == n - 1) break;
        }
        if (x != n - 1) return false;
    }

    return true;
}

米勒-拉宾素性测试的时间复杂度和费马素性测试类似，为 $O(k \log^2 n \log \log n)$ ，其中 $k$ 是迭代次数， $n$ 是我们要检验的数。它的空间复杂度为 $O(1)$ 。

相比于费马素性测试，米勒-拉宾素性测试在准确性上有显著的提升，尤其是在处理大数时。然而，它仍然是一种概率性的算法，因此，对于非常大的数或者需要非常高准确性的应用，可能需要运用更高级的素性检测方法。

多种语言代码实现：https://gist.github.com/AH-dark/306d76d001ecd94d1796f64a5ea74df6

椭圆曲线素性测试（ECPP）

至此，我们已经探讨了几种常见且有效的素数检验算法，从基本的试除法和穷举法到基于概率的费马素性测试和米勒-拉宾素性测试。这些方法已经可以处理绝大多数的素数检验需求。然而，在某些特殊的场合，例如非常大的数或者需要非常高准确性的应用，我们可能需要一种更为强大的素性检验算法。这就是我们这一章要介绍的内容——椭圆曲线素性测试。

椭圆曲线素性测试（Elliptic Curve Primality Proving，简称ECPP）是一种确定性的素数检验算法，可以在多项式时间内确定一个数是否为素数。ECPP 算法的优势在于它可以快速且准确地判断非常大的数（例如超过100位）是否为素数，且不需要任何预先已知的素数表。

椭圆曲线素性测试的理论基础深厚，需要理解椭圆曲线的数学理论。在实践中，这种算法的实现通常需要使用到高级的数学软件库，例如 GMP 库。

由于椭圆曲线素性测试的复杂性和它所需的数学知识，我在这里并不打算给出具体的代码实现。读者如果对此感兴趣，可以查阅相关的数学文献和代码库。

综上，椭圆曲线素性测试提供了一种强大且精确的素数检验方法，尤其适合需要处理大数和高准确性需求的场景。

选读：ECPP 算法概述

ECPP的主要思想是使用椭圆曲线和黎曼假设来找到一个数 $n$ 的证明因子（证人）。证明因子是一个满足特定条件的数，存在这样的数可以证明 $n$ 是素数。

在详细讨论ECPP算法之前，我们需要了解一些基础概念。

椭圆曲线：在ECPP算法中，我们使用的椭圆曲线定义在有理数域上，形式为 $y^2 = x^3 + Ax + B$ ，其中 $A, B \in \mathbb{Q}$ ，且 $4A^3 + 27B^2 \neq 0$ 以确保曲线没有奇异点。
椭圆曲线上的点加法：定义在椭圆曲线上的点加法遵循一定的几何规则。定义这样的加法操作后，椭圆曲线上的点将构成一个交换群。
Hasse定理：对于一个定义在有限域 $\mathbb{F}_q$ 上的椭圆曲线，其点的个数 $N$ 满足： $N - (q+1) \leq 2\sqrt{q}$ 。这一定理为我们寻找证明因子提供了可能。

ECPP算法的步骤如下：

选择椭圆曲线和初始点：选择一个定义在 $\mathbb{Q}$ 上的椭圆曲线 $E$ 和一个初始点 $P \in E(\mathbb{Q})$ 。我们要保证 $P$ 在模 $n$ 的剩余类环 $\mathbb{Z}/n\mathbb{Z}$ 中的阶为素数，这可以通过在多个椭圆曲线和初始点中选择来实现。
寻找证明因子：在找到适合的椭圆曲线和初始点后，我们计算点 $[m]P$ ，其中 $[m]P$ 表示点 $P$ 与自身相加 $m$ 次。我们使用 $[m] P=O$ 来寻找 $n$ 的一个证明因子 $d$ ，如果我们找到了一个满足 $\gcd(n, d) = 1$ 且 $1 < d < n$ 的 $d$ ，那么 $d$ 就是 $n$ 的一个证明因子。
证明 $n$ 是素数：如果我们找到了一个证明因子 $d$ ，那么我们可以证明 $n$ 是素数。首先，我们找到一个数 $k$ 满足 $k^2 < d < (k+1) ^2$ ，然后利用Hasse定理找到一个范围 $(k-2)\sqrt{d} < M < (k+2)\sqrt{d}$ ，然后证明在这个范围内存在一个数 $M$ 使得点 $[m]P = O$ 。这就证明了 $n$ 是素数。

这只是 ECPP 算法的概述，并没有涉及到很多细节，比如如何在实际操作中进行点的加法，以及如何实现各种优化。关于这些细节，我建议你参考专业领域的论文。

结语

经过我们的探究学习，我们看到了数学在程序设计中的重要性。从最简单的穷举法和试除法，到稍微复杂的费马素性测试，再到更高级的米勒-拉宾素性测试和椭圆曲线素性证明（ECPP）方法，数学和计算机科学相互结合，来解决我们面临的问题。

实现这些算法的过程不仅需要对数学有深入的理解，也需要熟练掌握编程技巧。不同的素数检验算法适用于不同的情况，选择合适的算法能大大提高程序的效率。特别是在处理加密和安全相关的问题时，有效的素数检验和生成技术尤为重要。

程序中的素性测试

序言

素数的基础知识

穷举法

试除法

费马素性测试

Miller–Rabin 素性测试

椭圆曲线素性测试（ECPP）

选读：ECPP 算法概述

结语

Comments

Send Comments