如何在常量時間內生成無偏差的隨機bigint

Question

在我的嵌入式項目中，我有一個處理任意長度整數的biginteger類。我希望能夠在0和任意數字之間生成一個隨機bigint。假設我有一個隨機字節的質量來源。

所有我見過的實現基本上是做同樣的事情：

1. 生成正確數量的字節一個大數目，
2. 如果大於max，再次生成。

我在這個實現中看到的問題是，它可能需要很長時間。想象一下，max = 2^2049-1 =（01 FF .. FF）。該算法將生成257個字節，然後檢查最高有效字節是<=1。所以有254/256的機會需要產生一個全新的257字節的數字。在（不可能）最糟糕的情況下，這個循環可能持續數分鐘或數年。

我的問題是：
在生成的數字太大的情況下，有沒有辦法保留我已經生成的大部分字節？
重新生成最重要的字節有效嗎，還是會引入偏差？如何將結果轉換爲一位數字？

有什麼辦法可以確保時間，同時避免偏差嗎？

-

另一個邊緣情況：max = 2^2048 + 1 =（01 00 .. 01）在這種情況下，最顯著字節可爲非零值，如果剩下的字節是0，接着一個或0001。所以大多數情況下，如果MSB不爲零，則它將無效，只是重新生成該字節將永遠無法使其生效。但只是強制設置爲零似乎也是錯誤的。

Answer 1

如果您的任意最大數量是2的冪減1，那麼可以使用隨機比特的來源（例如投擲硬幣）來填充比特。這給出了一個統一分佈的數字。您可以使用高質量的RNG以32或64組的形式生成位，並截斷最後一個字而不會出現偏差。

現在，如果您的任意最大數不是2的冪減1，請使用上述技術在0..1範圍內創建均勻分數。用於分數的位數越多，結果中的偏差越小。

例如，調用任意波形最大數量M，選擇一個n使

2^n >> M /* 2^n is much greater than M */ 

現在，您的隨機數

M * (rand(2^n)/2^n) 

其中rand是在第一段上述步驟。

Answer 2

隨機數發生器創建具有整數位數的隨機數。如果這個數字是真正的統計隨機數，那麼每一位都是獨立於其他位的，你可以使用或丟棄它們的任何組合。對於你的例子，你可以簡單地扔掉7位，並有一個不偏倚的數字。

對於不是2的冪的範圍，可以將範圍的大小進行因子分解，併爲每個範圍獲取一個隨機數，然後合併它們。如果我們假設一個功能randint(n)，提供0和n-1之間不偏不倚的隨機數，一般公式爲：

(((randint(A) * B + randint(B)) * C + randint(C)) * D + randint(D)) ... 

例如，如果你的範圍爲0-10^616-1，你可以認爲因素爲5^616*2^616。

rand_10_616 = randint(5^616) * 2^616 + randint(2^616) 

很明顯，你仍然有得到公正的結果爲5^616一個問題，但它是解決一個小問題。