跳到主要内容

WTF zk教程第2讲：质数基础

欢迎来到 WTF zk 教程的第2讲！在这一讲中，我们将探讨质数的基础知识。质数在密码学中扮演着关键角色，理解它们对于学习零知识证明至关重要。

1. 质数的定义​

质数（prime numbers）也称素数，定义如下：对于一个大于1的自然数，如果它不能被除了 11 和它本身之外的自然数整除，那么它就是质数。

2、3、5、7都是质数，因为它们只能被1和本身整除。另外，除了2以外的偶数均不是质数，因为它们除了1和本身之外，还可以被2整除。

2. 质数的性质​

质数是所有自然数的基本单元，数论的算术基本定理（Fundamental Theorem of Arithmetic）告诉我们：

任何大于1的自然数都可以分解为一系列质数的乘积，而且在不考虑质数次序的情况下，这个分解是唯一的。

例如：

84=22×3×784 = 2^2 \times 3 \times 7

这里，2、3、7都是质数，而且这个分解是唯一的。

素数定理：不超过N的素数的数目大约是 N/ln⁡NN/\ln{N}，且素数有无限多个。

Proof:

欧几里得证明法

  1. 假设有限个质数： 首先，假设存在有限个质数，将它们记为 p1,p2,…,pnp_1, p_2, \ldots, p_n。

  2. 构造新数： 考虑新的数 N=p1×p2×…×pn+1N = p_1 \times p_2 \times \ldots \times p_n + 1，即把所有已知质数相乘得到的数再加上 1。

  3. 新数的性质： 数 NN 显然是质数，因为它不是任何已知质数的倍数，因为除以任何一个已知质数的商都有余数 1。

  4. 矛盾： 因此，这就导致了矛盾，因为如果 NN 不是质数，那么它必定有一个质因数，但这个质因数要么是已知的质数，要么是不同于已知质数的新质数。

  5. 结论： 无论如何，都会导致与一开始假设的有限个质数矛盾。因此，最初的假设是错误的，质数的数量必须是无穷多的。

3. 质数与合数​

我们可以把自然数分为质数和合数。合数与质数相对：对于一个大于1的自然数，除了1和它本身之外，还有其他正因数，那么它就是合数。例如，4、6、8、9都是合数。

4. 寻找质数​

寻找质数是数论中的一项重要任务，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式（表示一种能够仅产生素数的公式），到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。 素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者则反之。

确定性算法​

最常用的方法是埃拉托斯特尼筛法（Sieve of Eratosthenes）。它的逻辑非常简单：先确定一个要搜寻的范围，然后把从 00 到 n\sqrt n 之间的所有质数的倍数剔除掉，剩下的就是范围内的所有素数。

我们可以用python实现这个方法：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [x for x in range(n + 1) if primes[x]]

# 示例：找出小于等于20的所有质数
limit = 20
prime_numbers = sieve_of_eratosthenes(limit)
print(f'小于等于{limit}的质数: {prime_numbers}')
# 小于等于20的质数: [2, 3, 5, 7, 11, 13, 17, 19]

随机算法​

5. 质数在密码学中的应用​

质数在密码学领域扮演着重要的角色，特别是在公钥密码学中。举个例子，RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它使用了大质数的乘积作为公钥和私钥的一部分：计算质数的乘积很简单，但是将大合数分解为质因数非常困难，这保证了RSA加密算法的安全性。

6. 总结​

在这一讲中，我们学习了质数的基础知识，包括定义、性质以及寻找质数的方法。质数在数学和密码学中都有着重要的应用，为我们理解零知识证明奠定了基础。