如何從乘法組 Zn* 中隨機選擇元素
我正在解決一個問題，其中我有兩個大的安全素數
p，並q隨機選擇 512 位中的每一個。我已經使用 OpenSSL 庫生成了這些安全素數。現在，n = pq
Zn* 將被稱為什麼？它是乘法模n下的一個群，與 相同
(Z/nZ)*嗎？但是我讀過 (Zn,⋅)，在乘法下以 n 為模的整數，當且僅當 n 是素數時是一個群？ 在這個連結如果這完全是一個組，那麼什麼都包含該組的元素？有沒有辦法使用 Openssl 之類的庫使用 C/C++ 中的程式碼隨機選擇其元素。
謝謝並恭祝安康。
$ (\mathbb Z_n,+,\cdot) $ 和 $ (\mathbb Z/n\mathbb Z,+,\cdot) $ 都表示加法和乘法模下的整數環 $ n $ ，每個可能不同但最終等效的結構。這套有 $ n $ 元素。
$ \mathbb Z_n^* $ 和 $ (\mathbb Z/n\mathbb Z)^* $ 兩者都表示所述集合的元素的子集，其在乘法模下具有逆 $ n $ （或等效地，最大公約數與 $ n $ 是 1)。它在乘法模下形成一個群 $ n $ .
戒指 $ (\mathbb Z_n,+,\cdot) $ 是一個欄位當且僅當 $ n $ 是素數，在這種情況下 $ \mathbb Z_n^* $ 簡直就是 $ \mathbb Z_n-{0} $ .
根據定義， $ x $ 在 $ \mathbb Z_n $ 屬於 $ \mathbb Z_n^* $ 當且僅當 $ x $ 有一個乘法逆元 $ y $ , 就是這樣 $ x,y\equiv1\pmod n $ （或等效地，當且僅當 $ \gcd(x,n)=1 $ ）。什麼時候 $ n=p,q $ 和 $ p $ 和 $ q $ 素數，這是當且僅當 $ x $ 是這樣的 $ x\ne0\pmod p $ 和 $ x\ne0\pmod q $ . 套裝 $ \mathbb Z_n^* $ 有 $ \varphi(n) $ 元素，其中 $ \varphi $ 是歐拉的總函式。如果 $ p\ne q $ ， 然後 $ \mathbb Z_n^* $ 是的集合 $ \varphi(n)=(p-1)(q-1) $ 要點 $ \mathbb Z_n $ 兩者都不能整除 $ p $ 也不 $ q $ . 如果 $ p=q $ ， 然後 $ \mathbb Z_n^* $ 是的集合 $ \varphi(n)=p(p-1) $ 要點 $ \mathbb Z_n $ 不能被 $ p $ .
我們可以得到一個均勻隨機的元素 $ \mathbb Z_n^* $ 在幾個方面：
啟發式：生成一個均勻隨機的整數 $ x $ 在 $ \mathbb Z_n $ （這是一個均勻隨機整數 $ [0,n) $ ） 直到 $ x $ 不能被任何一個整除 $ p $ 也不 $ q $ （如果在實踐中幾乎可以肯定，如果 $ p $ 和 $ q $ 很大）。我們可以等效地測試如果 $ \gcd(x,n)=1 $ 使用歐幾里得或二進制 GCD算法，優點是我們不需要分解 $ n $ . 此外，我們也可以生成 $ x $ 在 $ [1,n) $ 在測試之前，因為我們會消除 $ x=0 $ 反正。
建設性地：生成一個均勻隨機的整數 $ u $ 在 $ [1,p) $ ， 和
- 如果 $ q\ne p $ 生成一個均勻隨機整數 $ v $ 在 $ [1,q) $ , 和形式 $ x $ 在 $ [0,n) $ 和 $ x\equiv u\pmod p $ 和 $ y\equiv v\pmod q $ 由中國剩餘定理；例如，作為 $ x=(q^{-1}(u-v)\bmod p)q+v $ .
- 如果 $ q=p $ 生成一個均勻隨機整數 $ m $ 在 $ [0,p) $ , 和形式 $ x=m,p+u $ .