使用 Pohlig-Hellman 算法求解同餘

使用 Pohlig-Hellman 算法計算解：

$ 3^x\equiv 2 \pmod {65537} $

我的嘗試：

$ p-1 = 65537-1 = 65536= 2^{16} $

$ x= 2^0x_0+2^1x_1+2^2x_2+…+2^{15}x_{15} $

為了 $ x_0 $ :

$ 2^{65536/2}=3^{(65536/2)x_0} $

$ 1 \pmod {65537} \equiv (-1)^{x_0} \pmod{65537} $

所以 $ x_0 = 0 $

這是正確的嗎？因為在那之後的所有其他步驟，我得到 $ 0 $ 適合所有人 $ x_i $ 在哪裡 $ i=1,2,3,…,15 $

任何幫助，將不勝感激！

您在程序中是正確的。你需要表達 $ x $ 作為 $ x = 2^0x_0+2^1x_1+2^2x_2+…+2^{15}x_{15} $

在哪裡 $ x_i $ 在 $ GF(2) $

第一次計算：

$ 3^{(0*(p-1)/2)} \pmod p \equiv 1 $

$ 3^{(1*(p-1)/2)} \pmod p \equiv 65536 $

這樣當你計算 $ 2^{65536/2^{i+1}} \pmod p $ 你會得到 1 （對應於 $ x_{i} = 0 $ ) 或 65536 (對應於 $ x_{i} = 1 $ )

對於第一個值 $ i $ 你只會得到 $ x_i=0 $ , 但隨後對於 $ i=11 $ : $ 2^{65536/2^{12}} \pmod p\equiv 65536 $ 對應於 $ x_{11}=1 $

然後你需要繼續……但我只是想表明你不會得到 0 $ x_i $

引用自：https://crypto.stackexchange.com/questions/24094