使用離散對數進行什麼模計算？
對於奇數素數 $ p $ , 我被分配了一個組 $ \mathbb{Z}_p^* $ 所有可逆元素的 $ \mathbb{Z}_p $ . 基本上， $ \mathbb{Z}_p^* = {1,2,\ldots , p-1 } $ . 我也有 $ a $ 和 $ b $ ，它們是兩個生成器 $ \mathbb{Z}_p^* $ . 我的問題是，使用離散對數進行什麼模計算 $ \mathbb{Z}_p^* $ ? 或者換句話說，它是否成立： $$ a^k \equiv b \pmod p $$ $$ k \equiv \log_a b \pmod{p} $$ 或者它是否成立： $$ a^k \equiv b \pmod{p-1} $$ $$ k \equiv \log_a b \pmod{p-1} $$
還有一個後續問題：
如果 $ \mathbb{Z}_p^* $ , $ a $ 和 $ b $ 如上所述，它是否成立，如果 $ k=\log_a b $ 然後 $ k\in \mathbb{Z}_p^* $ ?
這個問題的替代方案都不成立。
對於任何 $ n>1 $ , 和任何 $ a $ 和 $ \gcd(a,n)=1 $ , $$ a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\text{ord}_n(a)} $$
在哪裡 $ \text{ord}n(a) $ 是順序 $ a $ 在乘法組 $ \mathbb Z_n^* $ , 那是最小的 $ r\ge1 $ 和 $ a^r\equiv1\pmod n $ .
元素的順序除以組的順序，即 $ \varphi(n) $ 團體用 $ \mathbb Z_n^* $ ， 在哪裡 $ \varphi $ 是歐拉的總函式。所以 $$ k\equiv\log_a b \pmod{\varphi(n)}\quad\implies\quad a^k \equiv b \pmod n $$
什麼時候 $ a $ 是一個生成器 $ \mathbb Z_n^* $ , 可測試為 $ a^{\varphi(n)/q}\not\equiv1\bmod p $ 對於每個素數 $ q $ 劃分 $ \varphi(n) $ ，我們有 $$ a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\varphi(n)} $$
重述這一點 $ p $ , 和任何 $ a $ 和 $ a\not\equiv0\pmod p $ , $$ k\equiv\log_a b \pmod{(p-1)}\quad\implies\quad a^k \equiv b \pmod p $$ 並且，對於最低的 $ r\ge1 $ 劃分 $ p-1 $ 這樣 $ a^r\equiv1\pmod p $ , $$ a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{r} $$
什麼時候 $ a $ 是一個生成器 $ \mathbb Z_p^* $ , 可測試為 $ a^{(p-1)/q}\not\equiv1\bmod p $ 對於每個素數 $ q $ 劃分 $ (p-1) $ ，我們有 $$ a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{(p-1)} $$