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 参考