高中数学扩展/进一步模算术/乘法群和离散对数

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

HSME
内容
进一步模算术
乘法群和离散对数
问题和项目
问题集
项目
解决方案
练习解答
问题集解答
其他
定义表
完整版本
PDF 版本

介绍

群论是当今最重要的数学理论之一。...更多动机即将到来

设p为素数，则模p乘法群是数字集合 {1, 2, .., p - 1}。顾名思义，在模p群中，乘法是主要且唯一的关注点。请注意，在阶为p - 1 的乘法群中，每个元素都有一个逆元。这是群的关键要求。一般群论中，为了使G成为一个群，它必须

1. 由一组东西组成
   • 在本例中，数字 1 到p - 1，
2. 有一个二元运算
   • 在本例中是乘法，
3. 在该运算下封闭，即如果a和b是属于该群的东西，则ab也必须属于该群
   • 这在模p算术中肯定得到满足
4. 有一个单位元
   • 在本例中是数字 1
5. 每个元素在该运算下都有一个逆元
   • 在模p中，由于我们排除了群中的 0，因此满足此条件。

基本上，一个群需要有一个 1，并且每个其他元素都必须有一个逆元。在模算术中，群非常特殊，因为它也是可交换的（ab = ba），而对于一般群，不需要可交换性。可交换群称为阿贝尔群，以挪威数学家阿贝尔命名，阿贝尔.

顺便说一句，模p乘法群具有有限数量的元素。在一般群论中，群可以有无限多个元素。

信息 - 阿贝尔奖

The Abel's prize. ...more to come

离散对数问题

回想一下在实数中定义的log函数。令b^x = y，取以b为底的log，我们得到x = log_b(y)，因此给定b和y，我们可以求解x。但在模算术中，同一个问题可能很难解决。

例如，我们知道 5^x ≡ 172 (mod 263) 对某个 x 成立。找到 x 并不容易。最简单的方法似乎是尝试 x = 2, 3, ... 等等。实际上，对于素数 p，如果给出 a^x ≡ b，则找到 x 就是所谓的离散对数问题，目前还没有已知的有效方法来解决它。

然而，缺乏有效的算法并不是唯一的问题。考虑 2^x ≡ 5 (mod 7)，它没有解！...待续

我们将在本章稍后介绍一种解决离散对数问题的非常强大的方法，称为 Pohlig-Hellman 算法。它通过使用中国剩余定理将问题分解成多个部分。然而，现在我们应该尝试了解离散对数问题的难度。

练习

1. 找到 x 使得 3^x ≡ 6 (mod 7)

2. 找到 x 使得 2^x ≡ 48 (mod 61)

3. 找到 x 使得 5^x ≡ 172 (mod 263)

阶

一个群的阶指的是群中元素的数量。例如，模 17 的乘法群的阶为 16。首先，我们应该只考虑模素数 p 的乘法群，因此一个群的阶为 p - 1。如果 G 是一个群，则我们用 |G| 表示群的阶。

一个元素 g 在群 G 中的阶指的是最小的非零数 k，使得 g^k ≡ 1。我们用 |g| 表示 g 的阶，因此 g^|g| ≡ 1。我们想要讨论两个非常重要和基本的定理。我们已经多次遇到第一个定理。它指出

如果 G 是一个（有限）群，g 是群中的一个元素，那么

$g^{|G|}=1\!$

该定理的证明类似于费马小定理的证明。设 a 为 G 中的一个元素，g_i 为 G 中的元素。我们考虑

$a,ag_{1},ag_{2},ag_{3},...,ag_{|G|-1}\!$

以上有 |G| 个元素，它们必须全部不同。假设相反，即 $g_{i}\neq g_{j}\!$ 但 $ag_{i}\equiv ag_{j}\!$，那么由于 a 属于一个群，一定存在 a^-1，两边同时乘以 a 的逆，我们得到 $g_{i}\equiv g_{j}\!$，这与假设矛盾。

因此，我们可以说上面的列表只是 G 的 |G| 个元素的不同顺序排列，我们得到

