质数之美

1 质数是什么？

「质数」prime number 又称素数，是定义在大于 1 的自然数中，除了 1 和本身以外不存在其他因数的数。更简单的说，在大于 1 的整数中，那些除了能被 1 和本身整除外，不能被其他数整除的数。

比如 10 以内的质数有 2、3、5、7。由于 4 有额外的因子 2，6 有额外的因子 2 和 3，8 有额外的因子 2 和 4，9 有额外的因子 3，因此它们都不是质数。这些数有另外一个称呼叫做「合数」，它与质数是相对的，是定义在大于 1 的自然数中，除了 1 和本身以外还存在其他因数的数。

可以用一个公式来描述它们之间的关系：正整数 = 0 + 1 + 质数 + 合数，其中 0、1 既不是质数也不是合数，这点很容易被弄混。

2 质数有啥用？

好不容易弄懂了啥是质数，那质数有啥用呢？

它的一个主要作用是用于加密，我们先来看一点关于密码学的基础知识。
「对称加密」是一种很常见的加密方式，所谓对称就是加密和解密使用同一个秘钥。

整个对称加密系统的流程大概是：

1. 发送者使用秘钥将文件加密后发送给接受者；
2. 然后通过某种私密渠道把秘钥发送给接受者；
3. 接受者接收到加密文件和秘钥后，使用密钥解密文件。

但是在整个过程中，秘钥的安全性很难得到保障，一旦发送的秘钥被劫持，那么文件就会被解密。

后来人们想到一种更加安全的方法，叫做「非对称加密」。在非对称加密系统中，加密和解密使用不同的密钥：公开的公钥和私有的私钥。公钥的加密的文件使用私钥才能解密，同样私钥的加密的文件使用公钥也才能解密。

好了，要到质数上场了！

给定一个由两个很大的质数 p 和 质数 q 相乘得到的合数 n，将 n 加入到 公钥 的生成中，将 p 和 q 加入到私钥的生成中。对 p 和 q 做严格的保密，那么即使 n 被劫持到也无所谓，毕竟大整数做质因子分解是非常难的，最后会因为找质数过久而无法破解文件。

是不是感觉这个方法有点厉害，这就是鼎鼎有名的 RSA 加密的基本原理！因此，质数也被称为密码学的根基！

当然质数还有一些其他应用，比如在生产耦合齿轮上，将两齿轮齿数设计成质数，这样可以减少两相同齿轮相遇的次数，从而减轻磨损，让齿轮更耐用。

3 如何找到质数？

看完上文你是不是有点疑问，不过这是我故意留下的坑——为什么大整数做质因子分解很难？

先来看如何使用计算机找质数，这里使用 python 代码做演示。

3.1 最基础的方法

使用定义给出的在大于 1 的整数中，那些除了能被 1 和本身整除外，不能被其他数整除的数。

那么我们让一个数去除以从 2 遍历到比自身小 1 的数，如果都不能被整除，就说明它是质数。

from timeit import timeit

def f1():
    max_number = 10000
    prime_number_list = []
    for num in range(2, max_number):
        for n in range(2, num):
            if num % n == 0:
                break
        else:
            prime_number_list.append(num)
    # print(prime_number_list)

# 计算一次运行的时间
t1 = timeit('f1()', 'from __main__ import f1', number=1)
print(f"f1: {t1}")

# 输出
# f1: 0.42162744887173176

3.2 改进方法 1

不知道你有没有发现，在判断整除的时候其实做了很多无用功，每个数字都不能整除大于自己一半以上的数字。那么我们直接把第二个循环的 num 替换成 num/2+1（+1 的原因是 range 的后半部分是开区间，在遍历时只会输出到 num/2）。

from timeit import timeit

def f2():
    max_number = 10000
    prime_number_list = []
    for num in range(2, max_number):
        for n in range(2, num//2+1):
            if num % n == 0:
                break
        else:
            prime_number_list.append(num)
    # print(prime_number_list)

t2 = timeit('f2()', 'from __main__ import f2', number=1)
print(f"f2: {t2}")

# 输出
# f2: 0.20759914070367813

通过执行时间可以看出，相比最原始的方法有两倍左右的提升。

3.3 改进方法 2

虽然上文可以缩减一半，但是仍然有很多无效计算，比如我们判断了 2 是否能被整除以后就不用判断 2 的所有倍数了。也就是说我们可以只判断质数是否能被整除。

from timeit import timeit

def f3():
    max_number = 10000
    prime_number_list = []
    for num in range(2, max_number):
        for n in prime_number_list:
            if num % n == 0:
                break
        else:
            prime_number_list.append(num)
    # print(prime_number_list)

t3 = timeit('f3()', 'from __main__ import f3', number=1)
print(f"f3: {t3}")

# 输出
# f3: 0.050802865996956825

3.4 厄拉多塞法

好了，厄氏大法该你上场了！

西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中，筛选出质数来，这方法被称作厄拉多塞筛法(Sieve of Eeatosthese)。

具体操作：先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

– 源出处不详

from timeit import timeit

def f4():
    max_number = 10000
    prime_bool_list = [1] * max_number
    prime_bool_list[0] = prime_bool_list[1] = 0
    for i in range(2, int(max_number**0.5) +1):
        if prime_bool_list[i] == 1:
            prime_bool_list[i*i:max_number:i] = [0]*len(prime_bool_list[i*i:max_number:i])

    prime_number_list = []
    for j in range(max_number):
        if prime_bool_list[j]:
            prime_number_list.append(j)
    # print(prime_number_list)

t4 = timeit('f4()', 'from __main__ import f4', number=1)
print(f"f4: {t4}")

# 输出
# f4: 0.0010158903896808624

这次有了很明显的提升！

非对称加密算法的公钥和私钥是一对大素数（100 到 200 位十进制数或更大）的函数。我用电脑做了测试生成 10**8 以下的数字需要 25 秒左右。可以想象如果生成出 100 位的数字的素数需要多久，而且还需要其他额外的其他操作。这个时间开销是非常恐怖的，在当前的计算机的速度看来是不可能的。所以这也是 RAS 被广泛使用的原因。

4 参考

• 素数和加密
• 对称加密与非对称加密，以及RSA的原理