給定GGg,bbb,G一個_G一種bg^{ab}, 正在尋找G一種G一種g^a一個難題？
如標題所示，給定 $ g $ , $ g^{ab} $ 是素群中的大元素 $ Z_p $ 和 $ b $ 在素數組 $ Z_r $ ( $ p > r $ , $ g $ 是一個生成器 $ Z_p $ ). $ a $ 是未知的，也在 $ Z_r $ , 正在尋找 $ g^a $ 一個難題？
更新 $ a $ , $ b $ 和 $ ab $ 是的群元素 $ Z_r $ ..
目前措辭的問題，並考慮其作者的評論，將歸結為：這是一個很難找到的問題 $ g^a\bmod p $ , 給定
- 大素數 $ p $
- 大整數 $ g $ 少於 $ p $ 這是一個生成器 $ \mathbb Z_p $ $$ see note 1 $$
- 主要 $ r $ 少於 $ p $
- 未知的知識 $ a $ 是小於的正整數 $ r $
- 正整數 $ b $ 少於 $ r $
- $ g^{a\cdot b\bmod r}\bmod p $ $$ see note 2 $$
注 1：我們可以放心地假設我已經假設這意味著 $ g $ 是乘法群的生成器 $ \mathbb Z_p^* $ 的 $ \mathbb Z_p $ ; 也就是應用 $ x\to g^x\bmod p $ 是對小於的正整數集的映射 $ p $ ; 這可以在因式分解時有效地測試 $ p-1 $ 已知，通過檢查 $ g^{(p-1)/q}\bmod p;\ne1 $ 對於每個素數 $ q $ 劃分 $ p-1 $ .
注2：語句使用符號 $ g^{ab} $ , 表明 $ g $ 處於素數組 $ \mathbb Z_p $
$$ which we can safely assume is the multiplicative group $\mathbb Z_p^$ $$, 表示那個元素 $ g^{ab} $ 的 $ \mathbb Z_p $ 以整數形式給出 $ g^{ab}\bmod p $ ; 並表明 $ a $ 和 $ b $ 處於素數組 $ \mathbb Z_r $ ,評論說 $ ab $ 計算在 $ \mathbb Z_r $ $$ which I similarly assume is the multiplicative group $\mathbb Z_r^$ $$, 並評論暗示一個元素 $ \mathbb Z_r $ 被同化為小於的非負整數 $ r $ ; 因此我的解釋是給定的陳述為 $ g^{ab} $ 真的是 $ g^{a\cdot b\bmod r}\bmod p $ . 我們不能猜測/希望/假設 $ g^r\bmod p;=1 $
$$ including that $r=p-1$, the order of $g$ $$，因為這會與給定的假設相矛盾 $ p $ 和 $ r $ 是素數 [見評論] $ p $ 大且大於 $ r $ ， 和 $ g $ 是一個發電機。因此 $ g^{a\cdot b}\bmod p $ 和 $ a\cdot b $ 整數乘法得到的沒有理由 $ g^{a\cdot b\bmod r}\bmod p $ ，通常不是。 現在我不知道如何在一般情況下解決這個問題，甚至不計算它的解決方案。這與我對某些參數可能是一個難題的印象的合理性相去甚遠。
如果我們知道 $ g^{a\cdot b}\bmod p $ $$ rather than $g^{a\cdot b\bmod r}\bmod p$, as I assume we do $$，我們可以忽略給定的 $ r $ 並且經常通過其他答案中概述的方法解決問題，因為該方法在以下情況下有效 $ \gcd(b,p-1)=1 $ . 根據 $ p $ 這可能很常見，也可能不常見；例如素數 $ p= $ 1719620105458406433483340568317543019584575635895742560438771105058321655238562613083979651479555788009994557822024565226932906295208262756822275663694111, $ \gcd(b,p-1)=1 $ 什麼時候 $ b $ 沒有小於 383 的除數，這種情況很少發生 $ b $ .
更新：現在在評論中詢問我們是否可以計算 $ c=b^{−1} $ 在 $ \mathbb Z_r $ ，然後計算 $ (g^{ab})^c $ 要得到 $ g^a $ . 這表明我對上述陳述的解釋有問題，儘管答案被接受了。
該方法不適用於大多數素數 $ r $ 少於 $ p $ 和大多數對 $ (a,b) $ , 不管是否 $ ab $ 計算在 $ \mathbb Z_r $ 或在 $ \mathbb N $ .
這確實有效，如果 $ g^r\bmod p;=1 $ 和 $ \gcd(b,r)=1 $ , 對於任何一種計算方式 $ ab $ （變成等價的）。但是，如果我們相信給定的 $ g $ 是發電機，唯一的 $ r $ 少於 $ p $ 和 $ g^r\bmod p;=1 $ 是 $ r=p-1 $ . 和
$$ using that $p$ is huge $$， 這樣的 $ r=p-1 $ 不是素數，相反 $ r $ 聲明建議並在評論中確認。這也不適用於 $ b $ 甚至，或不與 $ p-1 $ . 數值較小的插圖 $ p=23 $ , $ g=19 $
$$ which matches the condition that $g$ is a generator $$, $ r=17 $ 除非另有說明， $ a=8 $ ， 和 $ b=6 $ :
- 與乘法 $ \mathbb Z_r $ : $ ab=14 $ , $ g^{ab}=18 $ , $ c=3 $ , $ (g^{ab})^c=13 $ ， 不匹配 $ g^a=9 $
- 與乘法 $ \mathbb N $ : $ ab=48 $ , $ g^{ab}=3 $ , $ c=3 $ , $ (g^{ab})^c=4 $ ， 不匹配 $ g^a=9 $
- 更換 $ r $ 和 $ p-1=22 $ : $ ab=14 $ 或者 $ 48 $ , $ g^{ab}=18 $
$$ either way $$, $ c $ 無法計算。
我對預期陳述的最終（？）猜測是 $ g $ 不是生成器，與目前措辭的問題相反，而是
$ g $ 是素數的一個元素 $ r $ 在乘法組 $ \mathbb Z_p^* $
請注意這是如何創建條件連結的 $ r $ 到 $ p $ （和 $ g $ ），問題的措辭中沒有！憑藉這種新穎性，它認為 $ g^r\bmod p;=1 $ ，因此，如果 $ g^{ab} $ 用乘積計算 $ {ab} $ 在 $ \mathbb Z_r $ 或在 $ \mathbb N $ . 它還認為 $ \gcd(b,r)=1 $
$$ since $r$ is prime $$，因此最近評論中的方法總是有效的，答案是否定的。 我們可以用 $ p=23 $ , $ g=13 $
$$ which is not a generator since $g^{11}\bmod p;=1$ $$, $ r=11 $ $$ which is prime $$, $ a=8 $ ， 和 $ b=6 $ :
- $ ab=14 $ 或者 $ 48 $ , $ g^{ab}=18 $ $$ either way $$, $ c=2 $ , $ (g^{ab})^c=2 $ , 匹配 $ g^a=2 $ .