離散對數和周期函式的 Shor 算法
我想知道以下眾所周知的問題：讓 $ p $ 是一個素數， $ g $ 是一個生成器 $ (\mathbb{Z}/p\mathbb{Z})^\times $ , $ b \in (\mathbb{Z}/p\mathbb{Z})^\times $ . 尋找 $ x $ - 一個整數，使得 $ g^x = b \mod p $ .
當我閱讀有關離散對數問題的 Shor 算法時，我總是看到以下函式 $$ f(x_1, x_2) = b^{x_1} a^{x_2} \mod p $$任務是找到函式的周期，即 $ (\omega_1, \omega_2) $ 這樣 $$ f(x_1, x_2) = f(x_1 + \omega_1, x_2 + \omega_2) $$.
我的問題如下：為什麼我們考慮複雜的功能而不考慮最簡單的功能： $$ f(x_1) = b^{x_1} \mod p $$ 如果我們能找到函式的周期 $ \omega_1 < p - 1 $ 然後 $$ g^{x \omega_1} = 1 \mod p $$ 因此，根據小費馬定理，我們有 $$ x \omega_1 = 0 \mod p-1 $$ 這可以給出離散對數問題的解決方案
知道第二個函式的周期對您沒有幫助，因為您已經知道它（至少對於常見的 Diffie-Hellman 設置）！
首先註意期間 $ \omega $ 的 $ f(x_1)=b^{x_1}\bmod p $ 是順序 $ b $ 因為 $ f(0+\omega)=f(0)=1 $ 是由一個時期的一般定義所暗示的 $ \forall x\in\mathbb Z:f(x)=f(x+\omega) $ .
現在假設 $ p $ 是一個安全的素數（對於 Diffie-Hellman 來說很常見）。根據拉格朗日定理，我們知道所有乘法子群必須有順序 $ 1,2,p-1 $ 或者 $ \frac{p-1}{2} $ （的唯一除數 $ p-1 $ 通過建設 $ p $ ）。請注意，所有這 4 個值都是可以公開計算的。
現在註意到 $ f(x) $ 生成一個乘法子群 $ \mathbb Z^*_p $ （類似於生成器在 DH 中的工作方式）。因此，該子組必須具有上述 4 個可能的順序之一，我們已經知道了。因此，通過查找公鑰的順序，我們並沒有學到任何新東西。