如何測試一個數字是否是原根？
如何測試一個數字是否是一個原始根，假設 $ \text{mod}\enspace m $ 在哪裡 $ m $ 是素數？如果不？
如果數字與模數或素數互質，這還不夠嗎？
我會寫下我所做的，並想知道我是否正確：
我用 Rabin-miller 測試測試了模量是否為素數。它是素數，所以我使用 python 程序來分解 $ m-1 $ 自從 $ \phi(m) = m - 1 $ . 列印出來了 $ 2 $ 和另一個素數。所以我計算了 $ g ^ q \bmod (m-1) $ 對於所有因素 $ q $ 是因素，他們是 $ \neq 1 $ . 所以 $ g $ 應該是發電機吧？
對全部 $ m $ ， 如果 $ m $ 那麼是一個正整數
$ g $ 是一個原始的根 mod $ m $ $ ; $ 當且僅當
$ 0\leq g< m $ $ : $ 和 $ : $ $ \operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1 $ $ : $ 和 $ ;; $ 對於所有主要因素 $ q $ 的 $ \phi $ $ (m) $ , $ : g^{(\phi(m))/q} \not\equiv 1 \pmod m $ .
我假設我們是在 $ G = \mathbb{Z}_p^* $ ，我們有 $ g\in G $ ，我們要確定的順序是否 $ g $ 實際上是 $ p-1 $ .
來自練習 1.31，Silverman 和 Pipher：讓 $ a\in\mathbb{F}_p^* $ 然後讓 $ b = a^{(p-1)/q} $ . 證明要麼 $ b=1 $ 要不然 $ b $ 有訂單 $ q $ .
（此外，根據 1.33 的註釋，正好有 $ \phi(p-1) $ 原始元素。）
天真地，我會嘗試使用關於素數分解的練習結果 $ p-1 $ ，並且由於 $ a^{(p-1)/q} $ 是條款的訂單的LCM，你得到一個訂單元素 $ p-1 $ . 我不知道這是否比嘗試隨機元素和計算能力更有效 $ 1,…,p-1 $ .
編輯：看來我離得太遠了。來源：http ://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots
如果您不相信這一點，可以在 OEIS 上查找序列，參考文獻是：Burton, DM “整數模數的階數”、“素數的原始根”和“具有原始根的複合數” 。” 《初等數論》第 4 版第 8.1-8.3 節。愛荷華州迪比克：William C. Brown Publishers，第 184-205 頁，1989 年。
$$ From Jonathan Vos Post, Sep 10 2010 $$