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

高中数学扩展

---

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

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

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

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

离散对数问题

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

例如，我们知道对于某个x，5^x ≡ 172 (mod 263)。找到x 并不容易。最简单的方法似乎是尝试x = 2、3，等等。实际上，对于p 为素数，如果给定a^x ≡ b，则找到x 被称为离散对数问题，并且没有已知的有效方法来解决它。

然而，缺乏有效的算法并非唯一的问题。考虑 2^x ≡ 5 (mod 7)，它没有解！... 更多内容即将发布

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

练习

1. 求解 3^x ≡ 6 (mod 7)

2. 求解 2^x ≡ 48 (mod 61)

3. 求解 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^{1}\equiv 3$

$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（模 *p*）。

现在，如果我们证明 *G* 中的每个元素都必须满足 *x*^|g| ≡ 1，那么我们就完成了。假设存在一个元素 *h* 使得 *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$

... 更多内容待续

反馈

你觉得怎么样？ 太容易还是太难？ 信息太多还是不够？ 我们如何改进？ 请在讨论标签中发表评论告诉我们。 更好的是，自己编辑它并改进它。