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

廖雪峰 / 编程 / ... / Reads: 5246

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

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

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

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

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

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

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

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

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

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

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

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

故命题不成立。

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

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

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

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

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

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

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

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

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

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

__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等非常安全的非对称加密算法,今天网上银行、电子商务才能迅速发展。我们在享受数字化时代的今天,必须感谢过去一代又一代的数学家为人类科学奠定的坚实的基础。

Comments

Make a comment

Author: 廖雪峰

Publish at: ...

关于作者

关注公众号不定期领红包:

关注微博获取实时动态: