如何使用偽隨機數序列提取範圍內的隨機數

我想使用 Fisher-Yates shuffle 為數組生成 PRP

$$ 1,2,3,4,5,6,7,8,9,10,11,12 $$. 我用 PRNG 的特定種子實現了 NLFSR_25bit。（用於在算法的每次迭代中提取偽隨機數）

Fisher-Yates 從區間中獲取偽隨機數（即在算法的每次迭代中 (1,i)）我如何從區間中獲取偽隨機數？（而我的 PRNG 生成一個序列而不是一個數字）

因為我的數字是

$$ 1 , …, 12 $$我想使用 NLFSR_25bit 的 4_bit lsb，然後計算4_bit_lsb%12獲取 (1,12) 之間的數字 我也會感謝其他解決方案。

如果您在區間內有一個統一的整數採樣器 $ [0, 2^k) $ ，例如 LFSR（不是很統一，但我們假設它是）或任何加密 PRNG 截斷為 $ k $ -bit 輸出，從區間內的整數中採樣的標準方法 $ [0, n) $ 什麼時候 $ n < 2^k $ 和 $ n $ 不是 2 的冪是通過拒絕採樣。

考慮減少一個整數 $ x $ 在 $ [0, 2^k) $ 模組 $ n $ , 給 $ y = x \bmod n $ . 對於每一個 $ n $ 的可能值 $ y $ , 要麼 $ \lfloor2^k/n\rfloor $ 或者 $ \lceil2^k/n\rceil $ 的可能值 $ x $ 給予 $ y $ ——也就是說，要麼 $ 2^k/n $ 四捨五入，或 $ 2^k/n $ 四捨五入，取決於是否 $ y $ 有一個“額外的”代表 $ x \geq n\cdot\lfloor2^k/n\rfloor $ .

例如，如果 $ k = 4 $ 所以 $ 2^k = 16 $ ， 而如果 $ n = 3 $ ，那麼對於 $ x \in {0,3,6,9,12,15} $ , 其中有 $ \lceil16/3\rceil = 6 $ 可能性，我們有 $ y = 0 $ . 但對於 $ x \in {1,4,7,10,13} $ 或者 $ x \in {2,5,8,11,14} $ , 其中有 $ \lfloor16/3\rfloor = 5 $ 每個可能性，我們都有 $ y = 1 $ 或者 $ y = 2 $ ， 分別。因此 $ \Pr[y = 0] = 6/16 $ ， 但 $ \Pr[y = 1] = \Pr[y = 2] = 5/16 $ .

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y =  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 *0

如果我們首先從 $ [0, 2^k) $ 隨機均勻，然後模減 $ n $ ，結果將偏向於 $ y $ 有一個額外的可能代表 $ x \geq n\cdot\lfloor2^k/n\rfloor $ ，比如代表 $ x = 15 $ 為了 $ y = 0 $ 在上面的例子中。這給出了整數的非均勻分佈 $ [0, n) $ . 這種偏差有時被稱為模偏差，儘管它發生在地圖是否來自 $ x \in [0, 2^k) $ 至 $ [0, n) $ 是 $ x \mapsto x \bmod n $ 或其他任何東西——你永遠不可能把 16 羽鴿子放進 3 個洞，而每個洞的鴿子數量相同，無論你把它們放在什麼順序。

如果我們重複地從 $ [0, 2^k) $ 均勻隨機，並拒絕其中的一些固定子集，比如 $ x = 15 $ 在上面的例子中，那麼我們可以確保唯一的一組值 $ x $ 我們將考慮將平均分成大小相等的代表集 $ y $ . 值的哪個子集並不重要 $ x $ 我們拒絕，只要他們平均分配——我們也可以拒絕 $ x = 0 $ ， 甚至 $ x = 3 $ .

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y = *0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0

一個簡單的選擇是拒絕所有的值 $ x $ 以下 $ 2^k \bmod n $ ，因為這個界限可以在 $ k $ 簡單表達式的位無符號整數運算 $ (-n) \bmod n $ ， 自從

$$ \begin{array}{} 2^k \bmod n &= 2^k \bmod n - 0 \&= 2^k \bmod n - n \bmod n \&= (2^k - n) \bmod n. \end{array} $$ 這給出了以下用於對整數進行採樣的算法 $ [0, n) $ 均勻隨機給定一個均勻隨機抽樣器，用於整數 $ [0, 2^k) $ :

1. 樣本 $ x $ 從整數中均勻隨機地 $ [0, 2^k) $ .
2. 如果 $ x < 2^k \bmod n $ ， 重來。
3. 返回 $ x \bmod n $ .

引用自：https://crypto.stackexchange.com/questions/50567