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

高中數學擴充套件

---

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

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

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

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$

...待續

反饋

您覺得如何？ 太簡單還是太難？ 資訊太多還是不夠？ 我們該如何改進？ 請在討論區留言告訴我們。 更好的是，您可以自己編輯並改進它。