开发者的数学生存工具包

介绍

当处理密码学应用时，你需要理解一些底层的数学知识（至少，如果你想正确地做事）。例如，RSA密码系统（它是最早的方法之一，也是被最广泛采用的方法，直到它被更好的方法，例如基于椭圆曲线的方法所取代）通过使用公钥 $e$ 加密消息 $M$（表示为范围 $1, 2, 3, ... n-1$ 中的一个数字，其中 $n$ 是一个大的合数）来工作，执行以下计算：

$E(M) = M^e \pmod{n}$

如果你想解密消息，你需要私钥 $d$ 并执行：

$M = E(M)^d \pmod{n}$

现在，所有这些计算意味着什么，为什么RSA有效？诀窍在于Euler定理以及 $d$ 和 $e$ 通过 $d \times e \equiv 1 \pmod{\phi(n)}$ 相关联，因此当我们先应用 $e$ 然后应用 $d$ 时，“它与”将消息提升到1“相同”。当然，你可能不理解很多符号，但一些关键概念实际上非常简单。它们只是被所有的数学术语笼罩在迷雾中，这使得对那些了解其含义的人来说很容易陈述，但对于不熟悉它们的人来说，这可能相当具有挑战性。

另一个经常出现的问题是找到素数（通常是非常大的数字，有100位或更多位数）或确定某个数字是素数还是合数。例如，在zk-SNARKs（零知识简洁非交互式知识论证）中，关键要素之一是执行（类似于）同态加密的能力。这在实践中是通过在两组数字上配对两个椭圆曲线来实现的，其中元素的总数是素数 $m$，满足 $m = k \times 2^N + 1$，其中 $k$ 是一个奇数，$N$ 是一个大数。我们说 $m$ 具有大的2-adic性，并以紧凑形式表示为 $m - 1 \equiv 0 \pmod{2^N}$ 或 $2^N \mid m - 1$（这被读作 $2^N$ 整除 $m - 1$）。在RSA中，数字 $n$ 是两个大素数的乘积，$p$ 和 $q$，即 $n = p \times q$。如果你选择两个非常接近的素数，你的密码系统很容易使用 费马分解法 来破解。

因此，我们看到我们需要理解其背后的数学原理，才能知道我们可以应用哪些技巧来轻松解决问题，如何破解密码系统或我们自己系统的局限性或弱点是什么。我们将解释数论和抽象代数的许多关键思想，以帮助你建立处理密码学所需的基础。

自然数、整数、有理数、实数和复数。

自然数是那些我们用来计算物体的数字，也是我们最早在学校学到的东西：$1, 2, 3, 4...$ 是自然数。这些数字的集合通常用 $\mathbb{N}$ 表示。像 $-1$, $-2$, $0$ 等数字是整数的一部分；这个集合用 $\mathbb{Z}$ 表示（来自德语，zahlen，数字）。可以表示为两个整数 $a$ 和 $b$（其中 $b \neq 0$）之比的数字称为有理数，$r = a/b$，该集合用 $\mathbb{Q}$ 表示。有理数可以通过添加无理数（如 $\pi$ 和 $e$）来扩展，以形成实数集 $\mathbb{R}$。你可能也听说过复数 $\mathbb{C}$，它包含诸如 $i$ 这样的数字，其中 $i^2 = -1$。

在整数中，我们有四个基本运算：加法、减法、乘法和除法。让我们首先关注加法和减法：

如果我们在 $\mathbb{Z}$ 中取 $a$ 和 $b$，那么 $c = a + b$ 和 $d = a - b$ 也在 $\mathbb{Z}$ 中。我们说加法和减法是集合上的封闭运算。

2. 如果我们将 $0$ 加到任何数字 $a$，我们得到 $a$，即 $a + 0 = 0 + a = a$。$0$ 是 $\mathbb{Z}$ 的加法单位元。

3. 我们知道，如果我们对 $a$ 和 $-a$ 求和，我们得到 $0$。也就是说，$a + (-a) = a - a = 0$，所以减法与加 $-a$ 相同。$-a$ 是 $a$ 的加法逆元。

4. 给定 $a$、$b$ 和 $c$，$a + (b + c) = (a + b) + c$。这是结合律。

