跳转至

素数

素数与合数的定义，见 数论基础。

素数计数函数：小于或等于 \(x\) 的素数的个数，用 \(\pi(x)\) 表示。随着 \(x\) 的增大，有这样的近似结果：\(\pi(x) \sim \dfrac{x}{\ln(x)}\)。

素性测试

素性测试（Primality test）可以用于判定所给自然数是否为素数。

素性测试有两种：

  1. 确定性测试：绝对确定一个数是否为素数。常见例子包括试除法、Lucas–Lehmer 测试和椭圆曲线素性证明。
  2. 概率性测试：通常比确定性测试快很多，但有可能（尽管概率很小）错误地将 合数 识别为质数（尽管反之则不会）。因此，通过概率素性测试的数字被称为 可能素数，直到它们的素数可以被确定性地证明。而通过测试但实际上是合数的数字则被称为 伪素数。有许多特定类型的伪素数，最常见的是费马伪素数，它们是满足费马小定理的合数。概率性测试的常见例子包括 Miller–Rabin 测试。

试除法

暴力做法自然可以枚举从小到大的每个数看是否能整除。

参考实现 
1
2
3
4
5
6
bool isPrime(int a) {
  if (a < 2) return false;
  for (int i = 2; i < a; ++i)
    if (a % i == 0) return false;
  return true;
}

1
2
3
4
5
6
7
def isPrime(a):
    if a < 2:
        return False
    for i in range(2, a):
        if a % i == 0:
            return False
    return True

这样做是十分稳妥了，但是真的有必要每个数都去判断吗？

很容易发现这样一个事实：如果 \(x\) 是 \(a\) 的约数，那么 \(\frac{a}{x}\) 也是 \(a\) 的约数。

这个结论告诉我们，对于每一对 \((x, \frac{a}{x} )\)，只需要检验其中的一个就好了。为了方便起见，我们之考察每一对里面小的那个数。不难发现，所有这些较小数就是 \([1, \sqrt{a}]\) 这个区间里的数。

由于 \(1\) 肯定是约数，所以不检验它。

参考实现 
1
2
3
4
5
6
bool isPrime(int a) {
  if (a < 2) return 0;
  for (int i = 2; (long long)i * i <= a; ++i)  // 防溢出
    if (a % i == 0) return 0;
  return 1;
}

1
2
3
4
5
6
7
def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True

Fermat 素性测试

Fermat 素性检验 是最简单的概率性素性检验。

我们可以根据 费马小定理 得出一种检验素数的思路：

基本思想是不断地选取在 \([2, n-1]\) 中的基 \(a\)，并检验是否每次都有 \(a^{n-1} \equiv 1 \pmod n\)。