$a(ag_{1})(ag_{2})(ag_{3})\cdots (ag_{|G|-1})\equiv g_{1}g_{2}\cdots g_{|G|-1}\!$

为了简化书写，我们设

$s\equiv g_{1}g_{2}\cdots g_{|G|-1}\!$

因此，我们有

$a^{|G|}s\equiv s\!$

但 s 属于该群，因此存在 s^-1，我们得到

$a^{|G|}\equiv 1\!$

如预期的那样。

读者应该被说服去计算模 17 中每个元素的阶。如果做到了这一点，应该注意到每个元素的阶都整除 16，即群的阶。这个事实通常是正确的，被称为拉格朗日定理。

拉格朗日定理

Let G be a (finite) group, and let g be an element of the group.
The order of g must divide the order of the group G. More symbolically, |g| divides |G|.

我们将给出上述定理的证明，但读者应该尝试自己提出证明。

证明
设 g 为 G 中的一个元素。我们知道

$g^{|G|}\equiv 1\!$

我们计算 |G| 除以 |g| 的余数，即找到 r < |g| 和 q，使得 |G| = q|g| + r。因此我们有

$g^{|G|}=g^{|g|q+r}\equiv (g^{|g|})^{q}g^{r}\equiv g^{r}\equiv 1\!$

但是r小于g的阶，所以r = 0。因此我们有q|g| = |G|，所以g的阶整除G的阶。

总结

Let G be a group and g be an element of the group, then
1. g|G| = 1, and
2. |g| divides |G|

练习

1. 计算所有元素模47的阶。

2. 计算所有元素模137的阶。

3. 数3模17的阶为16。找出模17中所有阶为16的元素。

生成元

我们已经证明了在模17中，数3的阶为16。这实际上很有趣，因为它表明模17群中的每一个元素都可以表示为3的幂，如下所示可以确认。

$3^{0}\equiv 1$

$3^{2}\equiv 9$

$3^{3}\equiv 27\equiv 10$

$3^{4}\equiv 30\equiv 13\equiv -4$

$3^{5}\equiv -12\equiv 5$

$3^{6}\equiv 15\equiv -2$

$3^{7}\equiv -6\equiv 11$

$3^{8}\equiv 33\equiv 16\equiv -1$

$3^{9}\equiv -3\equiv 14$

$3^{10}\equiv -9\equiv 8$

$3^{11}\equiv 24\equiv 7$

$3^{12}\equiv 21\equiv 4$

$3^{13}\equiv 12\equiv -5$

$3^{14}\equiv -15\equiv 2$

$3^{15}\equiv 6$

$3^{16}\equiv 1$

如果g使得G中所有其他元素都可以表示为g的幂，那么g被称为G的生成元，因为g可以用来生成所有其他元素。在其他书籍中，g也可能被称为本原元素。

一个值得注意的事实是，如果p是素数，那么模p的乘法群有一个生成元。一个证明将在后面给出。现在让我们讨论一下这个事实的含义。首先，如果g是一个生成元，那么谈论以g为底的对数是有意义的，在数论中被称为以g为底的指数，因为每个元素h = g^x，所以ind_g(h) = x。因此，如果我们得到

$h\equiv k^{x}\!$

对于某个未知的x，我们对两边取指数

$\operatorname {ind_{g}} (h)=x\ \operatorname {ind_{g}} (k)\!$

使x成为主题，我们得到

$x={\frac {\operatorname {ind_{g}} (k)}{\operatorname {ind_{g}} (h)}}\!$

我们实质上将一个一般的离散对数问题转化成了一个以g为底的离散对数问题，其中g是一个生成元。因此，如果我们能够解决以g为底的离散对数问题，那么我们就解决了所有离散对数问题。

但是，解决以g为底（生成元）的离散对数问题也很难。实际上，找到一个生成元也不容易。

让我们回到模17。注意，实际上有8个生成元。它们是3、10、5、11、14、7、12和6。φ(17 - 1)也等于8，这并非巧合。

练习

1. 找出41的所有生成元。

2. 已知6是模41的生成元。求17（模41）以6为底的离散对数。

3. 模709中有多少个生成元。注意708 = 2² × 3 × 59。

