從同餘類集合中抽樣究竟意味著什麼？
假設一個人正在圍繞一組同餘類做一些密碼學，即：$$ \mathbb{Z}/n\mathbb{Z} = \mathbb{Z}_n = {[0]_n, [1]_m, \dots, [n-1]_n}. $$ 有時我們用來寫 $ a \leftarrow_R \mathbb{Z}_n $ 表示我們正在從 $ \mathbb{Z}_n $ . 但是，執行這樣的採樣究竟意味著什麼？我想它是以下
- 的簡寫 $ [a]_n \leftarrow_R \mathbb{Z}_n $ 加 $ a \leftarrow [a]_n $ ，即取班級代表，其中 $ 0 \leq a <n $ .
是這樣嗎？我們通常使用這個採樣數作為指數，因此對整個同餘類進行採樣是沒有意義的。
一開始我認為 $ a \leftarrow_R \mathbb{Z}_n $ 正在寫作以避免寫作 $ [a]_n \leftarrow_R \mathbb{Z}_n $ 太多次了。但這沒有意義。
也經常看到 $ \mathbb{Z}_n = {0, 1, \dots, n-1} $ . 它是其真正含義的簡寫嗎？
有時我們用來寫 $ a \leftarrow_R \mathbb{Z}_n $ 表示我們正在從 $ \mathbb{Z}_n $ . 但是，執行這樣的採樣究竟意味著什麼？
當我們談到 $ \mathbb{Z}_n $ 我們通常考慮最小剩餘系統模 $ n $ 那是整數 $ {0,1,\ldots,n-1} $
當我們寫 $ a \stackrel r\gets \mathbb{Z}_n $ 我們通常是指可能的機率過程分配，還有其他變體。
均勻採樣時應注意隨機源，簡單取模是危險的並且可能有偏差，需要丟棄。考慮您的隨機數在範圍內生成隨機數 $ [0,15] $ 你想取樣 $ \mathbb Z_{13} $ 比服用 $ \mod 13 $ 可以產生偏差，因為 13 將映射到 0，14 將映射到 1，15 將映射到 2。因此它們的採樣比其他採樣多， $ 2/16 $ 代替 $ 1/16 $ . 只需丟棄數字 $ >12 $ 並得到一個新的隨機數。
可以在最少殘留系統之外使用，例如
- 最近要求 RSA $ e > \varphi(n) $ 這仍將代表一個 $ e’ = e \bmod \varphi(n) $ ， 或者
- 可以得到私鑰 $ k $ 在 ECC 中比訂單長 $ n $ 基點的 $ G $ . 它仍然沒用，因為 $ [k]G = [k \bmod n]G $
但細節是魔鬼；在室外取樣可能會帶來一些意想不到的副作用。始終根據上下文檢查！
另一個問題；
- 我們是否僅限於最少殘留系統？
就像對手可以根據自己的優勢為所欲為一樣，我們也可以使用它。
- 例如，為了加快 gcd，我們可以允許負餘數。
- 一個人可能會跳過一個模組化減少步驟，這將導致數字不在範圍內 $ [0,n-1] $ 並且可能更高，Omura ‘90。最後，結果必須是最少的殘留物。在某些情況下，我們要求殘差為 $ (n/2,n/2] $ 因為它圍繞原點形成一個球，有助於更好地理解。
例如，當我們想使用 ElGamal 時，我們編寫 $ g^x $ ，但我們實際上在寫什麼？ $ g^x $ 或者 $ g^{[x]_q} $ .
第一個，因為我們從 $ [2,q-1] $ . 什麼時候 $ g^{[x]_q} $ 寫成這意味著 $ [x]_q $ 可以是任何一個 $ x+kq $ 在哪裡 $ k \in \mathbb Z - {0} $ .