为什么自然数中存在无穷多个素数

廖雪峰
资深软件开发工程师，业余马拉松选手。

素数（又称质数）是自然数中的“基本数”，但是找出自然数的素数却是无公式可循的。自然数中是否存在无穷多个素数呢？答案是肯定的。伟大的数学家欧几里得在两千多年前就给出了极其简洁的证明。以下是欧几里得的证明：

证明：自然数中存在无穷多个素数。

为了证明该命题，我们需要一个预备定理：

如果A，B都是x的倍数，且A > B，则A - B也是x的倍数。

证明很简单：设A = a * x, B = b * x, 则A - B = a * x - b * x = (a - b) * x，因此A - B是x的倍数。

欧几里得运用反证法巧妙地证明了素数的无穷性。

我们首先假定自然数中只存在有限个素数，则我们一定可以把他们都找出来，不妨用集合(A, B, C, ..., Z)表示。

考察所有素数的乘积x ＝ A * B * C * ... * Z：

x一定是合数，且x比任何一个素数都要大。

再考察x+1，因为x+1比x大，x比任何一个素数都要大，则x+1一定也是和数，否则我们就在找出所有素数的基础上又发现了一个更大的素数，与假设冲突。

由于x+1是合数，那么我们就一定能对其分解质因数，假设分解出某个质因数为C，则C也是x的质因数，因为x是所有素数之积，故x包含质因数C。

考察x+1和x之差：(x + 1) - x = 1，根据预备定理，x+1和x都是C的倍数，所以(x + 1) - x = 1也是C的倍数，但这是不可能的，因为最小的素数是2，1不可能是任何素数的倍数。

故命题不成立。

所以自然数中存在无穷多个素数。

由于自然数中存在无穷多个素数，所以寻找已知的最大的素数就成了全世界数学爱好者的乐趣。现在，借助计算机的威力，可以瞬间找出一亿以内的素数。

研究素数有什么实际的应用价值呢？两千年来，研究数论的数学家一直沉醉于研究本身，他们积累了大量的理论基础，随着近代科学的发展，越来越多的领域需要应用数论的知识。一个典型的领域便是密码学。

传统的密码学使用同一个密钥加密和解密，密钥本身的传输存在很大的问题，直到非对称加密算法的出现，使得我们可以用一个公钥加密，再通过一个私钥解密，RSA算法就是一个典型的非对称加密。

RSA算法的核心思想是基于分解质因数。可以很容易地选择两个非常大的素数并得到它们的乘积，反过来，给出一个非常大的合数，要分解质因数则是非常困难的，必须使用穷举算法。

维基百科给出的RSA算法简介如下：

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：

随意选择两个大的质数p和q，p不等于q，计算N=pq。
根据欧拉函数，不大于N且与N互质的整数个数为(p-1)(q-1)
选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)
用以下这个公式计算d：d × e ≡ 1 (mod (p-1)(q-1))
将p和q的记录销毁。

(N,e)是公钥，(N,d)是私钥。(N,d)是秘密的。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。

下面我们用Python编写一个最简单的RSA加密算法。

#!/usr/bin/env python

__author__ = 'Michael Liao (askxuefeng@gmail.com)'

'''
simplersa.py - a simple RSA encryption demo.
'''

def generate_keys(p, q):
    numbers = (11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
    N = p * q
    C = (p-1) * (q-1)
    e = 0
    for n in numbers:
        if n < C and C % n > 0:
            e = n
            break
    if e==0:
        raise StandardError('e not found')
    # find d: e * d % C == 1
    d = 0
    for n in range(2, C):
        if (e * n) % C == 1:
            d = n
            break
    if d==0:
        raise StandardError('d not found')
    return ((N, e), (N, d))

def encrypt(m, key):
    C, x = key
    return (m ** x) % C

decrypt = encrypt

if __name__ == '__main__':
    pub, pri = generate_keys(47, 79)
    L = range(20, 30)
    C = map(lambda x: encrypt(x, pub), L)
    D = map(lambda x: decrypt(x, pri), C)
    print 'keys:', pub, pri
    print 'message:', L
    print 'encrypt:', C
    print 'decrypt:', D

我们选择素数47, 79，然后计算出密钥(3713, 11) (3713, 1631)，程序输出如下：

keys: (3713, 11) (3713, 1631)
message: [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
encrypt: [406L, 3622L, 3168L, 134L, 3532L, 263L, 1313L, 2743L, 2603L, 1025L]
decrypt: [20L, 21L, 22L, 23L, 24L, 25L, 26L, 27L, 28L, 29L]

可以看到，输入序列[20, 21, ... , 29]用公钥加密后再用私钥解密得到原始序列（加L是因为Python在运算中将整数扩展为长整数了）。

无需担心RSA专利，该专利已于2000年9月过期。

如果你准备用其他语言实现上述RSA算法，需要注意的是，Python的整数是不限制大小的，所以计算乘法不会有问题，而很多语言限制了整数的范围（32位或64位），计算结果如果超出范围高位会被直接截掉。例如，用Java时就必须用BigDecimal而不是long计算。

由于有了RSA等非常安全的非对称加密算法，今天网上银行、电子商务才能迅速发展。我们在享受数字化时代的今天，必须感谢过去一代又一代的数学家为人类科学奠定的坚实的基础。

Python yield使用浅析

快速排序算法

Comments

Loading comments...