我可以执行
random[0] % 201，但是0-54的数字比55-200的数字更有可能，这会使结果数字比预期的更可预测。如何使用随机八位位组字符串以创建范围为0 ... k-1（其中k为201）的数字？
#1 楼
在另一个答案中给出的方法是正确的：给定范围为$ [0，n-1] $且$ 1但是，这并不是最好的方法，正如所问的那样：它从输入字符串中消耗的能量比严格需要的更多。换句话说，当输入字符串的长度有限时，算法失败的几率会高于所需的几率。如果输入字符串中有$ m $值，则失败的几率是$（1-⌊n/k⌋⋅k/ n）^ m $。对于$ k = 201 $，$ n = 256 $，$ m = 3 $，几乎是$ 1 \％$。情况可能变得更糟：对于$ k = 129 $，$ n = 256 $，$ m = 3 $，失败几率超过$ 12 \％$。
我们可以修改算法以进行改进在那上面并删除$k≤n$的要求。
设置$ r←0 $，$ s←1 $。
从随机字符串中获取一个新的$ x $ ，设置$ r←r⋅n+ x $和$ s←s⋅n$。
如果$r≥⌊s/k⌋⋅k$，则设置$ r←r-⌊s/k⌋\ cdot k $和$ s←s-⌊s/k⌋⋅k$，然后继续执行步骤2。
输出$ y = r \ bmod k $，然后停止。
正确性证明：通过归纳法，在第2步之前和第3步之前，$ r $是一个均匀随机整数，其中$0≤r
整数$ r $和$ s $永远不会$（k-1）⋅n$，因此该算法不需要任意精度算术。对于给定的长度为$ m $的输入字符串，它将失败的可能性降到最低，从而为完全一致的输出提供最小的可能性：$（n ^ m \ bmod k）/ n ^ m $; $ k = 201 $，$ n = 256 $，$ m = 3 $等于$≈0.0009\％$（而不是$≈1\％$）;或$≈0.0007\％$（而不是$≈12\％$）来表示$ k = 129 $，$ n = 256 $，$ m = 3 $。
如果输入有效字符串包含位或具有任意数量的面的骰子卷，包括变量（只需根据从输入字符串中提取的$ x $在步骤2中更改$ n $即可。）
如果我们需要生成多个输出$ y $，则有几种选择：
最简单的方法是重新开始；但这显然不是最佳选择，尤其是在$ n≫k $时。
我们可以在第4步将“停止”更改为：“设置$ r←⌊r/k⌋$，设置$ s←⌊s/ k ⌋$（然后，如果需要，将$ k $更改为下一个输出）；然后继续执行步骤3“。结果算法仍然产生均匀分布的输出（证明草图中的递归成立），当$ n≫k $时，大大减少了输入字符串的消耗，但是我不确定最优不是最优的（对于$ k =是公然的） 2 $，$ n = 3 $）。
如果我们事先知道所需输出$ y $的数量$ j $，我们可以设置$ \ hat k = k ^ j $，在$ [0，\ hat k中生成一个$ \ hat y $制服-1] $使用最优算法，然后通过将$ \ hat y $表示为以$ j $为基数$ k $的数字来将$ \ hat y $拆分为$ j $输出。这回到了最佳状态，但不是顺序算法，并且在$ j $增长时需要使用任意精度算法，并带有$ O（j）$额外的内存。
我们可以使用几批$ j生成任意数量的输出。和前面的调整一样，但是使用了上述次优的顺序算法。这允许使用有限的额外内存，并且随着$ \ hat k = k ^ j $的增长而接近最优。但这不是顺序算法。
我现在倾向于相信，在某些最坏的情况下，任何最佳算法都必然需要$ O（\ log m）$额外的内存。但是，可以使用有限的额外内存（比上面的内存少得多，并且更接近最优）来制作顺序算法。我打算详细介绍这种算法（如果其他人找到了参考文献，或者有合适的算法，请告诉我们！）。
#2 楼
一个简单的方法是使用小于201的数字，如果不是，则丢弃该数字（移至下一个字节）。如果字节为：
由于该序列是随机的，因此原始序列中每个数字的每个可能值都有概率$ \ frac {1} {256} $。因此，在任何给定点，下一个字节将为$ k \ leq200 $的概率也为$ p_0 = \ frac {1} {256} $。
但是，该字节的概率$ \ frac {55} {256} $将被丢弃。因此，数字是独立的，第二个字节为我们提供数字$ k $的概率为$ p_1 = \ frac {55} {256} \ cdot \ frac {1} {256} $。
继续这种推理，将丢弃前$ j $个字节而下一个字节为$ k $的概率为$ p_j = \ left（\ frac {55} {256} \ right ）\ cdot \ frac {1} {256} $。因此，下一个导出数字为42的概率为$$ p = p_0 + p_1 + p_2 + \ cdots = \ sum_ {n = 0} ^ {+ \ infty} \ left（\ frac {55} {256} \右）^ n \ cdot \ frac {1} {256}。$$
这是一个几何级数，概率为$$ p = \ frac {1} {1- \ frac { 55} {256}} \ cdot \ frac {1} {256} = \ frac {1} {\ frac {201} {256}} \ cdot \ frac {1} {256} = \ frac {256} {201 } \ cdot \ frac {1} {256} = \ frac {1} {201}。$$
由于这对于$ k $的201个可能值中的每一个均成立，因此派生序列为
通常，如果您的RNG输出数字$ x \ in \ {0，\ cdots，n-1 \} $，则需要推导数字$ y \ in \的随机序列{0，\ cdots，k-1 \} $，如果$ x <\ left \ lfloor \ frac {n} {k} \ right \ rfloor \ cdot k $并丢弃，则可以取$ y = x \ bmod k $ $ x $否则。
由于$ \ left \ lfloor \ frac {n} {k} \ right \ rfloor \ cdot k $是$ k $的整数倍，所以没有偏差。 br />
评论
$ \ begingroup $
您能不能再说几句为什么是真的？这对于OP可能具有附加价值，尤其是在密码学中，除非您有证明或可靠的参考，否则您不希望将任何事情视为理所当然。
$ \ endgroup $
–托马斯
2012年12月15日17:08
$ \ begingroup $
@Thomas：我以这个前提为前提，因为随机序列的数字应该是完全独立的，所以我们使用哪个数字（和顺序）都无关紧要。但是除了引号之外，随机序列的每个可命名子序列也应该从Infinity和思维方式（几乎不是固态密码学）中是随机的，我找不到任何参考。
$ \ endgroup $
–丹尼斯
2012-12-15 17:24
$ \ begingroup $
是的，是的，序列中的每个数字都是独立的，但是对于几乎不知道为什么丢弃一个数字并尝试下一个（独立的）数字是有效策略的概率来说，这可能不是立即显而易见的。我正是这个意思。顺便说一句，您是否用X <（N / K）* K作错字？我认为您的意思是X
–托马斯
2012年12月15日17:39
$ \ begingroup $
我认为您是对的Thomas，因为打错了字。有了（N / K）* K，K会互相抵消，而您剩下N，X已经可以保证小于。
$ \ endgroup $
– Neubert
2012年12月15日19:10
$ \ begingroup $
@Thomas：我明白你的意思。当我有更多时间时，我将对此进行扩展。 X <（N / K）* K的除法为整数除法。如果我们对小于100的整数感兴趣，则可以使用所有X，使得X <（256/100）* 100 = 2 * 100 =200。如果X
–丹尼斯
2012年12月15日20:34
#3 楼
fgrieu的答案一如既往地好。但是，我只想记录一个替代方法。因此，某些标准（例如NIST的公钥标准FIPS 186-4：数字签名标准）允许生成随机数，其中会生成一些额外的八位位组以减少（但不能完全消除）偏差。根据该文件的公式B.1.2，对于要在DSA算法（公用公钥标准）中使用的密钥的生成，认为小于$ 1/2 ^ {64} $的偏差是可以接受的。
换句话说，不是生成仅八（8）位，而是生成至少76位，然后使用模运算。偏差将足够小，以至于在很多情况下都看不到（至少在生成的随机数不是很大的情况下）。
接受一些偏差的好处是输入的数量所需的位是确定性的，因此可以避免最坏的情况，即在产生输出之前需要一定数量的随机位。
所以到最后，您可以这样做：
random [0 ... 8]％201
评论
$ \ begingroup $
这似乎与我的新答案中所述的NIST SP 800-90附录A.5.3中的简单模块化方法相同。请注意，您的确必须生成9字节的偏差小于六十分之一的字节。
$ \ endgroup $
–马腾·博德威斯♦
17年8月1日14:27
$ \ begingroup $
NIST和FIPS文档由同一组织提供。这些公式确实是相同的。
$ \ endgroup $
–user4982
17年8月3日，12：46
#4 楼
NIST SP 800-90中提出了多种将位/八位字节串转换为随机数的经过测试的方法：建议使用确定性随机位生成器生成随机数。它们在附录A.5中定义：A.5.1，简单丢弃方法：生成最小$ m $位的值，直到得到一个小于$ r $-唯一最大值（即，丹尼斯在此处的答案中描述的方法）；
A.5.2，复杂丢弃方法：生成大量随机数的复杂方法
A.5.3，简单模块化方法：比最小位数$ m $多生成至少64位，然后返回该值除以$ r $（会出现一些偏差；您也可以将其与简单的丢弃方法结合使用，使其无偏但不确定）。
显然，您可以添加/减去一个恒定值$ x $，如果您想使用$ [x..n + x）$而不是$ [0..n）$。
评论
$ \ begingroup $
我认为简单的模块化方法与fgrieu给出的答案相似。该问题还为其他数学问题math.stackexchange.com/questions/1314460/…提供了答案。
$ \ endgroup $
–丹尼尔
17年8月1日在13:10
#5 楼
尝试使用位掩码。例如-M是您想要的上限，因此使用r？评论
$ \ begingroup $
感谢您的参与，但这还不够。这样只能导出$ 2 ^ y $的值，对于那些值，您只需$ y $位即可。除法不适用于位，不能有部分位。
$ \ endgroup $
–马腾·博德威斯♦
2015年3月18日在16:09
评论
$ \ begingroup $
我不知道这应该如何工作。假设k = 140，n = 256，第一个x =139。它会至少循环一次，然后每个pastebin.com/zHxm9LD6。看起来似乎根本不应该循环播放，但是，因为139 <140 ...
$ \ endgroup $
– paynes_bay
13年8月2日在20:24
$ \ begingroup $
没关系。.floor（s / k）* k == floor（256/140）* 140 == 140-不是1。
$ \ endgroup $
– paynes_bay
13年8月2日在22:26
$ \ begingroup $
最佳解决方案在概念上与算术编码类似，并且原则上您可以具有O（1）的存储要求用于处理（当然，O（log k）也可以存储输出）。
$ \ endgroup $
–尼尔·斯莱特（Neil Slater）
15年3月18日在15:49
$ \ begingroup $
@Neil Slater：算术编码确实可以达到最优，或者使用O（1）内存并且很实用。但是，除非出错，否则使用O（1）内存进行算术编码可能会遇到比最佳算术编码需要更多位的情况。
$ \ endgroup $
–fgrieu♦
15年3月18日在15:58
$ \ begingroup $
@fgrieu：实际上，我阅读它已经很长时间了。有几个简单的状态标志，但是现在您提到它，可能会有更多状态标志-我可能忘记了如何隐含模糊的值的递归分辨率。以前实现它时我很懒，只是使用大型整数库来避免所有位改组。
$ \ endgroup $
–尼尔·斯莱特（Neil Slater）
15年3月18日在16:10