title: 02. 质数基础
tags:
  - zk
  - basic
  - prime numbers​

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

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

1. 质数的定义

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

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

2. 质数的性质

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

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

例如：

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

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

Proof:

欧几里得证明法

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

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

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

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

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

3. 质数与合数

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

4. 寻找质数

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

确定性算法

• 埃拉托斯特尼筛法

最常用的方法是埃拉托斯特尼筛法（Sieve of Eratosthenes）。它的逻辑非常简单：先确定一个要搜寻的范围，然后把从 0 到 \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]
​

• 卢卡斯-莱默检验法
• AKS素性测试

随机算法

• 费马素性检验
  • 利用费马小定理来测试。
• 米勒-拉宾检验

5. 质因式分解

质因数分解（Prime factorization）是数学中的一种概念，任何一个合数都可以分解为若干个素数的乘积。例如，数字12可以分解为2 x 2 x 3。
质因式分解仅针对合数，求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。

6. 最大公因数和最小公倍数

最大公因数（highest common factor，hcf）也称最大公约数（greatest common divisor，gcd）是数学词汇，指能够整除多个非零整数的最大正整数。若多个正整数记为 ` (a_1,a_2, …… , a_n) `，则他们的最大公因数可以表示为 `gcd(a_1,a_2, …… , a_n)` 。例如8和12的最大公因数为4，记为`gcd(8,12) = 4`。此外，最大公因数至少为1。常采用列举法、素因数分解、短除法进行求解。

最小公倍数（least common multiple，lcm）表示若有一个数`X`，可以被另外两个数`A`、`B`整除，且`X`同时大于或等于`A`和`B`，则`X`为`A`和`B`的公倍数。`A`和`B`的公倍数有无限个，而所有正的公倍数中，最小的公倍数就叫做最小公倍数。不失一般性，`n`整数`a_1`,`a_2`,⋯,`a_n`的最小公倍数一般参照英文记法记作`lcm⁡(a_1,a_2,……, a_n)`。常采用列举法、短除法进行求解。

上述二者的关系为 `gcd(a,b) * lcm(a,b) = |ab| `

7. 质数在密码学中的应用

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

8. 总结

在这一讲中，我们学习了质数的基础知识，包括定义、性质以及寻找质数的方法，以及质因式分解、最小公倍数和最大公约数的简单介绍。质数在数学和密码学中都有着重要的应用，为我们理解零知识证明奠定了基础。