群

上述属性表明，整数集 $\mathbb{Z}$ 与 .+..+. 运算一起形成一个代数群。其他集合与不同的运算组合，具有相同的数学结构。例如，带乘法的正有理数具有群结构。$n \times n$ 可逆矩阵在矩阵乘法下形成一个群。向量空间 在加法下形成一个群（如果你取任意两个向量 $u$ 和 $v$，它们的和总是在向量空间中）。椭圆曲线密码学利用了在椭圆曲线上添加两个点总是会得到曲线上的第三个点这一事实。群出现在数学、物理和化学的许多应用中。我们可以将群定义为一个（非空）集合 $G$ 加上一个二元运算（即，一个从集合 $G$ 中取两个输入元素的运算）$\times$，满足：

G1. 如果 $a$ 和 $b$ 在集合中，那么 $a \times b = c$ 也在集合中。

G2. 存在一个单位元 $e$，使得 $e \times a = a \times e = a$。

G3. 如果 $a$ 在集合中，则集合中存在某个 $b$，使得 $a \times b = e$。我们说 $b$ 是 $a$ 的逆元，并将其表示为 $b = a^{-1}$。

G4. 对于 $a, b, c$，$a \times (b \times c) = (a \times b) \times c$。

群中的表示法有时令人困惑，人们可以自由地使用加法 (+) 或乘法 ($\times$) 表示法，并将它们的单位元称为 $0$ 或 $1$。这无关紧要，因为二元运算可能非常奇怪（例如椭圆曲线上的“加法”）。如果你从更抽象地看待事物开始，它会很快得到回报。

练习：取 $n \times n$ 矩阵的空间，使其行列式非零（即可逆矩阵的集合）。证明这是一个群。

我们还在学校学到，整数中的加法是可交换的（即，因子的顺序不会改变结果 $a + b = b + a$）。然而，并非所有群都满足此条件。对于那些特权群，我们称为阿贝尔（或交换）群。阿贝尔群有一个附加条件：

G5. 如果 $a$，$b$ 在 $G$ 中，$a \times b = b \times a$。

当我们查看整数中的乘法和除法时，我们看到存在一些问题。

1. 如果 $a$ 和 $b$ 是整数，$a \times b = c$ 也是一个整数。该运算在乘法下是封闭的。
2. 如果我们将任何数字乘以 $1$，我们得到相同的数字。$1$ 是乘法单位元。
3. 给定 $a, b, c$，我们有 $a \times (b \times c) = (a \times b) \times c$。
4. 给定 $a$、$b$ 和 $c$，$a \times (b + c) = a \times b + a \times c$ 并且 $(b + c) \times a = b \times a + c \times a$。这是分配律。
5. 如果 $a$ 和 $b \neq 0$ 是整数，它们的除法 $a/b$ 不一定是整数。例如，$a = 3$ 和 $b = 2$ 导致 $c = 3/2$，这是一个有理数（不是整数）。换句话说，该运算不是封闭的。

环和域

集合 $\mathbb{Z}$ 与加法和乘法一起形成一个环。具有普通加法和乘法的多项式也形成一个环。$n \times n$ 矩阵也在加法和乘法下形成一个环。形式上，环是一个集合 $R$，带有两个运算 $+$ 和 $\times$，使得：

1. R 在 $+$ 下是一个阿贝尔群（即，R 满足群 G1 到 G4 的所有条件，加上交换律 G5）。
2. 存在一个乘法单位元 $e$，使得 $a \times e = e \times a = a$。通常，我们使用 $e = 1$。
3. 乘法是结合的。
4. 我们有关于加法的乘法分配律。

练习：检查 $n \times n$ 矩阵是否通过普通矩阵加法和乘法形成环。

如果我们查看有理数，对于任何非零元素，我们都有一个乘法逆元。例如，$1/5$ 是 $5$ 的乘法逆元，因为 $5 \times 1/5 = 1$。除法现在是一个封闭运算。此外，乘法也是可交换的。$\mathbb{Q}$ 具有普通加法和乘法是域。域的其他示例是 $\mathbb{R}$ 和 $\mathbb{C}$。当集合中的元素数量有限时（例如 $4$，$2^{255} - 19$ 等），该域称为有限域。这些对于密码学非常重要。

