钻头
PDF零容忍偏差
Terence Kelly
公正的随机选择出奇地棘手。公平性的组合数学尤其令人困惑，而且在洗牌中，其后果也格外重大。洗牌一组元素意味着随机选择其元素的有序序列。例如，洗牌 {A,B,C} 意味着以相等的概率选择以下排列之一：
高风险
洗牌对于广泛的重要应用至关重要。洗牌氨基酸序列是生物信息学中随机化的主要和基本用途。[12] 洗牌默认网络浏览器选项可以解决反垄断打击。[32] 在线扑克网站洗牌虚拟扑克牌，每年收入 600 亿美元。[9] 当美国征兵抽签洗牌生日以征召公民服兵役时，风险最高：20 世纪的战争造成超过 60 万美国人丧生，1600 万美国应征入伍者参加了这些战争。
– Curtis W. Tarr，兵役局局长，1970 年 6 月[25]
在可能失去衬衫和生命的地方，公平性至关重要。在 1969 年的征兵抽签中，由于漫不经心的洗牌导致 12 月生日的人获得了过多的热带假期，公众的愤怒迫使进行了改革。[26,29] 由此产生的串联洗牌协议从单独的混合机中抽取成对的标记弹珠，一个用于生日，另一个用于征兵顺序号[25,28]。如今，洗牌通常是计算机化的，但这不能成为偏差的借口。例如，赌博法规要求虚拟游戏中的数学概率与其物理对应物中的概率相匹配。[21] 公平性不仅仅是一个好主意，它还是法律。
尽管洗牌的概念很简单，公平性也很重要，但糟糕的建议和有缺陷的代码却比比皆是。看似受人尊敬的权威机构在几十年里一直搞砸洗牌。糟糕的洗牌代码的糟糕之处在于，它通常在常规测试中看起来工作正常。真正做到正确需要仔细推理随机选择的组合数学。
这就是我们将要学习的内容。我们将从剖析一个精心策划的、博物馆级别的笨拙洗牌方法大全开始——来自一本历史悠久的编程教科书。然后，我们将开发一个正确的洗牌程序，该程序可以扩展到远远超出玩具规模的问题，同时避免偏差。最后，我们将考虑如何获得所有随机选择算法所需的随机数。我们沿途积累的心理清单将使我们能够审计现成的解决方案。最终，我们将看到，公正的洗牌非常容易，几乎没有理由以其他方式进行。
参见“如何不编程”
图 1 中简洁的 C 程序总结了广泛存在的洗牌错误。它至少包含三种不同的偏差和几个其他可疑的特征。您很少会遇到缺陷密度如此高的代码。
图 1：充满错误的洗牌
“这是一个机会游戏吗？”
老千：“不是我玩的方式。”
– W.C. Fields，《My Little Chickadee》
图 1 的第 6 行容易出现模偏差。程序员想要一个均匀分布在零和 N−1 之间的随机数，但 rand() % N 并不能保证均匀性。图 2 展示了模偏差的惊人不公平性。程序员天真地期望图 2 的第 4 行中的 rand() % N < N/2 评估为 true 的频率与 false 的频率相同，但由于模偏差，它评估为 true 的频率是 false 的两倍。如此倾斜的赔率会在旧西部的赌场引发枪战，在现代赌场引发诉讼。
图 2：模偏差传递极端不均匀性
图 1 的另一个问题是使用了标准 C 伪随机数生成器 (PRNG)，这本身就是一个错误，因为 rand() 经常被实现得很糟糕。[23] 没有什么可以阻止这种传统持续下去；最新的 C 标准明确认可过时的实现。[14] 更糟糕的是，rand() 的经典缺陷与 rand() % N 反模式相互作用不良：如果 N 是 2、4 或 8 等小的 2 的幂，则 rand() % N 会产生 rand() 返回值的低位。不幸的是，许多糟糕的实现在低位中提供特别差的随机性。[23] 例如，在过去的一些商业 Unix 系统上，连续调用 rand() % 2 会返回 0,1,0,1,0,1,... 无限循环。糟糕的低位随机性会影响图 1 中第 6 行的几次迭代。
除了涉及 PRNG 误用的通用错误外，图 1 的程序还包含两个更严重的特定于洗牌的偏差。
第一个是洗牌偏差。第 6 行和第 7 行访问 A[] 中的每个元素，并将其与从整个数组中随机选择的元素交换。图 3 通过逐步分析以这种方式洗牌 {A,B,C} 的结果树来解释洗牌偏差。分支代表公平的随机交换，右侧的叶子代表结果，所有结果都是等可能的。请注意，某些排列的出现频率高于其他排列。例如，BAC 出现五次，但 CAB 仅出现四次。八个结果以 C 开头，九个以 A 开头，十个以 B 开头。根本问题是洗牌结果和排列之间不匹配。应用于 N 个项目时，图 1 的有偏差的洗牌产生 NN 个结果，每个结果都是 N! 个排列之一。但是对于任何 N，N! 都不能整除 NN
图 3：N = 3 个项目的有偏差的洗牌的结果树
图 1 中的第二个特定于洗牌的偏差，第 4 行的种子偏差，具有相似的味道，但后果更可怕。PRNG 种子的数量，对于srand() 种子可以生成少于 13! 个结果。对于扑克来说，这是绝望的，因为 52! > 2225。即使是 128 位种子也不足以用于扑克：可以生成的排列的分数小于 2128 / 2225 = 1 / 297，即 1 / 158,456,325,028,528,675,187,087,900,672。公正的洗牌意味着所有排列都是等可能的，直到一个排列的选择仅由外生的真随机熵决定（即，种子，如果我们使用基于 PRNG 的洗牌器）。然而，使用小种子的 PRNG 的洗牌器，在种子熵提供之前，任意地使几乎所有排列都不可能。
对于扑克等安全至上的应用，图 1 至少包含两个漏洞，除了使用非加密安全的 PRNG 之外。首先，Unix 纪元时间是一个相当可预测的 PRNG 种子（第 4 行），这可能允许作弊者猜测种子并计算生成的洗牌。其次，小的 32 位种子空间使任何人都可以预先计算所有可能牌组的查找表，这反过来又允许作弊者从自己的手牌中推断出牌组的状态。类似的漏洞困扰着一个流行的西洋双陆棋程序[24]，并允许成功攻击商业扑克软件。[31]
值得注意的是，图 1 的所有弊病都困扰着一本著名的教科书系列中的洗牌代码。这个系列拥有信誉良好的出版商、自豪的常春藤盟校学历的作者以及跨越三十年的九个昂贵的版本，没有明显的危险信号。然而，来自 1990 年代中期的第二版建议使用 rand() % N 将随机数缩放到所需的范围，并提供了带有模偏差、洗牌偏差、种子偏差和前面提到的其他问题的洗牌代码。最近的第九版部分解决了其中一些但不是全部缺陷。它的洗牌代码与第二版类似，但它指出了洗牌偏差，并邀请读者自行研究公正的洗牌。它还提到了标准 C rand() 的质量差，并建议在严肃的用途中使用更好的 PRNG。然而，最新版本没有提到种子偏差，它继续推荐 rand() % N，但没有提到模偏差，也没有提到 srand(time(NULL)) 的可预测性。
可悲的是，没有人垄断坏代码或坏建议。即使在面临高风险的富裕玩家中，混乱也很普遍。微软搞砸了本应成为其摆脱反垄断麻烦的门票的洗牌。[32] 官方 Java 文档将 PRNG 的周期（输出流重复之前的调用次数）与种子偏差的原因或补救措施混淆了
对于生成大型排列的应用，请考虑一个周期远大于可能的排列总数的生成器；否则，将不可能生成某些预期的排列。例如，如果目标是洗牌一副 52 张牌，则可能的排列数为 52! (52 阶乘)，约为 2225.58，因此最好使用周期约为 2256 或更大的生成器....[4]
这是误导和不相关的。长周期并不能排除偏差，并且在不重新播种的情况下多次洗牌会增加所需种子的尺寸。例如，某些“梅森旋转器”PRNG 的周期远大于 2256，但它们接受 64 位种子。因此，使用这些 PRNG 的洗牌器在播种后的第一次洗牌中最多产生 264 种不同的结果，这小于 21!。对于超出玩具规模的问题，尽管周期很长，但严重的偏差是不可避免的。当今的一些现成 PRNG 可以接受大约 20,000 位长的种子，但 220000 小于 2087!。一百万个项目的单次公正洗牌涉及超过 1800 万位的熵。此外，重复洗牌会增加熵需求：一系列 J 次独立的 N 项公正洗牌可以有 (N!)J 种可能的结果，所有结果都必须是等概率的。因此，该系列至少需要 log2((N!)J) 位的输入熵，这比单次洗牌所需的多 J 倍。
正确的洗牌
洗牌偏差在 1964 年变得过时了——比前面讨论的有缺陷的教科书系列早三十年——当时 Durstenfeld 发表了一种公正的算法来就地洗牌数组。[8] 基本思想很简单直观，反映了阶乘的定义：反复将从不断减少的未选择项目池中以均匀概率选择的项目附加到输出序列。绘制 Durstenfeld 算法的结果树，就像图 3 中错误的洗牌一样，您将得到正好 N! 个不同的叶子。
为了等概率，Durstenfeld 算法中的项目选择必须避免模偏差。消除模偏差的关键是拒绝：丢弃如果映射到所需范围会导致偏差的随机数。例如，要使用六面骰子在四个备选项中公平选择，请掷骰子直到结果在 [1..4] 范围内。丢弃 5 或 6，因为将这些坏值确定性地映射到可接受的范围会引入偏差。拒绝坏值以丢弃随机数为代价确保公平性。下面使用的简单拒绝方法最多可能使消耗的随机数预期数量增加一倍；在实践中，成本通常要低得多。
图 4 显示了一个完整的洗牌程序，该程序围绕 Durstenfeld 算法的变体构建。第 16-18 行的洗牌循环通过将随机未选择的条目交换到每个位置来从左到右填充数组 A[]。循环不变式是小于 i 的数组条目包含 A[] 的等概率选择和等概率排列的子集。未选择的条目在第 17 行由函数 U() 随机选择，U() 是 random_number % range 的替代品，它使用拒绝来避免偏差。
图 4：公正的洗牌程序
第 4 行到第 11 行的 U() 的主体值得仔细研究。U() 接受一个 64 位参数 K，该参数必须位于 [1..232] 中，这是在第 6 行强制执行的限制。长参数允许调用者自由地表达缩放 32 位随机数的各种合理方式：U(1) 返回零；U(232) 返回原始（未缩放的）随机数；K 参数的任何其他值都返回均匀分布在K 参数是一个 32 位数字，则请求原始随机数将是不可能的。
第 7 行从 stdin 中吸取原始 32 位随机数。有时，性能或其他考虑因素建议硬连线特定的随机数源或固定的源菜单。然而，将选择推迟到运行时更灵活且面向未来。这就是为什么 GNU 命令行洗牌实用程序 "shuf" 提供从文件或管道读取随机数的选项。用户可以提供他们想要的任何随机位。
图 4 第 9 行的拒绝阈值接受尽可能多的随机数，同时确保第 10 行的模运算产生公正的返回值。如果随机数 R 是从 K 均匀整除（没有余数）的范围中均匀概率抽取的，则是可接受的，因为那时 R % K 是公正的。变量 M 等于 232（第 5 行）。由于整数除法会截断，因此第 9 行的 M / K 是完整的K * (M / K) 的整数范围可以被 K 整除；此范围之外的任何 R 都必须拒绝。
图 4 的方法不是唯一一种无偏差洗牌的方法。我们可以实现范围内的整数之间的一一对应关系unpack”程序中实现。最后，在计算机化不是硬性要求的情况下，不要忽视物理洗牌的选项。赌场和彩票继续出于充分的理由使用物理随机选择。
随机性从何而来？
诸如图 4 的洗牌器之类的随机选择算法需要随机数。我们如何获得合适的随机数？
伪随机数生成器对于许多目的很有用，但公正的洗牌不是其中之一。PRNG 的目的是将少量真随机熵“拉伸”为大量的伪随机位，如果真正的熵很昂贵并且拉伸没有危害，这是合理的。但是正如我们所见，基于 PRNG 的洗牌器容易受到偏差的影响，偏差是由 PRNG 种子的数量与排列的数量不匹配引起的。本文档的示例代码中包含的注释中更详细地回顾了这些以及其他基于 PRNG 的洗牌的基本问题。如果我们不使用 PRNG，那么我们就不必担心令人眼花缭乱的种子偏差组合数学和 PRNG 的曲折历史。[15,20,23]
公正的洗牌器可以直接消耗真随机位，并且所需的随机数数量很容易计算。例如，图 4 的程序在洗牌最多 232 个项目时，预计每个项目最多消耗 64 个随机位。直接将单个大随机数映射到排列的替代方法预计需要 2 × ⌈log2(N!)⌉ 位的熵来洗牌 N 个项目。如今获得如此多的真实熵困难吗？
如今，在许多计算机上，真随机数既便宜又充足。许多 CPU 支持非特权的 RDSEED 指令，该指令从芯片上的、加密级的、符合 NIST 标准的、非确定性的/proc/cpuinfo 以查看您的 CPU 是否支持它。RDSEED 在中等年龄的 Intel 服务器上每秒提供数千万个随机位。按照这个速度，未来的征兵抽签可以洗牌个人公民而不是生日，可以在几分钟内无偏差地随机排列整个美国人口；双胞胎和三胞胎的父母可能更喜欢这种方式而不是洗牌生日。真随机数生成器不再是高端 CPU 功能。流行的、廉价且坚固的 Raspberry Pi 单板计算机至少十年以来一直具有真 RNG。[33]
注意：真随机数生成器的历史与伪随机生成器的历史一样麻烦。兰德公司 1940 年代的里程碑式真 RNG 是一个笨拙的装置。[3] 在 1990 年代，三个商业真 RNG 小工具都未能通过 Marsaglia 的统计随机性测试。[19] 最近，AMD 对 RDSEED 的合作伙伴 RDRAND 的实现完全崩溃了。[27] 而且，每当安全成为问题时，我们都必须思考 Ken Thompson 关于信任陌生人设计和制造的任何东西的永恒建议：“不要。”[30]
幸运的是，我们可以通过组合来源来减轻可疑熵来源的风险，这与前面提到的串联洗牌抽签协议的精神一致。有时，简单地按位异或独立的随机位流在一起是安全且有帮助的；有关详细信息以及更复杂的方法，请阅读有关随机性合并器的内容。侧边栏介绍了一种应对不完善熵源的另一种技术。
熵炼金术
现实世界的熵源很少遵守概率论的理想化规则。偏差是普遍存在的。幸运的是，冯·诺伊曼想出了一种技巧，可以将暗淡的铅制有偏差的硬币变成闪耀的金制公平硬币：抛两次。如果结果是正面-正面或反面-反面，则不输出任何内容并重新开始。否则，输出该对的第二个结果：对于正面-反面，输出反面，对于反面-正面，输出正面。如果抛掷是独立的，则输出流是公平硬币的输出流，而与实际硬币的偏差无关。
在随机选择的最重要的实际应用中，零容忍偏差是一个硬性要求。在许多其他应用中，零容忍既可行又谨慎。当然，作为程序员，您有时可以自由地采用不同的策略。重要的是对偏差做出有意识且明智的决策；量化和描述软件中存在的所有偏差；并向所有利益相关者清楚地解释您允许偏差的理由。
深入挖掘
O'Connor 回顾了洗牌算法的历史。[22] Knuth 和 Yao[16] 以及 Lumbroso[18] 开发了节俭的拒绝方法，用于在随机数昂贵的情况下进行公正选择。Press 等人描述了
位
示例代码 tarball 位于 https://queue.org.cn/downloads/2024/Drill_Bits_12_example_code.tar.gz，其中包含图 1 和图 4 的洗牌器；一个将单个大随机数映射到排列的洗牌器；一个使用 RDSEED 生成真随机数的程序；一个快速而粗糙的小程序，用于从击键计时中收集熵；一个估计大型洗牌的熵需求的脚本；以及关于基于 PRNG 的洗牌的注释。
练习
1. 表达式 "random_number % N" 永远不会有偏差吗？假设随机数在 [0..232−1] 上均匀分布，量化其作为 N 函数的偏差。将每个特定 N 值的偏差定义为最可能结果概率与最不可能结果概率的比率。
2. 审计某些编程和脚本语言中提供的据称无偏差的 "random_number % N" 替代品。
3. 将图 4 中的程序修改为扑克发牌程序，该程序具有“完成时停止”[13] 洗牌（即，仅根据当前游戏的需要洗牌牌堆的顶部）。Bentley 考虑了一个相关的抽样问题。[1]
4. 将图 4 中的函数 U() 与 Lemire 的算法 3 和附录 A 进行比较。[17] 考虑 s 参数端点的行为。算法 3 是否处理 s = 0？调用者可以表达 s = 2L 吗？
5. 修改 U() 以在可能的情况下消耗更少的随机位。例如，U(8) 只需要三个随机位。
6. Wikipedia 概述了 N! 不能整除 NN（对于 N > 2）的两个证明，但在我看来，这两个证明都包含漏洞。[10] 填补漏洞。
7. 物理学家认为真随机性在自然界中存在吗？
8. 比较图 4 中的示例程序在从我的 RDSEED 程序与 /dev/urandom 或硬连线 PRNG 读取随机数时的性能。
9. “ps -AF | sha512sum” 是收集熵的一种快速技巧。它产生多少位熵？
10. 击键、存储或网络计时是虚拟机在虚拟机监控程序下运行时可靠的熵源吗？查看 VirtIO-RNG 和 /dev/hwrng。
11. 种子偏差真的是一个问题吗？考虑洗牌一副标准的 52 张扑克牌。如果所有 52! 个排列都是等可能的，那么前五张牌构成同花大顺的概率是多少？现在为具有 B 位种子的基于 PRNG 的洗牌计算该概率，其中 B 的几个合理值。更一般地，描述由小种子引入的偏差，就玩家面临的概率变化而言。大种子会引入偏差吗？
12. PRNG 使通过重用保存的种子可以轻松重现随机程序的运行。对于诸如图 4 这样从 stdin 读取随机数的程序，是否可以重现？请参阅 GNU shuf 的文档。
13. 研究 Linux /dev/random 和 /dev/urandom PRNG 以及 /proc/sys/kernel/random/。自首次引入以来，这些是如何演变的？
14. Durstenfeld 的算法在 60 年后仍然强劲。PRNG 的预期寿命是多少？1960 年代的任何 PRNG 至今仍在使用吗？今天的 PRNG 预计可以使用到 2084 年吗？
15. 如果 PRNG 输出“通过了随机性的统计测试”，我们是否应该得出结论，测试失败了（即，未能检测到不是真正随机的数据）？
致谢
我感谢 Jon Bentley 和 John Dilley 的有益对话和审阅大纲、早期草稿和示例代码；感谢 Kevin O'Malley 审阅示例代码；感谢 Skaff Elias 提供与在线赌博相关的见解和指导；以及感谢 Suyash Mahar 和 Haris Volos 测量 RDSEED 指令的速度。
参考文献
1. Bentley, J. 2000. 《编程珠玑》，第 2 版。第 12 章：示例问题。 Press。
2. Boneh, D., Shoup, V. 2023. 《应用密码学研究生课程》；https://toc.cryptobook.us/book.pdf。
3. Brown, G. W. 1949. 兰德公司随机数字的历史 — 摘要。技术报告 P-113，兰德公司。https://www.rand.org/pubs/papers/2008/P113.pdf。
4. Oracle Corporation. 2024. 选择 PRNG 算法；https://docs.oracle.com/en/java/javase/21/core/choosing-prng-algorithm.html。
5. Deitel, H. M., Deitel, P. J. 1994. 《C 语言程序设计》，第二版。Prentice Hall。模偏差：第 160-163、183、215、289 和 403 页；洗牌偏差：第 402-404 页；种子偏差：第 289 和 403 页。
6. Deitel, H. M., Deitel, P. J. 2023. 《C 语言程序设计》，第九版（全球版）。Pearson。模偏差：第 250-254、396 和 545 页；洗牌偏差：第 545-546 和 574 页；种子偏差：第 544 页；安全 PRNG：第 275 页。
7. Diaconis, P. Fulman, J. 2023. 《洗牌的数学》。美国数学学会。
8. Durstenfeld, R. 1964. 算法 235：随机排列。《 通讯》7(7)。整篇文章占据第 420 页的右下角。https://dl.acm.org/doi/pdf/10.1145/364520.364540。
9. Yahoo! Finance. 2024. 在线扑克行业回顾和 2030 年预测；https://finance.yahoo.com/news/online-poker-industry-review-forecast-130200589.html。
10. Fisher-Yates 洗牌。2024. Wikipedia； https://en.wikipedia.org/wiki/Fisher–Yates_shuffle。
11. 英特尔数字随机数生成器：软件实现指南。2018。https://www.intel.com/content/www/us/en/developer/articles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html。
12. Jones, D. 2010. 生物信息学应用中（伪）随机数生成的良好实践；http://www0.cs.ucl.ac.uk/staff/D.Jones/GoodPracticeRNG.pdf。
13. Kelly, T. 2020. 高效图搜索：完成时停止。《acmqueue 18(4)》；https://queue.org.cn/detail.cfm?id=3424304。
14. Kelly, T. 2023. Catch-23：新的 C 标准引发世界大火。《acmqueue 21(1)》，12-29；https://dl.acm.org/doi/pdf/10.1145/3588242。
15. 密码学上不安全的 PRNG。2024. Wikipedia；https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number
_generator#NSA_kleptographic_backdoor_in_the_Dual_EC_DRBG_PRNG。
16. Knuth, D. E., Yao, A. C. 2000. 《算法分析选集》，第 34 章：非均匀随机数生成的复杂性，545–603。斯坦福语言与信息研究中心。1976 年论文的更新版本。
17. Lemire, D. 2018. 区间内的快速随机整数生成。https://arxiv.org/abs/1805.10941。
18. Lumbroso, J. 2013. 来自抛硬币的最佳离散均匀生成，以及应用。arXiv 1304-1916；https://arxiv.org/abs/1304.1916。
19. Marsaglia, G. 1996. Marsaglia 随机数 CDROM。https://web.archive.org/web/20100612204426/ http://stat.fsu.edu/pub/diehard/cdrom/pscript/cdmake.ps。
20. Menn, J. 2013. 秘密合同将 NSA 与安全行业先驱联系起来。路透社。关于贿赂、后门和“密码学安全”但并非如此的 PRNG 的故事；https://www.reuters.com/article/uk-usa-security-rsa-idUKBRE9BJ1CJ20131220/。
21. 游戏设备最低标准。2023. 内华达州博彩委员会和内华达州博彩控制委员会法规 14，第 14.040 节，第 5 段；https://gaming.nv.gov/regs/statutes-regs/。
22. O'Connor, D. 2014. 关于洗牌算法的历史注释。Academia；https://www.academia.edu/1205620/OConnor_A_Historical_Note_on_Shuffle_Algorithms。
23. Press, W. H., Teukolsky, S. A., Vetterling, W. T., Flannery, B. P. 2007. 《数值食谱：科学计算的艺术》，第三版。剑桥大学出版社。第 7 章涵盖 PRNG；第 341–342 页提供基线建议。本书并非所有建议都很好；第 343 页推荐 PRNG() % N。PDF 可在 https://numerical.recipes/book.html 上获取。
24. 操纵西洋双陆棋 [USENET 新闻主题]。Google Groups；https://groups.google.com/g/rec.games.backgammon/c/Dh33pOhN-dE/m/0THUPU49AAAJ。
25. Rosenbaum, D. E. 1970. 选秀官员重新设计彩票程序以使系统更随机。《纽约时报》（6 月 25 日），17；https://timesmachine.nytimes.com/timesmachine/1970/06/25/issue.html。
26. Rosenbaum, D. E. 1970. 统计学家指责选秀彩票不是随机的。《纽约时报》（1 月 4 日），66。关于如何拙劣地进行物理洗牌的经典案例研究。第二列包含排版错误（垂直旋转）；https://timesmachine.nytimes.com/timesmachine/1970/01/04/issue.html。
27. Salter, J. 2010. 一个月大的 AMD 微代码错误如何毁了我的周末。arsTechnica；https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/。
28. 兵役制度彩票。https://www.sss.gov/about/return-to-draft/lottery/。
29. Starr, N. 1997. 非随机风险：1970 年选秀彩票。《统计教育杂志 5(2)》；https://jse.amstat.org/v5n2/datasets.starr.html。
30. Thompson, K. 1984. 对信任信任的反思。图灵奖讲座。《 通讯 27(8)》；https://dl.acm.org/doi/pdf/10.1145/358198.358210。
31. Viega, J., McGraw, G. 2002. 《构建安全软件》。Addison-Wesley。有关扑克攻击，请参见第 238–241 页。
32. Weir, R. 2010. 执行微软洗牌：浏览器投票中的算法失败；https://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html。以创新地使用非传递比较函数而闻名。
33. 真随机数生成器。《MagPi》杂志，第 40 期（2015 年 12 月）。https://magpi.raspberrypi.com/issues/40
Terence Kelly ([email protected]) 永不让随机性碰运气。
https://xkcd.com/221/
版权所有 © 2024 归所有者/作者所有。出版权已许可给 。
最初发表于 Queue 第 22 卷，第 2 期——
在 数字图书馆 中评论本文
© 保留所有权利。