證明加法逆作為 Z*p 的生成器

讓有 $ p\ ,q $ 奇數素數，這樣 $ p=2q+1 $ .

讓存在 $ a \in Z^_p $ 以便 $ a \not= \pm 1(mod\ p) $ . 證明如果 $ a $ 不是生成器 $ Z^_p $ 然後 $ -a $ 是一個生成器 $ Z^*_p $ .

自從 $ p $ 是素數，階數 $ (\mathbb Z/p)^\ast $ 是 $ p-1=2q $ ，因此根據拉格朗日定理，每個元素必須有除階 $ 2q $ .

請注意，由於 $ \mathbb Z/p $ 是一個域，不能有其他的平方根 $ 1 $ 和 $ -1 $ ， 所以 $ a $ 不能有訂單 $ 1 $ 或者 $ 2 $ . 它也不能有訂單 $ 2q $ 因為那會使它成為發電機。所以 $ a $ 有訂單 $ q $ .

出於同樣的原因， $ -a $ 不能有訂單 $ 1 $ 或者 $ 2 $ : 這意味著 $ a $ 是一的平方根。現在如果 $ -a $ 有訂單 $ q $ ， 然後

$$ 1=(-a)^q=(-1)^qa^q=-a^q=-1 \text, $$ 一個矛盾。因此，我們必須得出結論 $ -a $ 有訂單 $ 2q $ .

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