Prime-Numbers
找到具有第 n 個單位根的素數域
我怎樣才能找到最小的素數 $ p $ ，這樣的場 $ GF(p) $ 有 $ n $ - 統一的根源？
例如，我知道對於 $ p=2^{256} - 351 \times 2^{32} + 1 $ 有統一的根源 $ n=2^{32} $ . 但是不知道有沒有更小的 $ p $ 對於統一的根，或者如何找到最小的素數，這將具有相同的“順序” $ p $ 對於特定的 $ n $ .
如果它讓事情變得更容易，為了我的目的， $ n $ 永遠是一種力量 $ 2 $ .
我怎樣才能找到最小的素數 $ p $ ，這樣的場 $ GF(p) $ 有 $ n $ - 統一的根源？
形式的任何素數 $ kn + 1 $ 有 $ n $ - 統一的根源；我們知道這一點，因為該組 $ \mathbb{Z}_p^* $ （對於素數 $ p $ ) 是有序的循環群 $ p-1 $ ，因此對於所有的因素 $ p-1 $ ， 包含 $ (p-1)/k $ ，它具有該順序的元素（至少，如果您不計算 $ p $ 其中有 $ 2^{31} $ 統一的根源，但不是秩序的要素 $ 2^{32} $ )
快速搜尋表明 $ 18 \cdot 2^{32} + 1 = 77309411329 $ 是該形式的最小素數，因此這就是您的答案。
快速計算表明 $ 45467087722 ^ {2^{32}} \equiv 1 \pmod{77309411329} $ ，也就是說，它是一個 $ 2^{32} $ 統一的根（更具體地說，它有秩序 $ 2^{32} $ )