node.js - Node : Generate 6 digits random number using crypto. randomBytes

Question

由于 1000000 不是 2 的幂，因此随机生成从 0 到 999999 的精确值的正确方法是什么？

这是我的方法:

1. 使用crypto.randomBytes生成3个字节并转换为hex
2. 使用前 5 个字符转换为整数(最大为 fffff == 1048575 > 999999)
3. 如果结果>999999，重新从第1步开始

它将以某种方式创建一个递归函数。逻辑上是否正确，是否会引起性能问题？

Answer 1

有几种方法可以从随机位中提取一定范围内的随机数。 NIST Special Publication 800-90A revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators 中描述了一些常见的

尽管此标准是关于确定性随机位生成的，但有一个名为A.5 将随机位转换 为随机数的有用附录，其中描述了三种有用的方法。

描述的方法是:

• A.5.1 简单丢弃法
• A.5.2 复杂丢弃法
• A.5.3 简单模块化方法

前两个在运行时间方面不是确定性的，而是生成一个完全没有偏差的数字。它们基于拒绝抽样。

复杂的丢弃方法讨论了一种更优化的方案，用于生成一个范围内的大量随机数。我认为它对于几乎任何正常使用来说都太复杂了；如果您需要额外的效率，我会看看下面描述的优化简单丢弃方法。

简单模块化方法是时间常数和确定性的，但具有非零(但可忽略)偏差。但是，它需要相对大量的额外随机性才能实现可忽略的偏差；基本上要有 2^128 分之一的偏差，你需要在所需范围的位大小之上增加 128 位。对于较小的数字，这可能不是选择的方法。

您的算法显然是简单丢弃法(通常称为“拒绝抽样”)的一个版本，所以没问题。

---

我自己想到了一种基于简单丢弃方法的非常有效的算法，称为 "Optimized Simple Discard Method" or RNG-BC其中“BC”代表“二进制比较”。它基于这样的观察，即比较只查看最高有效位，这意味着最低有效位仍应被视为随机的，因此可以重复使用。请注意，此方法尚未经过正式同行评审；我确实提供了与简单丢弃法等价的非正式证明。

---

当然，您应该使用通用方法，它在给定任何 N 值的情况下都很有效。在这种情况下，复杂丢弃法或简单模块法应优先考虑简单丢弃法。还有其他更复杂、效率更高的算法，但通常使用这两种算法中的任何一种都没有问题。

请注意，在 [0, N) 范围内生成随机数时，首先检查 N 是否为 2 的幂通常是有益的。如果 N 是 2 的幂，那么就没有必要使用任何这些可能昂贵的计算；只需使用来自随机位或字节生成器的所需位即可。