...待续

生成元的存在

在本节中，我们将证明模p素数中必须存在一个生成元。假设一个阿贝尔（乘法）群G的阶为p - 1（即 {1,2,3,...p - 1} 是G的元素，并且算术在模p下进行），令g为G中最大阶的元素，即 |g| ≥ |h| 对于G中的任何元素h。

现在考虑方程

$x^{|g|}\equiv 1{\pmod {p}}\!$

或者等价地

$x^{|g|}-1\equiv 0{\pmod {p}}\!$

元素g显然满足上述方程，但g的任何幂也满足。可以确认

$(g^{a})^{|g|}\equiv (g^{|g|})^{a}\equiv 1^{a}\equiv 1\!$

换句话说，我们可以将多项式因式分解如下

$x^{|g|}-1=(x-1)(x-g)(x-g^{2})\cdots (x-g^{|g|-1})\equiv 0\!$

我们可以证明只有g的幂才能满足上述方程。假设不是这样，即如果一个元素h不是g的幂，但h也满足h^|g| ≡ 1，那么将h代入上述方程，我们得到

$h^{|g|}-1=(h-1)(h-g)(h-g^{2})\cdots (h-g^{|g|-1})\equiv 0\!$

因为假设 h 不是 g 的幂，所以上面的所有项均不为零，因此它们必须有逆。将每一项乘以其逆。最终得到

$1\equiv 0\!$

这是荒谬的！矛盾！因此，只有 g 的幂才能满足 x^|g| ≡ 1 (mod p)。

现在，如果我们证明 G 中的每个元素都必须满足 x^|g| ≡ 1，那么我们就完成了。假设存在一个元素 h 不满足该方程，那么 |h| 不会整除 |g|。因此，我们必须有

$|gh|={\frac {|g||h|}{\gcd {(|g|,|h|)}}}$

(如果不太清楚，请参阅习题)，它大于 |g|。但这与 g 具有最大阶的事实相矛盾！因此，G 的每个元素都必须是 g 的幂，因此 g 是 G 的生成元。

上述内容表明，在模 p 素数中，始终存在生成元，但它没有告诉我们如何找到一个生成元。截至今天，还没有普遍使用的高效算法来为一般的 p 寻找生成元。

练习

0. (可选) 证明 lcm(a,b)×gcd(a,b) = ab，其中 lcm(x,y) 表示 x 和 y 的最小公倍数。例如，lcm(5,7) = 35，lcm(14,49) = 98。

1. 在模 p 中证明，|ab| = lcm(|a|,|b|)，其中 lcm(x,y) 表示 x 和 y 的最小公倍数。例如，lcm(5,7) = 35，lcm(14,49) = 98。

子群

...待续

*Pohlig-Hellman 算法*

现在，我们准备好学习关于用于查找离散对数的 Pohlig-Hellman 算法。如上所述，它通过将问题分解为多个部分来解决问题。在本节中，我们可能需要计算器。

首先考虑一个简单的例子。设 p = 113，给定 3 是模 113 的生成元，我们要找到一个 x 使得 3^x ≡ 38。我们可以假设

x = 0, 1, 2, ... , 或 111

(因为 x¹¹² ≡ 1 ≡ x⁰)。所以 x 就像模 112 = 2⁴7 中的一个值。根据中国剩余定理，x 可以唯一地表示为一个二元组。

假设

$x\equiv a_{0}+2a_{1}+2^{2}a_{2}+2^{3}a_{3}{\pmod {2^{4}}}\!$

我们以上面这种奇特的方式表示 x，以便我们可以更容易地获得值（很快就会明白），并且

$x\equiv b{\pmod {7}}\!$.

其中 $a_{i}$ 取值为 0 或 1，b 取值为 0, 1, 2, 3, 4, 5, 或 6。

该算法分为三个阶段，我们将逐一描述每个阶段。首先，我们要计算 $a_{0},a_{1},a_{2}$ 和 $a_{3}$ 的值。我们计算以下值

1. $3^{0{\frac {112}{2}}}\equiv 3^{0}\equiv 1$
2. $3^{1{\frac {112}{2}}}\equiv 3^{56}\equiv -1\equiv 112$

