隨機化素數場元素
我需要我的程式碼來生成隨機元素 $ GF(p) $ ( $ F_p $ 或者 $ Z_p $ ，如果你願意）。
我可用的 Crypto API 提供了一個帶有隨機位串的 API。為了滿足我的需求，我可以想到兩種可能的解決方案，每種都有其缺點。
*解決方案 1：*樣品 $ \lceil\log_2p\rceil $ 位，並減少其對應的整數模 $ p $ 或者 $ 2^{\lfloor\log_2p\rfloor} $ . 這是有效且容易的，但產生的分佈並不均勻。
*解決方案 2：*重複採樣 $ \lceil\log_2p\rceil $ 位直到輸出整數小於 $ p $ . 這給出了一個很好的均勻分佈，但不是恆定的時間，並且可能會洩漏一些關於隨機發生器內部的東西。
這些是一個好主意，還是另一種常用的方法？
*編輯：*接受的答案適用於任何大小（不一定是素數）的任何元素集（不一定是欄位）。
是另一種常用的方法嗎？
樣本 $ \lceil \log_2p \rceil+64 $ 位，並減少其對應的整數模 $ p $ .
仍然會有偏差，但它很小。而且，假設您使用恆定時間模運算，它是恆定時間……
嗨@AryaPourtababaie
我一直有完全相同的問題，並想找到一種方法來生成統計上接近均勻的分佈 $ F_p $ . 這是我對上述方案的分析。
我有一個素數 $ p $ 和具有長度的隨機字元串 $ n $ . 讓 $ S = {0,1}^n $ 並定義函式
$ H : S \rightarrow F_p, ~~~ H(x) \mapsto x \bmod p $
定義 $ U_p $ 成為均勻分佈 $ F_p $ ， 然後讓 $ H_p $ 表示輸出的分佈 $ H $ 當其輸入均勻分佈時。
我想計算之間的統計距離 $ U_p $ 和 $ H_p $ , $ \Delta(U_p, H_p) $ .
觀察如果 $ p $ 均分 $ S $ ，那麼所有殘基類將具有相同數量的元素，即 $ |S|/p $ . 但是因為 $ p $ 是一個大素數並且 $ S $ 是一種力量 $ 2 $ , 永遠不會是這樣。將有一組殘基比其他殘基多被擊中一次，即那些小於 $ |S| \bmod p $ . 為了計算統計距離，計算這些殘基在兩個分佈中的機率差異就足夠了。
定義： $ m = |S| \bmod p $
$ k = \lfloor ~|S|/p~ \rfloor $
我們可以分區 $ F_p $ 分兩組：
$ A = {0, \ldots, m-1} $
$ B = {m, \ldots, p-1} $
中的殘留物 $ A $ 每個都由 $ k+1 $ 要點 $ S $ , 而殘留在 $ B $ 由產生 $ k $ 元素。你可以看到
$ U_p(x) < H_p(x), \mbox{ for } x \in A $
$ U_p(x) > H_p(x), \mbox{ for } x \in B $
具體來說：
$ U_p(x) = 1/p $
$ H_p(x | x \in A) = (k+1)/|S| $
$ H_p(x | x \in B) = k/|S| $
然後，
$ \Delta(U_p, H_p) = \Pr_{H_p}(A) - \Pr_{U_p}(A) = m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right) $
關鍵部分是這樣的：
$ m \cdot \left(\frac{k+1}{|S|} - \frac{1}{p} \right) \leq $
$ m \cdot \left(\frac{|S|/p + 1}{|S|} - \frac{1}{p} \right) = $
$ (|S| \bmod p) \cdot \frac{1}{|S|} < $
$ \frac{p}{|S|} $
現在你可以看到，如果你修復你的 $ p $ ，您可以使用所需的位串長度。如果您使用大小相似的隨機字元串 $ p $ ，您可能不會獲得相當小的距離。但是@poncho 的建議將保證您最多 $ 2^{-64} $ 統計距離，你可以控制你能得到多低。
例如，對於標準雜湊長度，您有 224、256、384、512。例如，對於 256 位左右的素數，下一個雜湊長度為 384，您得到的統計距離最多為 $ 2^{-128} $ 按照今天的標準，這是非常安全的。