如何找到元素 g 順序 q，給定 2 個大素數 p 和 q 其中 q|p-1
我計算了 2 個大素數， $ p $ （最少 2048 位）和 $ q $ （最少 224 位），其中 $ p-1 \mod q = 0 $ 通過使用 SageMath。
$ p = $ 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525193403303896028543209689578721838988682461578457274025662014413066681559$
$ q = $ 26959946667150639794667015087019630673637144422540572481103610249951
現在，我需要元素 $ g $ 命令 $ q $ . 我試圖找到它，但它需要很長時間（仍在執行）。任何人都知道如何找到元素 $ g $ ?
乘法組 $ \mathbf{Z}_p^* $ 非零整數模 $ p $ 是有序循環的 $ p-1 $ , 所以它只有一個階子群 $ k $ 對於每個除數 $ k $ 的 $ p-1 $ . 特別是，它只有一個順序子組 $ q $ ，由這些整數組成 $ a $ 這樣 $ a^q \bmod p = 1 $ . 讓 $ G $ 成為這個子群。
獲取元素 $ g $ 的 $ G $ , 取任意元素 $ a $ 的 $ \mathbf{Z}_p^* $ 然後讓 $ g = a^{(p-1)/q} \bmod p $ . 然後 $ g $ 是一個元素 $ G $ 因為
$$ g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p. $$ 的順序 $ g $ 是階的除數 $ G $ , 所以它是一個除數 $ q $ ，並且由於 $ q $ 是素數，它等於 $ 1 $ 或者 $ q $ . 唯一的秩序元素 $ 1 $ 是身份 $ 1 $ ， 因此，如果 $ g \not\equiv 1 \pmod p $ 你完成了。否則，請嘗試另一個 $ a $ .