關於離散對數基公式變化的證明問題
我正在查看這篇論文中離散對數的基本公式變化的證明（第 6 頁，第 4 個項目符號縮進）。
在引言中，論文指出：
讓 $ F_q $ 是有限的有序域 $ q $ ， 在哪裡 $ q=p^n $ ( $ p $ 素數），並讓 $ F_q^* = F_q -{0} $ . 給定 $ g $ , 的原始元素 $ F_q $ , 和任意 $ y\in F_q^* $ , 的離散對數 $ y $ 根據 $ g $ 定義為 $$ \log_g y = x \iff g^x=y \text{ in } F_q \text{ and } 0\leq x\leq q-2. $$
然後論文作者證明了離散對數基公式的變化：
認為 $ \Gamma $ 是另一個原始元素 $ F_q $ 我們知道 $ \log_g \Gamma = \gamma $ .
$ \Gamma $ 和 $ g $ 既原始 $ \implies \gcd(\gamma , q-1)=1 $
$ \implies \exists \overline\gamma $ 這樣 $ \gamma \overline\gamma \equiv 1 \pmod{q-1} \implies g=\Gamma ^{\overline\gamma} $ 在 $ F_q $ .
所以 $ \log_g y = x \iff y = g^x = \Gamma ^{\overline\gamma x} $ 在 $ F_q \iff \log_\Gamma y \equiv \overline\gamma x \pmod{q-1} $ .
將最後一個同餘乘以 $ \gamma $ 給 $ \log_g y \equiv \log_g \Gamma \cdot \log_\Gamma y \pmod{q-1} $ .
我的問題是，為什麼以下成立（從證明的開始）： $$ g \text{ and } \Gamma \text{ both primitive element of } F_q \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1 $$
證明：
$$ g \text{ and } \Gamma \text{ both primitive element of } F_q^* \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1 $$
有限域中的原始元素意味著它是一個生成器，即 $ \langle g\rangle = GF(q) = F_q^* $ .
讓 $ g \text{ and } \Gamma $ 都是原始元素 $ GF(q) $ . 通過使用對立面，我們將達到相反的效果。
假使，假設 $ \gcd(\gamma , q-1) = d \neq 1 $ 在哪裡 $ \log_g \Gamma =\gamma $ .
我們可以這麼說 $ \gamma = d \cdot k $ 對於一些非負整數 $ k $ 和 $ q-1 = d \cdot t $ . $ (q-1) \cdot t = \lambda \cdot k $ . 所以; $ \lambda = \frac{(q-1)\cdot t}{k} $
$ \log_g \Gamma =\gamma $ 方法 $ \Gamma = g^\gamma $ 現在，
$$ \begin{align} \Gamma &= g^\frac{(q-1)\cdot t}{k} && ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\ \Gamma^{k} &= g^{(q-1)\cdot t} && ;\text{take } kth \text{ power}\ \Gamma^{k} &= 1^t \ \end{align} $$
清楚地， $ k < q-1 $ 但我們發現了一種力量 $ k $ 發電機 $ \Gamma $ 這樣 $ \Gamma^{k} = 1 $ 這個意思 $ \Gamma $ 不是原始元素。這證明了這個說法。
讓 $ a $ 是一個組的一個元素，並且 $ o(a) $ 成為 $ a $ 在組中。這是一個容易證明的問題 $ o(a^r) = \frac{o(a)}{gcd(o(a),r)} $ . 因此 $ a $ 和 $ a^r $ 生成相同的組iff $ gcd(o(a),r)=1 $ . 現在您可以通過以下方式設置組 $ F^{\ast} $ 和 $ q-1 $ 元素和 $ a $ 它的生成器。