高中數學擴充套件/進一步模運算/乘法群和離散對數

高中數學擴充套件

---

補充章節 — 素數和模運算 — 邏輯

數學證明 — 集合論和無窮過程 — 計數和生成函式 — 離散機率

矩陣 — 進一步模運算 — 數學規劃 — 馬爾可夫鏈

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$

... 更多內容待續

反饋

你覺得怎麼樣？ 太容易還是太難？ 資訊太多還是不夠？ 我們如何改進？ 請在討論標籤中發表評論告訴我們。 更好的是，自己編輯它並改進它。