数论的一些概念

可除性

我们将从讨论可除性开始。给定两个自然数 $a$ 和 $b$，我们说 $a$ 整除 $b$（并写成 $a \mid b$）如果存在另一个数 $c$，使得 $a \times c = b$。$a$ 被称为 $b$ 的因子。如果 $a$ 不能整除 $b$，我们写成 $a \nmid b$，我们可以写成 $b = q \times a + r$，其中 $r < a$，其中 $q$ 是商，$r$ 是除法的余数。如果 $a$ 整除 $b \times c$，则 $a \mid b$ 或 $a \mid c$。另一个事实是，如果 $a \mid b$ 并且 $a \mid c$，则对于任何数字 $x, y$，$a \mid (x \times b + y \times c)$。

素数

一个数 $p > 1$ 称为素数，如果它唯一的因子是 $1$ 和它本身。否则，这个数是合数。素数的例子有 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...$。算术基本定理 告诉我们，任何数字都可以以唯一的方式（直到排序）表示为素数幂的乘积。例如，$20 = 2^2 \times 5$，$186 = 2 \times 3 \times 31$，$5 = 5$ 等。找到素数对于密码学至关重要。一种简单的方法（但对于大数来说绝不实用）来查看数字 $p$ 是否为素数包括检查它是否可以被小于 $p$ 的所有素数整除。问题是，如果 $p$ 非常大，这可能会非常低效。有一些更好和更快的算法，但我们将在其他时间介绍它们。

练习：找到小于 100 的所有素数。

最大公约数和欧几里得算法

一个重要的概念是最大公约数：给定两个数 $a$ 和 $b$，我们想找到最大的数 $c$，使得 $c \mid a$ 并且 $c \mid b$。我们将其表示为 $c = \gcd(a, b)$ 或简称为 $c = (a, b)$。例如，$20 = 2^2 \times 5$ 和 $50 = 2 \times 5^2$。这两个数字都可以被 $1, 2, 5, 10$ 整除。$10$ 是除这两个数字的最大数，因此 $\gcd(20, 50) = 10$。如果 $\gcd(a, b) = 1$，则两个数 $a, b$ 称为互质（或互素）。如果 $a$ 和 $b$ 都是素数（且不同），则 $1$ 是唯一的公因子。但是，$8$ 和 $9$ 本身不是素数（$8 = 2^3$ 和 $9 = 3^2$），但它们唯一的公因子是 $1$，因此它们互质。

最大公约数满足以下等式，对于某些 $x$ 和 $y$：

$x \times a + y \times b = \gcd(a, b)$

使用 欧几里得算法 可以非常有效地找到最大公约数，并且使用扩展欧几里得算法也可以以很少的额外成本找到数字 $x$ 和 $y$。

为了理解该算法，让我们看一个例子：假设我们要计算 gcd(2502, 864)。该算法利用余数总是小于除数这一事实，因此我们可以“砍掉”较大的数字；这种砍伐不会影响最大的公约数。

1. 让我们找到 2502/864 的余数，$r_0 = 774$。
2. 让我们找到 864/774 的余数，$r_1 = 90$。
3. 774/90 的余数是 $r_2 = 54$。
4. $r_3 = 36$
5. $r_4 = 18$
6. $r_5 = 0$，因为 $36$ 可以被 $18$ 整除。所以，最大公约数是 $18$。

我们可以从 $864 = 2^5 \times 3^3$ 和 $2502 = 2 \times 3^2 \times 139$ 的分解中看到，$\gcd$ 等于 $2 \times 3^2 = 18$。优点是我们通过几个步骤 (6) 找到了它，我们不必知道分解（对于大数来说，这真的很难找到。事实上，那是RSA密码系统的关键）。

同余和模算术

