Pohlig-Hellman：在 subgrp 中求解時，為什麼要對父組進行乘法運算ppp而指數根據p一世p一世p_i子組的
在 Pohlig-Hellman 算法中，我們將離散對數問題 (DLP) 放在一個組中並在子組中解決它 $ p_1^{n_1} $ , $ p_2^{n_2} $ , $ p_3^{n_3} $ 等然後將其與中國剩餘定理（CRT）結合起來。
原始 DLP 是 $ \bmod p $ ＆ 命令 $ p -1 = n = p_1^{n_1} * p_2^{n_2} * p_3^{n_3} …. $
當我們求解子組時 $ p_1^{n_1} $ ，我們幀的係數個數 $ x $ 基於最大值 $ x $ 可以拿即 $ p_1^{n_1} - 1 $
例如，如果我們正在求解 $ 3^4 $ ，然後我們框定 $ x $ 作為
$ x = c_0 + 3c_1 + 3^2c_2 + 3^3c_3 $
$ x $ 這裡有 4 個係數 ( $ c_0 $ , $ c_1 $ , $ c_2 $ & $ c_3 $ ) 因為 x 的最大值是 [ $ p_1^{n_1} - 1 $ ] （因為它是 $ \bmod p_1^{n_1} $ )
然而，當我們實際求解時 $ x $ 對於子組 $ p_1^{n_1} $ , 我們用 $ \bmod q $ ， 代替 $ \bmod p_1^{n_1} $ . 這是為什麼？
例如，如果我們在這裡舉個例子：當他們計算 $ 8006^{2025} = 1 $ 對於子組 $ 2^2 $ , 這實際上計算為 $ 8006^{2025} \bmod p $ 而不是 $ \bmod p_1^{n_1} $ . 在所有的計算中都是一樣的。為什麼是這樣？難道不應該做 $ \bmod p_1^{n_1} $
當我們正在尋找 $ x = x_1 \bmod {p_i}^{n_i} $ , 我們在做計算 $ \bmod q $ 而不是做他們 $ \bmod {p_i}^{n_i} $ .
**編輯：**或者另一個問題可能是這個 - 子組的操作總是 $ \bmod p $ 而不是 $ \bmod {p_i}^{n_i} $ . 考慮到這一點，那麼為什麼我們為 3 個子組得到的 3 個同餘方程也不是 $ \bmod p $ . 他們為什麼 $ \bmod 4 $ , $ \bmod 81 $ & $ \bmod 25 $ ?
**EDIT2：**根據各種答案，我將我的問題歸結為一行
雖然子組中的乘法是以 p 為模進行的，但為什麼子組中的指數是以模擴展的 $ p_i $ ?
有什麼理論可以解釋這一點嗎？
問題的範例要求找到解決方案 $ x $ 方程的 $ a^x\equiv b\pmod p $ 給定 $ p $ , $ a $ , $ b $ ， 和 $ p=8101 $ , $ a=6 $ , $ b=7531 $ . 據說 $ a $ 是一個生成器 $ \mathbb Z_{8101} $ , 但它的意思是 $ \mathbb Z_{8101}^* $ ，這是乘法群模 $ p $ . 這 $ ^* $ （或者 $ ^\times $ ) 表示我們使用整數環模的乘法定律 $ p $ ，或者等價地，我們通過保持環中可逆的元素來形成群，正如群公理所要求的那樣。特別是，這意味著我們排除 $ 0 $ , 和任何 $ c $ 和 $ \gcd(c,p)\ne1 $ .
那個離散對數問題是模素數 $ p $ ，一個簡化的特殊情況¹。上述組 $ \mathbb Z_p^* $ 因此是²循環的。它有秩序 $ n=p-1 $ ， 那是 $ n $ 我們可以通過它們在範圍內的整數代表來指定元素 $ [1,n] $ . 任何元素的順序 $ c $ 該組的，定義為最小整數 $ \ell>0 $ 和 $ c^\ell\equiv1\pmod p $ 從而劃分順序 $ n $ 該組的。我們被告知 $ a $ 是一個生成器，這意味著 $ a $ 是 $ n $ ，我們可以檢查一下這個³。
我們現在處於可以應用 Wikipedia 中所述的通用 Pohlig-Hellman算法的情況下， $ \mathbb G $ 有秩序的 $ n $ 我們的 $ \mathbb Z_p^* $ 有秩序的 $ n=p-1 $ ， 他們的 $ g $ , $ h $ 和 $ e_i $ 我們的 $ a $ , $ b $ ， 和 $ n_i $ :
- 該算法的第一步是分解 $ n $ 進入 $ n=\prod{p_i}^{n_i} $ ， 那是 $ 8100=2^2\cdot3^4\cdot5^2 $ . 對於每個 $ i $ 我們將形成一個子組 $ \mathbb Z_p^* $ 我們解決子問題的地方。
- 每個子問題都是 $ \left(a^{n/({p_i}^{n_i})}\right)^{x_{p_i}}\equiv b^{n/({p_i}^{n_i})}\pmod p $ （根據連結範例的符號，它使用 $ x_2 $ , $ x_3 $ , $ x_5 $ 維基百科使用的地方 $ x_1 $ , $ x_2 $ , $ x_3 $ ）。這個子問題中的每一個都在（循環）子組中 $ \mathbb Z_p^* $ 由產生 $ a^{n/({p_i}^{n_i})}\bmod p $ , 有序的 $ {p_i}^{n_i} $ . 我們使用 Pohlig-Hellman 分別求解每個素數冪階組。涉及子群元素的計算在主群內，因此在 $ \mathbb Z_p^* $ , 因此模 $ p $ . 涉及指數的計算（特別是解 $ x_{p_i} $ ) 以子群階為模，即 $ {p_i}^{n_i} $ .
- 然後我們加入解決方案 $ x_{p_i} $ 在中國剩餘定理步驟中，互質模數是 $ {p_i}^{n_i} $ , 哪個產品是我們的 $ n=p-1 $ .
總之，所有涉及乘法的計算 $ a $ 或者 $ b $ 是模組 $ p $ ，以便在組中 $ \mathbb Z_p^* $ . 養也一樣 $ a $ 或者 $ b $ （或其權力的乘積）到某種權力。僅涉及指數的操作（即定義我們將這種組合提高到哪個冪的整數 $ a $ 或/和 $ b $ ) 取模以外的東西為模 $ p $ : 群階或子群階，因此取模 $ n $ 在哪裡 $ n=p-1 $ , 或以某個除數為模 $ n $ .
為什麼我們為 3 個子組得到的 3 個同餘方程也不是 $ \bmod p $ . 他們為什麼 $ \bmod 4 $ , $ \bmod 81 $ & $ \bmod 25 $ ?
因為它們是模數的同餘 $ {p_i}^{n_i} $ 的 3 個子組中的 $ \mathbb Z_p^* $ 由 3 個元素生成 $ a^{n/({p_i}^{n_i})}\bmod p $ . 這些子組中的關係（乘法） $ \mathbb Z_p^* $ 將是模數 $ p $ .
雖然子組中的乘法是模數 $ p $ , 為什麼子群中的指數展開模 $ p_i $ ?
對於任何有限群 $ (\mathbb G,) $ 有秩序的 $ r $ （也就是說，與 $ r $ 元素），對於任何 $ x\in\mathbb G $ ，它成立⁴ $ \underbrace{xx\ldots x*x}_{r\text{ terms}}=x^r=1 $ ， 在哪裡 $ 1 $ 是該組的中立者。
因此，對於任何整數 $ s $ 和 $ t $ , $ x^s*x^t=x^{s\cdot t\bmod r} $ ， 在哪裡 $ s\cdot t\bmod r $ 無論群的性質和群定律如何，都在整數上計算 $ * $ . 這就是為什麼指數以組階為模計算的原因。
當我們考慮一個子群 $ \mathbb Z_p^* $ （因此計算是模 $ p $ ) 有順序 $ p_i $ （如在這個子問題中）或 $ {p_i}^{n_i} $ （如在整體問題中），該子組是一組順序 $ r=p_i $ 或者 $ r={p_i}^{n_i} $ . 在該子組中工作時，我們可以因此減少指數模 $ r $ .
注意順序 $ r $ 有限子群的 總是劃分主群的順序，這裡 $ n=p-1 $ .
在子組中解決它 $ {p_1}^{n_1} $ , $ {p_2}^{n_2} $ , $ {p_3}^{n_3} $ ETC
在這裡要精確很重要：我們正在求解一個方程 $ a^x\equiv b\pmod p $ 在順序子組中 $ {p_i}^{n_i} $ 主要群體的 $ \mathbb Z_p^* $ . 因此，與指數相關的方程在整數環模中陳述（並求解） $ {p_i}^{n_i} $ 著名的 $ \mathbb Z_{{p_i}^{n_i}} $ ; 而與主群中的指數相關的方程在整數環中模 $ n=p-1 $ 著名的 $ \mathbb Z_n $ .
關於符號的挑剔注意：
對於整數 $ m>0 $ , 符號 $ u\equiv v\pmod m $ 讀作“ $ u $ （是）符合 $ v $ 模組 $ m $ “或有時” $ u $ 等於） $ v $ … 模組 $ m $ ”，作為“（的代表）的縮寫 $ u $ 等於（代表） $ v $ 在整數環中取模 $ m $ ”。該符號意味著（等效地）：
- 那 $ m $ 劃分 $ u-v $
- 那 $ u-v $ 是的倍數 $ m $
- 歐幾里得除法的餘數 $ \left\lvert u-v\right\rvert $ 經過 $ m $ 是 $ 0 $
- 存在整數 $ w $ 和 $ u=(w\cdot m)+v $
符號 $ u=v\bmod m $ 和 $ v\bmod m=u $ , 其中 $ \bmod $ 是將兩個整數組合成一個整數的運算符，分別讀作“ $ u $ 等於） … $ v $ 模組 $ m $ “ 和 ” $ v $ 模組 $ m $ 等於） $ u $ ”。兩者都意味著（等效地）：
那 $ u\equiv v\pmod m $ 如上所述，和 $ 0\le u<m $
那 $ u $ 是
- 歐幾里得除法中的餘數 $ v $ 經過 $ m $ ， 什麼時候 $ v\ge0 $
- $ m-1-((-u-1)\bmod m) $ ， 否則
聽的時候” $ u $ 等於 $ v $ 模組 $ m $ ”（沒有明顯的停頓），或者看到 $ u=v\mod m $ （在左側有額外的間距 $ \bmod $ 由於使用
\mod而不是\pmod或\bmod)，可能會出現關於 if 的歧義 $ 0\le u<m $ 意思是，這在某些加密應用程序中很重要。當我們寫 $ c=m^e\bmod n $ 在 RSA 中，我們肯定地斷言 $ 0\le c<n $ . 為了一致性，我們想寫 $ \forall k\in\mathbb N,;2^k\equiv2^{k\bmod 42}\pmod{43} $ ， 而不是 $ \forall k\in\mathbb N,;2^k=2^{k\bmod 42}\bmod 43 $ , 有反例 $ k=6 $ .¹ 求解時 $ a^x\equiv b\pmod m $ 在復合材料的最一般情況下 $ m $ , 外部步驟可能是考慮因素 $ m $ 作為 $ m=\prod{m_j}^{k_j} $ 和 $ m_j $ 主要; 然後解決每個問題 $ a^{x_j}\equiv b\pmod{m_j^{k_j}} $ ; 然後加入解決方案。這裡有單 $ m_1 $ （一種特殊情況），以及 $ k_1=1 $ （另一種特殊情況）。
² 反之亦然，見此。
³ 標準技術確保 $ a^{n/p_i}\not\equiv1\pmod p $ 對於每個素數 $ p_i $ 劃分 $ n $ . 這裡 $ n=p-1=8100=2^2\cdot3^4\cdot5^2 $ 因此 $ p_i\in{2,3,5} $ ，並且兩者都不是 $ 6^{4050}\bmod8101 $ , $ 6^{2700}\bmod8101 $ , $ 6^{1620}\bmod8101 $ 是 $ 1 $ ， 因此 $ a=6 $ 確實是發電機。
⁴費馬小定理，形式為 $ a^{p-1}\equiv1\pmod p $ 為素數 $ p $ 和 $ a $ 不能被 $ p $ , 正是該陳述的一個限制 $ (\mathbb G,) $ 群組 $ \mathbb Z_p^ $ 和 $ p $ 是素數。