算法题密码学质数判定的算法你能想到几种？（上）

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动。本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

大家好，我是披着狼皮的🐏。今天给大家介绍几个用于素性测试（primality test）的确定性算法，适用于判断给定整数 n 是否为质数。注意，这里不考虑 0、1 等其他不是质数也不是合数的数，在实际应用上大家记得自己加 if 判断。

试除法（Trial Division）+ 优化

最直接的方法，遍历从 2 到 n-1 的所有数字，并检查其是否能整除 n，找到了便返回 False。

def is_prime(n):
    for x in range(2, n):
        if n % x == 0:
            return False
    return True
复制代码

优化 1

如果 n 是合数，那么必然存在两个约数

p1​ 和

p2​，且

p1​≤n​≤p2​。简单来说，因数是一对一对出现的，而

n​ 就是那个“对称轴”，我们不必把所有小于 n-1 的数都试一次，到 x == sqrt(n) 就可以停下了。

from math import isqrt  // Python 版本 >= 3.8

def is_prime(n):
    for x in range(2, isqrt(n) + 1):
        if n % x == 0:
            return False
    return True
复制代码

优化 2

如果 n 能被一个偶数整除，那么它一定能被 2 整除，合理吧？因此，我们可以跳过除了 2 以外的所有偶数。

from math import isqrt  // Python 版本 >= 3.8

def is_prime(n):
    if n == 2:
        return True
    elif n % 2 == 0:
        return False
        
    for x in range(3, isqrt(n) + 1, 2):
        if n % x == 0:
            return False
    return True
复制代码

优化 3

除了 2 与 3，所有质数一定能表达成 6k+1 或 6k+5 的形式，k 为一个正整数。

（质数一定能表达成这个形式，但能表达成这个形式的数不一定是质数。）

论证

• 6k 能被 6 整除，不是质数;
• 6k+2 和 6k+4 能被 2 整除，不是质数；
• 6k+3 能被 3 整除，不是质数；

那么就只剩下 6k+1 和 6k+5 有可能质数了。

注：6k+5 也可以写成 6k-1，因为

5≡−1(mod6)。

对于有可能是质数的数，我们还得用试除法，范围还能再进一步的缩小 —— 在能表示成 6k+1 或 6k+5 的数中寻找因数就可以了。

为什么？

所有的合数都能分解成质数，所以 n 只需要与可能是质数的数（即 6k+1 或 6k+5）判断就可以了。

def is_prime3(n):
    if n == 2 or n == 3:
        return True
    # 不能表达成 6k+1 或 6k+5 的数一定不是质数
    if n % 6 != 1 and n % 6 != 5:
        return False
    # 进一步的判断
    for x in range(5, int(sqrt(n)) + 1, 6):
        if n % x == 0 or n % (x + 2) == 0:
            return False
    return True
复制代码

威尔逊定理（Wilson's Theorem）

数论四大定理之一：

当且仅当

$n$

n 是质数时：

$$(n - 1)! \equiv -1 \pmod n$$

(n−1)!≡−1(modn)

简单来说，如果 n 是质数，则 n-1 的阶乘加 1 除以 n 的余数为 0。

论证

{1,2,…,n−1} 里的每个元素

a 都会有一个模

n 的倒数

a∗∈{1,2,…,n−1}，即

aa∗≡1(modn)。（这里就不论证这句话了……）

若

a=a∗，

只有 1 和

n−1 的模倒数是自身，

{2,3,…,n−2} 内的每个数都有一个独特的模倒数。两两配对，那么我们就有几个模

n 等于

1 的对。

证明完毕，上代码。

from math import factorial

def is_prime(n):
    return (factorial(n - 1) + 1) % n == 0
复制代码

AKS素性测试（Agrawal–Kayal–Saxena Primality Test）

$n$

n 是质数当且仅当：

$n$

n 能整除

$(x + 1)^n - (x^n + 1)$

(x+1)n−(xn+1) 的展开式的所有系数。

论证

利用二项式定理（binomial theorem），展开原式：

可以看得出，

xn+1 这项去掉了

(x+1)n 展开式的首尾项。那么上方的定理也可以这么表达：

$n$

n 是质数当且仅当：

$n$

n 能整除

$\binom{n}{r}, r=1,2,\dots,n-2,n-1$

(rn​),r=1,2,…,n−2,n−1。

让

N=(rn​)，

显然

n 能整除

n!，那么

n 就能整除

N(n−r)!r!。如果一个数能整除一个几个数的积，那么它一定至少能整除它们之一。由于

p 不能整除

• 
  $(p-r)!$

  (p−r)!，因为

  $(p-k)<p$

  (p−k)<p 且

  $p$

  p 是质数；

• 
  $r!$

  r!，因为

  $k<p$

  k<p 且

  $p$

  p 是质数；

那么它一定能整除

N。

这个定理对于质数成立。

当

n 为合数时，

让

c 为

n 的因数，

n=cd。显而易见，

c,d∈{1,2,…,n−1}。

如果上方的式子可以被

n 整除，那么必然会有一个正整数

k 使得

(cn​)=kn。

让我们看看

k 是不是整数。

根据威尔逊定理，

k 不可能是整数。这个定理对于合数不成立。

论证完毕，代码如下：

from math import comb  // Python 版本 >= 3.8

def is_prime(n):
    for r in range(1, n):  // (n-1) + 1 = n
        if comb(n, r) % n != 0:
            return False
    return True
复制代码

优化

$$\binom{n}{k}=\binom{n}{n-k}$$

(kn​)=(n−kn​)

(1n​)=(n−1n​)，

(2n​)=(n−2n​)，以此类推。因此，range 的范围可以缩小一半。

from math import comb  // Python 版本 >= 3.8

def is_prime(n):
    for r in range(1, n // 2 + 1):
        if comb(n, r) % n != 0:
            return False
    return True
复制代码

赶紧点赞，不然你下次面试遇到的题目就是这题。

下篇文章将给大家介绍几个效率更高的概率性算法（probabilistic test）。就这样，拜拜。