我们使用计算机面临的一个问题是我们能使用的数字是有限的。此外，在某些情况下，我们对数字本身不感兴趣，而是对它属于某个类或组感兴趣。例如，当我们押注轮盘赌时，我们可以选择结果是偶数还是奇数。如果是偶数，则 $r = 2 \times k$，对于某些 $k \in {0, 1, 2, 3...18}$。如果是奇数，则 $r = 2 \times k + 1$。我们注意到，如果我们想检查奇偶性，我们只需要查看余数，在这种情况下，余数可以取两个值：$0$ 或 $1$。事实上，当我们想检查计算机中的一个数字是否为偶数时，我们会查看最左边的位，并检查它是否为零。对于 $2$ 的情况，我们看到任何数字 $a$ 满足以下条件之一：

$a \equiv 0 \pmod{2}$

$a \equiv 1 \pmod{2}$

我们说 $a$ 与 $0$（或 $1$）模 $2$ 同余。这样，我们将所有数字分成两类：偶数和奇数。对于任何数字 $p > 1$，我们可以做同样的事情，记住余数是 $0 \leq r \leq p - 1$。这也可以看作是 $a \equiv r \pmod{p}$ 作为 $p \mid a - r$ 或 $a = k \times p + r$。这个符号是高斯发明的，对于研究许多复杂的问题非常有效。我们可以执行通常的运算，例如加法和乘法，但我们必须小心事物的运作方式，因为结果总是必须在 $0 \leq r \leq p - 1$ 的范围内（作为旁注，你可以选择不同的范围，例如 $-2, -1, 0, 1, 2, p-3$，但这可能会令人困惑，我们最好坚持我们的第一个选择）。

在求和的情况下，我们可以像普通数字一样添加它们，如果结果超过 $p$，则取余数。例如，让我们取 $p = 7$，所以我们拥有的元素是 $0, 1, 2, 3, 4, 5, 6$。首先，我们看到 $0$ 是集合的一个元素，并且将其添加到任何数字都不会改变结果。如果我们添加 $2$ 和 $3$，结果是 $5$。如果我们添加 $5$ 和 $4$，我们得到 $9$，但是

$4 + 5 = 9 \equiv 2 \pmod{7}$

$2$ 只是 $9$ 除以 $7$ 的余数。我们看到结果停留在原始集合中。当我们添加 $4$ 和 $3$ 时会发生什么？

$4 + 3 = 7 \equiv 0 \pmod{7}$

我们得到 $0$！那是因为 $7$ 可以被自身整除，余数是 $0$。我们看到 $4$ 在这种算术下是 $3$ 的加法逆元。同样，$1$ 和 $6$ 互为逆元，$2$ 和 $5$ 互为逆元。我们可以认识到集合 $0, 1, 2, 3, 4, 5, 6$ 与模 $7$ 完成的和是一个阿贝尔群。减法可以简单地定义为添加数字的逆元，或者只是执行普通减法，然后取结果模 $p$。

使用乘法，我们得到类似的东西。例如，

$4 \times 5 = 20 \equiv 6 \pmod{7}$。

取模运算确保我们始终停留在集合内。我们还看到 $1$ 作为乘法单位元，因为任何数字乘以 $1$ 保持不变。让我们看看 $6 \times 6$ 会发生什么：

$6 \times 6 = 36 \equiv 1 \pmod{7}$。

我们将 $6$ 乘以自身并得到 $1$！我们之前谈到除法 $a/b$ 可以重新表示为 $a \times b^{-1}$，其中 $b \times b^{-1} = 1 = b^{-1} \times b$。我们看到 $6$ 是它自身用乘法模 $p$ 的乘法逆元。我们还可以看到：

$3 \times 5 = 15 \equiv 1 \pmod{7}$

$2 \times 4 = 8 \equiv 1 \pmod{7}$

所以，$3 = 5^{-1}$ 和 $2 = 4^{-1}$！这听起来很奇怪，但我们必须记住我们正在使用同余。我们可以通过改写来理解这个的确切含义。让我们以 $6$ 和 $6$ 为例。有两个数字 $a = q_1 \times 7 + 6$ 和 $b = q_2 \times 7 + 6$（因为这就是同余的含义）。让我们取乘积 $a \times b$：

$a \times b = (q_1 \times 7 + 6) \times (q_2 \times 7 + 6)$

让我们应用分配律：

$a \times b = q_1 \times q_2 \times 7^2 + 6 \times 7 \times (q_1 + q_2) + 36$