我们这样做是为了以后查询。

现在考虑

$a=38^{\frac {p-1}{2}}\equiv 3^{x{\frac {p-1}{2}}}\equiv 3^{(a_{0}+a_{1}2+a_{2}2^{2}+a_{3}2^{3}){\frac {p-1}{2}}}$

因此

$a=3^{(a_{0}{\frac {p-1}{2}}+a_{1}(p-1)+a_{2}2(p-1)+a_{3}2^{2}(p-1))}\equiv 3^{(a_{0}{\frac {p-1}{2}})}$

现在我们将 *a* 与上面计算的值进行比较，如果 *a* 等于 1，那么我们可以得出结论 $a_{0}$ = 0，否则如果 *a* 等于 -1，那么我们可以得出结论 $a_{0}$ = 1。因此我们已经发现了 $a_{0}$ 的值。

为了找出 $a_{1}$，我们注意到

$38^{\frac {p-1}{2}}3^{-a_{0}{\frac {p-1}{2}}}\equiv 3^{(x-a_{0}){\frac {p-1}{2}}}\equiv 3^{(a_{1}(p-1)+a_{2}2(p-1)+a_{3}2^{2}(p-1))}\!$

所以计算

$a\!$	$=\!$	$38^{\frac {p-1}{2^{2}}}3^{-a_{0}{\frac {p-1}{2^{2}}}}\equiv 3^{(x-a_{0}){\frac {p-1}{2^{2}}}}\!$
	$\equiv \!$	$3^{(a_{1}{\frac {p-1}{2}}+a_{2}(p-1)+a_{3}2(p-1))}$
	$\equiv \!$	$3^{(a_{1}{\frac {p-1}{2}})}\!$

现在如果 *a* = 0 那么 $a_{1}=0$，否则 $a_{1}=1$。

以同样的方式，计算

$38^{\frac {p-1}{2^{3}}}3^{(-a_{0}-2a_{1}){\frac {p-1}{2^{3}}}}$

然后

$38^{\frac {p-1}{2^{4}}}3^{(-a_{0}-2a_{1}-2^{2}a_{2}){\frac {p-1}{2^{4}}}}$

来确定$a_{2}$ 和 $a_{3}$ 的值。

现在确定b 的值。让我们计算以下 7 个值

1. $3^{0{\frac {112}{7}}}\equiv 3^{0}\equiv 1$
2. $3^{1{\frac {112}{7}}}\equiv 3^{16}\equiv 49$
3. $3^{2{\frac {112}{7}}}\equiv 3^{32}\equiv 28$
4. $3^{3{\frac {112}{7}}}\equiv 3^{48}\equiv 16$
5. $3^{4{\frac {112}{7}}}\equiv 3^{64}\equiv 106$
6. $3^{5{\frac {112}{7}}}\equiv 3^{80}\equiv 109$
7. $3^{6{\frac {112}{7}}}\equiv 3^{96}\equiv 30$

然后我们计算

$a=38^{\frac {112}{7}}\equiv 3^{x{\frac {112}{7}}}\equiv 3^{b{\frac {112}{7}}}$

并与上面计算的值进行比较以获得b。

如果我们正确地计算了a 的值，那么我们应该看到

$a_{0}=1$

$a_{1}=1$

$a_{2}=1$

$a_{3}=1$

并且

b = 6.

现在解

$x\equiv 1+2+2^{2}+2^{3}\equiv 15{\pmod {16}}\!$

$x\equiv 6{\pmod {7}}\!$

得到 *x* = 111。因此 3¹¹¹ = 38。

同时模方程的组合通过中国剩余定理实现

$x=a*7*(7^{-1}\mod {16})+b*16*(16^{-1}\mod {7}){\pmod {112}}$

$x=15*7*7+6*16*4{\pmod {112}}=111$

...待续

反馈

您觉得如何？ 太简单还是太难？ 信息太多还是不够？ 我们该如何改进？ 请在讨论区留言告诉我们。 更好的是，您可以自己编辑并改进它。