Rsa
未知順序組中的數論問題
我正在閱讀一篇論文，我正在努力理解其中的一部分。假設我們有一個小組 $ G $ 未知順序 $ n $ . 我們知道 $ B<n<B+C $ . B 和 C 都是大值）。
我們選擇一個隨機元素 $ z \in G $ . 假設我們有一些素數值 $ B+C<e_1,e_2,…,e_l $ . 我們計算 $ h=z^ {\prod_i e_i} $ .
索賠是 $ \gcd(n,\prod e_i)=1 $ （這是真的，因為每個素數都大於 $ n $ ) 我們可以說 $ h $ 均勻分佈在 $ G $ . 我們如何證明這個說法？
定義函式 $$ \begin{align} f: G&\to G\ x&\mapsto x^{\prod_i e_i} \end{align} $$ $ f $ 是內射的。證明：如果 $ f(x)=f(y) $ 然後 $ x^{\prod_i e_i}=y^{\prod_i e_i} $ ， 因此 $ (x\cdot y^{-1})^{\prod_i e_i}=1 $ ，因此順序 $ k $ 的 $ (x\cdot y^{-1}) $ 是一個除數 $ \prod_i e_i $ . 由於任何群元素的階除群階， $ k $ 也是一個除數 $ n $ . 自從 $ \gcd(n,\prod e_i)=1 $ , $ k $ 一定是 $ 1 $ . 因此 $ (x\cdot y^{-1})=1 $ ， 因此 $ x=y $ .
任何對有限集的注入都是雙射。它遵循 $ f $ 是一個雙射 $ G $ .
因此 $ h $ 被構造為均勻隨機元素的圖像 $ z $ 的 $ G $ 通過雙射 $ f $ 超過 $ G $ . 因此 $ h $ 是一個均勻隨機元素 $ G $ .