Skip to content

Latest commit

 

History

History
98 lines (61 loc) · 4.58 KB

readme.md

File metadata and controls

98 lines (61 loc) · 4.58 KB
title tags
02. 质数基础
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的自然数都可以分解为一系列质数的乘积,而且在不考虑质数次序的情况下,这个分解是唯一的。

例如:

$$ 84 = 2^2 \times 3 \times 7 $$

这里,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]

随机算法

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

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

6. 总结

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