MoonMath SNARK 手册

整数( integers 或 whole numbers )指不带小数部分的数字。\( \frac{2}{3} \), \( 1.2 \) 和 \( -1280.006 \) 等数字都不是整数。

在本书中，我们使用 \( \mathbb{Z} \) 作为整数集合的代表：

\[ \mathbb{Z} := \{\ldots, -3,-2,-1,0,1,2,3,\ldots\} \]

如果 \( a\in \mathbb{Z} \) 是一个整数，我们使用 \( |a| \) 表示 \( a \) 的绝对值( absoulte value )。绝对值指 \( a \) 的不考虑符号的非负值，如下：

\[ \begin{equation} |4|= 4 \\ |-4|= 4 \end{equation} \]

我们使用符号 \( \mathbb{N} \) 表示所有正整数，通常称之为自然数( natural numbers )。此外，我们使用 \( \mathbb{N}_{0} \) 表示所有非负整数。上述叙述说明， \( \mathbb{N} \) 不包含 \( 0 \) ，但 \( \mathbb{N}_{0} \) 包含：

\[ \begin{align*} \mathbb{N} := \{1,2,3,\ldots\} & & \mathbb{N}_{0} := \{0,1,2,3,\ldots\} \end{align*} \]

此外，我们使用符号 \( \Bbb{Q} \) 表示有所有有理数(rational numbers)构成的集合。该集合是由所有分数 \( \frac{n}{m} \) 构成的，其中 \( n \in \Bbb{Z} \) 是一个整数且 \( m \in \Bbb{N} \) 是一个自然数。

在集合 \( \Bbb{N}\)、 \( \Bbb{Z}\) 和 \( \Bbb{Q} \) 上定义了加法和乘法的概念。我们大多数人可以在大脑中进行许多整数运算，但随复杂度的增加，在大脑中进行计算变得复杂。我们通常使用Sagemath进行复杂计算(我们会在本书稍后部分定义环和域)：

sage: ZZ # Sage 对整数集合的表示
Integer Ring
sage: NN # Sage 对自然数集合的表示
Non negative integer semiring
sage: QQ # Sage 对有理数集合的表示
Rational Field
sage: ZZ(5)
5
sage: ZZ(5) + ZZ(3)
8
sage: ZZ.random_element(10**6)
455617

我们特别感兴趣的数字集合是素数(prime numbers)。素数指自然数 \( p \in \Bbb{N} \) 在满足 \(p \ge 2\) 条件下，其只能被它本身和 \(1\) 整除。除了 \(2\) 以外的所有素数被称为奇素数(odd prime numbers)。我们使用 \( \Bbb{P} \) 表示所有素数构成的集合，使用 \( \Bbb{P}_{\ge 3}\) 表示奇素数。

素数集合 \( \Bbb{P} \) 是一个无限集合且可以按照数字大小进行排序。这意味着对于任何一个素数 \( p \in \Bbb{P} \) ，都存在另一个素数 \( p' \) 使得\( p < p' \) 。结论是没有最大的素数。将所有素数按大小排序，我们写出：

\[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, \ldots\]

算术基本定理(fundamental theorem of arithmetic)告诉我们，在某种意义上素数是构成其他自然数的基本组件，或者说，每一个自然数都可以通过素数彼此相乘获得。假设 \( n \in \Bbb{N} \) 且 \( n > 1 \) ，存在素数 \( p_1, p_2, \ldots, p_k \in \Bbb{P} \)，那么存在:

\[ n = p_1 \cdot p_2 \cdot \ldots \cdot p_k \ \]

除了因子的顺序，该分解对于任何自然数都是不同。我们称上述分解为 \(n\) 的质因数分解(prime factorization)

示例 1 质因数分解

为了使读者理解质因数分解概念，我们此处给出对数字 \( 504 \in \Bbb{N} \) 的分解。分解方法是使 \(504\) 依次除以从 \(2\) 开始的素数，分解结果如下：

\[504 = 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 7\]

我们可以通过Sage检查此结果，该程序提供了自然数质因数分解算法：

sage: n = NN(504)
sage: factor(n)
2^3 * 3^2 * 7

上述计算揭示了一个重要的结论：计算一个整数的质因数分解在运算上是昂贵的，因为我们必须重复除以所有小于该数的素数，直到所有因子都是素数本身。由此，出现了一个重要的问题：计算自然数质因子分解的速度到底有多快？ 这个问题就是著名的整数因子分解问题(integer factorization problem)。据我们所知，目前仍没有比将待分解的数除以按升序排列的所有素数这一朴素方法更快的分解方法。

在另一方面，计算给定集合的素数的乘积是快速的。我们发现素数相乘与其逆过程，即自然数的质因子分解在计算资源耗费上完全不同。质因子分解问题是单向函数(one-way function)的一个例子。所谓单向函数指一种在某一方向计算简单但逆向计算复杂的可逆函数(nvertible function)。

计算是否可行取决于我们拥有的计算资源。当前自然数的质因子分解没有多项式时间内实现的算法。但是，美国数学家 Peter W. Shor 在 1994 年开发了一种在量子计算机上使用的可在多项式时间内完成的自然数质因子分解算法¹。因此，当前依赖于自然数质因子分解的加密算法(如 RSA 算法)将在量子计算机出现后变得不安全。

练习 1. 计算 -123, 27 和 0 的绝对值。

练习 2. 对 30030 进行质因数分解并使用sage进行检查

练习 3. 已知如下方程：

\[ 4 \cdot x + 21 = 5\]

计算符合以下假定的 \(x\) 的所有解：

1. 方程定义在自然数集上
2. 方程定义在整数集上

练习 4. 已知以下方程：

\[2 x^3 - x^2 - 2 x = - 1\]

计算符合以下假设的所有解：

1. 方程定义在自然数集上
2. 方程定义在整数集上
3. 方程定义在有理数集上