让我们进一步拆分 $36 = 1 + 35 = 1 + 7 \times 5$，并将 $7$ 作为公因子重新组合：

$a \times b = 7 \times (q_1 \times q_2 \times 7 + 6 \times (q_1 + q_2) + 5) + 1$

第一项可以被 $7$ 整除，所以它与 $0$ 同余。或者，如果我们从 $a \times b$ 中减去 $1$，我们会看到它可以被 $7$ 整除（因为它是 $7$ 和一个整数的乘积）。

我们可以看到，如果 $p$ 是素数，那么集合 $0, 1, 2, ... p - 1$ 具有加法和乘法模 $p$ 是一个有限域。

练习：证明这确实是一个有限域。

Z/nZ 作为群。循环群。

你经常会看到这些集合表示为 $\mathbb{Z}/p\mathbb{Z}$。如果我们想在 $\mathbb{Z}/n\mathbb{Z}$ 中使用非素数的 $n$，我们必须非常小心（在这种情况下，它也不是有限域）。例如，让我们尝试解决这个方程：

$(x + 2) \times (x + 1) \equiv 0 \pmod{12}$

我们可以使用我们的数学知识，当两个数的乘积为 $0$ 时，至少其中一个是 $0$（剧透警告：这会出错）：

1. $(x + 2) \equiv 0 \pmod{12}$。如果 $x = 10$，则 $x + 2 = 12 \equiv 0$，因为它可被 12 整除。
2. $(x + 1) \equiv 0 \pmod{12}$。如果 $x = 11$，则 $x + 1 = 12 \equiv 0$，因为它可被 12 整除。

现在让我们选择 $2$，看看会发生什么：

$(2 + 2) \times (2 + 1) = 12 \equiv 0 \pmod{12}$。

所以 $2$ 是方程的解，但是 $2 + 2 \equiv 4 \not\equiv 0$ 并且 $2 + 1 \equiv 3 \not\equiv 0$。发生这种情况是因为 $12$ 不是素数。

事实上，给定 $a$ 和 $n$，如果且仅当 $\gcd(a, n) = 1$，即 $a$ 和 $n$ 互质，则 $a$ 具有逆元（模 $n$）。在前面的示例中，$3$ 与 $12$ 不互质（它们有 $3$ 作为公因子）。

如果集合不太大，我们可以通过反复试验找到逆元。但是，如果我们有一些可以帮助我们计算逆元以及如何计算数字的（整数）幂的结果，那就太好了。

让我们关注一个素数 $p$，并取集合 $(\mathbb{Z}/p\mathbb{Z})^{\star}$ 的所有非零元素。让我们固定 $p = 7$，所以 $(\mathbb{Z}/p\mathbb{Z})^{\star} = {1, 2, 3, 4, 5, 6}$，让我们关注集合上的乘法。我们可以定义幂 $a^n = a \times a \times a \times ... \times a$。显然，$1$ 并不有趣，因为 $1^n = 1$，所以让我们取 $5$：

$5^1 \equiv 5 \pmod{7}$

$5^2 \equiv 4 \pmod{7}$

$5^3 \equiv 6 \pmod{7}$

$5^4 \equiv 2 \pmod{7}$

$5^5 \equiv 3 \pmod{7}$

$5^6 \equiv 1 \pmod{7}$

$5^7 \equiv 5 \pmod{7}$

$5^8 \equiv 4 \pmod{7}$

$5^{13} \equiv 5 \pmod{7}$

我们看到 $5$ 的幂跨越了群的所有元素。我们还看到数字以 $6$ 的间隔重复自身，即 $4 = 5^2 = 5^8 = 5^{14}...$。让我们看看 $3$：

$3^1 \equiv 3 \pmod{7}$

$3^2 \equiv 2 \pmod{7}$

$3^3 \equiv 6 \pmod{7}$

$3^4 \equiv 4 \pmod{7}$

$3^5 \equiv 5 \pmod{7}$

$3^6 \equiv 1 \pmod{7}$

$3^7 \equiv 3 \pmod{7}$

我们得到了所有元素（尽管顺序不同）。最后，让我们看看 $2$：

$2^1 \equiv 2 \pmod{7}$