参考实现 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
bool millerRabin(int n) {
  if (n < 3) return n == 2;
  // test_time 为测试次数,建议设为不小于 8
  // 的整数以保证正确率,但也不宜过大,否则会影响效率
  for (int i = 1; i <= test_time; ++i) {
    int a = rand() % (n - 2) + 2;
    if (quickPow(a, n - 1, n) != 1) return false;
  }
  return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def millerRabin(n):
    if n < 3:
        return n == 2
    # test_time 为测试次数,建议设为不小于 8
    # 的整数以保证正确率,但也不宜过大,否则会影响效率
    for i in range(1, test_time + 1):
        a = random.randint(0, 32767) % (n - 2) + 2
        if quickPow(a, n - 1, n) != 1:
            return False
    return True

如果 \(a^{n−1} \equiv 1 \pmod n\) 但 \(n\) 不是素数，则 \(n\) 被称为以 \(a\) 为底的 伪素数。我们在实践中观察到，如果 \(a^{n−1} \equiv 1 \pmod n\)，那么 \(n\) 通常是素数。但这里也有个反例：如果 \(n = 341\) 且 \(a = 2\)，即使 \(341 = 11 \cdot 31\) 是合数，有 \(2^{340}\equiv 1 {\pmod {341}}\)。事实上，\(341\) 是最小的伪素数基数。

很遗憾，费马小定理的逆定理并不成立，换言之，满足了 \(a^{n-1} \equiv 1 \pmod n\)，\(n\) 也不一定是素数。甚至有些合数 \(n\) 满足对任意满足 \(a\perp n\) 的整数 \(a\) 均有 \(a^{n−1} \equiv 1 \pmod n\)，这样的数称为 Carmichael 数。

Carmichael 函数

对正整数 \(n\)，定义 Carmichael 函数（卡迈克尔函数）为对任意满足 \((a,n)=1\) 的整数 \(a\)，使

\[ a^m\equiv 1\pmod n \]

恒成立的最小正整数 \(m\).

即：

\[ \lambda(n)=\max\{\delta_n(a):(a,n)=1\} \]

Carmichael 函数有如下性质：

  1. （Carmichael 定理）对任意素数 \(p\) 和任意正整数 \(r\)，

    \[ \lambda\left(p^r\right)=\begin{cases} \frac{1}{2}\varphi\left(p^r\right), & p=2 \land r\geq 3, \\ \varphi\left(p^r\right), & \text{otherwise}. \end{cases} \]
    证明

    该定理等价于：

    若模 \(n=p^r\) 有 原根，则 \(\lambda(n)=\varphi(n)\)，否则 \(\lambda(n)=\dfrac{1}{2}\varphi(n)\).

    当模 \(p^r\) 有原根时，由 原根存在定理 可知命题成立。否则 \(p=2\) 且 \(r\geq 3\)，我们有：

    \[ \lambda\left(2^r\right)\mid 2^{r-2} \]

    又由 \(5^{2^{r-3}}\equiv 1+2^{r-1}\pmod{2^{r-2}}\) 知 \(\lambda\left(2^r\right)>2^{r-3}\)，因此

    \[ \lambda\left(p^r\right)=2^{r-2}=\frac{1}{2}\varphi\left(p^r\right) \]

    进而有：

    1. 对任意正整数 \(n\)，有 \(\lambda(n)\mid \varphi(n)\)

    2. 对任意正整数 \(a\)，\(b\)，有 \(a\mid b\implies \lambda(a)\mid \lambda(b)\)

  2. 令 \(n\) 的唯一分解式为 \(n=\prod_{i=1}^k p_i^{r_i}\)，则

    \[ \lambda(n)=\left[\lambda\left(p_1^{r_1}\right),\lambda\left(p_2^{r_2}\right),\dots,\lambda\left(p_k^{r_k}\right)\right] \]

    由 中国剩余定理 和 Carmichael 定理易证。

    进而有：

    1. 对任意正整数 \(a\)，\(b\)，有 \(\lambda([a,b])=[\lambda(a),\lambda(b)]\)

Carmichael 数

对于合数 \(n\)，如果对于所有正整数 \(a\)，\(a\) 和 \(n\) 互素，都有同余式 \(a^{n-1} \equiv 1 \pmod n\) 成立，则合数 \(n\) 为 Carmichael 数（卡迈克尔数，OEIS:A002997）。

比如 \(561 = 3 \times 11 \times 17\) 就是一个 Carmichael 数，同时也是最小的 Carmichael 数。

我们可以用如下方法判断合数 \(n\) 是否为 Carmichael 数：

Korselt 判别法[^korselt1899probleme]

合数 \(n\) 是 Carmichael 数当且仅当 \(n\) 无平方因子且对 \(n\) 的任意质因子 \(p\) 均有 \(p-1 \mid n-1\).

上述判别法可简化为：

Carmichael 数判别法

合数 \(n\) 是 Carmichael 数当且仅当 \(\lambda(n)\mid n-1\)，其中 \(\lambda(n)\) 为 Carmichael 函数。

Carmichael 数有如下性质：

  1. Carmichael 数无平方因子且至少有 \(3\) 个不同的质因子。

  2. 设 \(C(n)\) 为小于 \(n\) 的 Carmichael 数个数，则：

    1. （Alford, Granville, Pomerance. 1994[^alford1994infinitely]）\(C(n)>n^{2/7}\)。

      由此可知 Carmichael 数有无限多个。

    2. （Erdős. 1956[^erdos1956pseudoprimes]）$C(n)