02.质数基础

title: 02. 质数基础 tags: zk basic prime numbers WTF zk教程第2讲：质数基础 欢迎来到 WTF zk 教程的第2讲！在这一讲中，我们将探讨质数的基础知识。质数在密码学中扮演着关键角色，理解它们对于学习零知识证明至关重要。 质数的定义 质数（prime numbers）也称素数，定义如下：对于一个大于1的自然数，如果它不能被除了 $1$ 和它本身之外的自然数整除，那么它就是质数。 2、3、5、7都是质数，因为它们只能被1和本身整除。另外，除了2以外的偶数均不是质数，因为它们除了1和本身之外，还可以被2整除。 质数的性质 质数是所有自然数的基本单元，数论的算术基本定理（Fundamental Theorem of Arithmetic）告诉我们： 任何大于1的自然数都可以分解为一系列质数的乘积，而且在不考虑质数次序的情况下，这个分解是唯一的。 例如： $$ 84 = 2^2 \times 3 \times 7 $$ 这里，2、3、7都是质数，而且这个分解是唯一的。 素数定理：不超过N的素数的数目大约是 $N/\ln{N}$，且素数有无限多个。 ...