發現XXx離散對數問題中的奇偶校驗

認為 $ p $ 是素數，並且 $ g, a\in\mathbb F_p $ 給定元素 $ g $ 一個原始根。離散對數問題提出了尋找整數的任務 $ x $ 這樣 $ g^x=a $ . 證明即使 $ x $ 無法恢復，可以檢查是否 $ x $ 通過檢查元素是奇數或偶數 $ a^{(p-1)/2} $ .

我不確定如何處理這個問題。我試過 $ g^{x(p-1)/2} = a^{(p-1)/2} = 1 $ .

任何幫助，將不勝感激！謝謝。

宣稱。 $ a^{(p-1)/2} = 1 $ 當且僅當 $ x $ 甚至。

*證明。*如果 $ x $ 是偶數，讓 $ x = 2y $ . 然後

$$ a^{(p-1)/2} = (g^x)^{(p-1)/2} = g^{2y(p-1)/2} = (g^{p-1})^y = 1^y = 1. $$ 如果 $ x $ 很奇怪，讓 $ x = 2y+1 $ . 然後

$$ a^{(p-1)/2} = g^{(2y+1)(p-1)/2} = \dots $$ （記住這裡 $ g $ 是一個生成器 $ \mathbf{F}_p^* $ ).

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