| title | tags | |||
|---|---|---|---|---|
02. 质数基础 |
|
欢迎来到 WTF zk 教程的第2讲！在这一讲中，我们将探讨质数的基础知识。质数在密码学中扮演着关键角色，理解它们对于学习零知识证明至关重要。
质数（prime numbers）也称素数，定义如下：对于一个大于1的自然数，如果它不能被除了
2、3、5、7都是质数，因为它们只能被1和本身整除。另外，除了2以外的偶数均不是质数，因为它们除了1和本身之外，还可以被2整除。
质数是所有自然数的基本单元，数论的算术基本定理（Fundamental Theorem of Arithmetic）告诉我们：
任何大于1的自然数都可以分解为一系列质数的乘积，而且在不考虑质数次序的情况下，这个分解是唯一的。
例如：
这里，2、3、7都是质数，而且这个分解是唯一的。
素数定理：不超过N的素数的数目大约是
Proof:
欧几里得证明法
-
假设有限个质数： 首先，假设存在有限个质数，将它们记为
$p_1, p_2, \ldots, p_n$ 。 -
构造新数： 考虑新的数
$N = p_1 \times p_2 \times \ldots \times p_n + 1$ ，即把所有已知质数相乘得到的数再加上 1。 -
新数的性质： 数
$N$ 显然是质数，因为它不是任何已知质数的倍数，因为除以任何一个已知质数的商都有余数 1。 -
矛盾： 因此，这就导致了矛盾，因为如果
$N$ 不是质数，那么它必定有一个质因数，但这个质因数要么是已知的质数，要么是不同于已知质数的新质数。 -
结论： 无论如何，都会导致与一开始假设的有限个质数矛盾。因此，最初的假设是错误的，质数的数量必须是无穷多的。
我们可以把自然数分为质数和合数。合数与质数相对：对于一个大于1的自然数，除了1和它本身之外，还有其他正因数，那么它就是合数。例如，4、6、8、9都是合数。
寻找质数是数论中的一项重要任务，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式（表示一种能够仅产生素数的公式），到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。 素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者则反之。
最常用的方法是埃拉托斯特尼筛法（Sieve of Eratosthenes）。它的逻辑非常简单：先确定一个要搜寻的范围，然后把从
我们可以用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]质数在密码学领域扮演着重要的角色，特别是在公钥密码学中。举个例子，RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，它使用了大质数的乘积作为公钥和私钥的一部分：计算质数的乘积很简单，但是将大合数分解为质因数非常困难，这保证了RSA加密算法的安全性。
在这一讲中，我们学习了质数的基础知识，包括定义、性质以及寻找质数的方法。质数在数学和密码学中都有着重要的应用，为我们理解零知识证明奠定了基础。