$2^2 \equiv 4 \pmod{7}$

$2^3 \equiv 1 \pmod{7}$

$2^4 \equiv 2 \pmod{7}$

这次我们没有跨越群的所有元素，并且在 $3$ 之后得到了相同的数字。我们将证明这些结果通常有效（前提是我们正在以素数为模进行运算）。

首先，我们可以证明集合 $(\mathbb{Z}/p\mathbb{Z})^{\star}$ 与乘法一起形成一个阿贝尔群（乘积永远不会为 0，因为所有数字都不能被 $p$ 整除）。其次，群是有限的，因为元素的数量是有限的（在我们的例子中是 6）；它的阶数是 6。我们还看到，通过反复将 $5$ 乘以自身（即取 $5$ 的幂），我们可以生成群的所有元素（请注意，一切在 6 之后重复，这是群的阶数）。由于该群可以由其一个元素生成，因此它是一个（有限）循环群。

对于元素 $a$，使得 $a^n \equiv 1 \pmod{p}$ 的最小正整数 $n$ 被称为 $a$ 的阶数。群的元素及其各自的阶数（括号中）是：1(1)，2(3)，3(6)，4(2)，5(6)，6(2)。我们可以看到每个元素的阶数除以群的阶数 6。我们将介绍以下定理，这些定理表明这并非巧合。

三个有用的定理和 RSA 背后的魔法

费马小定理：如果 $p$ 是素数，那么，对于任何整数 $a$，我们都有 $a^p - a$ 可被 $p$ 整除：

$a^p \equiv a \pmod{p}$。

练习：检查这对于 $(\mathbb{Z}/7\mathbb{Z})^{\star}$ 的所有元素是否有效。

如果 $a$ 与 $p$ 互质，我们可以等价地写成：

$a^{p-1} \equiv 1 \pmod{p}$

一个有趣的推论是，我们可以通过执行 $a^{-1} = a^{p-2}$ 来计算逆元，即使在某些情况下我们高估了幂（例如，$6 \times 6 \equiv 1 \pmod{7}$）。

Euler定理：如果 $a$ 和 $n$ 是正数互质整数，则 $a^{\phi(n)} \equiv 1 \pmod{n}$，其中 $\phi(n)$ 是 Euler函数。

Euler函数 $\phi(n)$ 计算与 $n$ 互质的数字 $m < n$。例如，如果我们取 $n = 5$，数字 $1, 2, 3, 4$ 都与 $5$ 互质，并且 $\phi(5) = 4$（这是合理的，因为 $5$ 是素数）。如果我们取 $8$，我们有 $1, 2, 3, 4, 5, 6, 7$；但是，只有 $1, 3, 5, 7$ 与 $8$ 互质，所以 $\phi(8) = 4$。对于素数，我们有

$\phi(p) = p - 1$

因此，Euler定理为我们提供了费马定理作为特例。另一个有用的属性是，如果 $m$ 和 $n$ 互质，则

$\phi(m \times n) = \phi(n) \times \phi(m)$

这表明 $\phi$ 是一个 积性函数。特别是，如果 $n$ 是两个素数 $p$ 和 $q$ 的乘积，则

$\phi(n) = (p - 1) \times (q - 1)$

RSA 的工作原理就在这里。公钥 $e$ 和私钥 $d$ 是模 $\phi(n)$ 的乘法逆元，

$d \times e \equiv 1 \pmod{\phi(n)}$

这意味着对于某个整数 $k$，$d \times e = 1 + k\phi(n)$，因此当我们计算时 $M^{e \times d} = M^{1 + k\phi(n)} = M \times M^{k\phi(n)} \equiv M \pmod{n}$ 因为 $M^{k\phi(n)} = (M^{\phi(n)})^k \equiv 1^k \pmod{n}$。RSA 的难度取决于分解数字 $n$ 的难度，并且多年来密钥的长度已大大增加（约为 2000 到 4000 位）；另一方面，椭圆曲线以较短的密钥提供相同的安全级别。

子群。拉格朗日定理

我们看到 $(\mathbb{Z}/7\mathbb{Z})^{\star}$ 的阶数为 6，如果我们取任何元素 $a$，则 $a^6 \equiv 1 \pmod{7}$。但是，对于 2，我们可以做 $2^3 \equiv 1 \pmod{7}$。子群 $H$ 是 $G$ 的子集，它本身就是一个群，即满足 G1-G4。例如，如果我们考虑子集 $H={1}$，这是一个 1 阶子群。为什么？因为 $1 \times 1 = 1$，所以运算是封闭的，所有其他属性都来自群 $G$ 的运算。$G$ 也是它自身的子群。这两个被称为 $G$ 的平凡子群（不是很重要）。集合 ${1,2,4}$ 是 $(\mathbb{Z}/7\mathbb{Z})^{\star}$ 的一个子群。为了检查这一点，我们需要查看集合中是否包含某个元素，它的逆元也包含在该集合中，单位元属于该集合并且运算是封闭的。让我们检查一下：

• $1$ 在集合中，$1$ 是它自身的逆元。
• 运算是封闭的，因为 $2 \times 2 \equiv 4 \pmod{7}$，因为 $4 \times 4 = 16 \equiv 2 \pmod{7}$ 并且因为 $2 \times 4 = 8 \equiv 1 \pmod{7}$（我们不需要检查与 $1$ 的乘积，因为这是显而易见的）。我们还检查了逆元，因为 $4=2^{-1}$。

子集 ${1,2,4}$ 形成一个 3 阶子群。拉格朗日定理 指出，子群的阶数可整除群的阶数。我们还有另一个子群 ${1,6}$，它是 2 阶的。这些是非平凡子群。如果一个群的阶数是素数，那么它的唯一子群是平凡子群（因为 $p$ 是素数，子群只能是 1 阶和 $p$ 阶）。一个只有平凡子群的群被称为单群。例如，具有加法的 $\mathbb{Z}/7\mathbb{Z}$ 是 7 阶的群 ${0,1,2,3,4,5,6}$。除了整个群和 0 之外，没有其他子群。请注意，每个元素（除了零，它的阶数为 1）的阶数是 7，因为 $7 \times a = a+a+a+a+a+a+a$ 可以被 7 整除，因此与 0 模 7 同余。当使用椭圆曲线时，某些群可以分解为更小的子群这一事实令人担忧：如果群的阶数不是素数，则可以将其分解为更小的群，并且攻击者可以通过在这些子群上执行搜索来破坏系统。

离散对数问题

给定一个群，我们可以重复地对一个点 $g$ 应用运算以得到一个点 $P$，即 $g^k = g \times g \times g \times \cdots \times g = P$。例如，在 $(\mathbb{Z}/7\mathbb{Z})^{\star}$ 中，5 通过与自身连续相乘来生成所有元素。然后我们可以问，我们应该将 5 与自身相乘多少次 $x$ 才能得到 3，即 $5^x \equiv 3 \pmod{7}$。因为我们知道这个群的阶数是 6，所以我们只应该关注数字 0-6。如果我们向上看或尝试所有组合，$5^5 \equiv 3 \pmod{7}$，所以 $x=5$。类似地，如果我们寻找 $y$ 使得 $5^y \equiv 4 \pmod{7}$，我们得到 $y=2$。寻找 $x$ 使得 $g^k = P$ 的问题被称为离散对数问题（在数论中，$x$ 和 $y$ 被称为指数）。我们很快看到，这个对数与实数上的普通对数的工作方式截然不同（尽管这个想法是相同的，给定 $y$，找到 $x$ 使得 $e^x=y$）。没有明显的模式，它不是递增的，如果我们必须在一个大的集合上搜索，那将是非常令人生畏的。许多密码系统都依赖于这个问题在有限循环群上的难度。

总结

我们介绍了数论和代数中的一些基本术语和概念，这些术语和概念在阅读密码学时会很有用，因为许多关键概念和策略都依赖于数学。群、环和域以及素数的概念几乎总是出现。很快我们将继续使用其他重要的工具和概念，这些工具和概念将帮助我们理解椭圆曲线密码学是如何工作的，如何在群上执行更快的运算以及如何组合椭圆曲线来构建 zk-SNARK。

• 原文链接： blog.lambdaclass.com/mat...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～