突破随机数生成算法

随机数已在软件中广泛使用. 例如，彩票程序是可以想象的应用程序之一. 但是，随机数在更重要的应用程序中也起着重要作用. 例如，敏感信息的加密，复杂的系统建模（例如地球的天气）以及公平的数据采样都离不开随机数.

但是，计算机生成的随机数要比扔筛子困难得多，这些随机数实际上并不是完全不可预测的随机数生成算法，而是由基于随机的算法自动生成的. 这些数字实际上是可复制的，不是真正的随机（伪随机数）. 因此，随机数的随机性是基本算法面临的主要问题.

然而，得克萨斯大学的两位计算机科学家Eshan Chattopadhyay和David Zuckerman已经开发出一种改进的随机提取器. 该算法仅需要两个低随机性源即可生成真正的随机数. 这是基本算法所取得的重大突破.

为了提高随机性，一般的随机算法会将环境的随机性引入算法中，例如鼠标或键盘的位置. 计算机将在几个时间点采样鼠标的位置，并将其转换为数字字符串. 但这仍然不是真正随机的. 例如，如果前一时刻的鼠标位置在屏幕的左侧，则鼠标向右移动的可能性非常低. 因此，以这种方式生成的随机数序列仍然是有意义的，或者可以偏向特定值. 换句话说，这种随机性仍然很弱.

随机提取器使用这些弱源来发矿一样-先开采矿石，然后将金排尽.

两位科学家的算法是对随机提取器的改进. 这个随机提取器将两个独立的弱随机数源组合成一个几乎随机的集合，只有很小的偏差. 然后使用弹性函数（一种信息组合方法）将一串数字转换为真正的随机位-1或0.

将信息与弹性功能相结合可以防止偏差. 例如，在大选中，一些故意的选民可能会将选举结果推向期望的方向. 但是弹性功能可以保护诚实的选民. 因为它没有选择简单的多数随机数生成算法，而是先将数据分为3组，然后在每组中选择多数，然后将所选数字分为3组，然后提取各组中的多数，依此类推直到最后. 这种方法使选举能够容忍大量坏人的存在，就随机数生成而言，这种方法可以滤除偏差数.

与以前需要接近随机输入的随机提取器相比，该新方法是通过“金矿开采”从具有非常非常弱的随机性的源中挖掘真实的随机数，从而实现了随机性的本质. 已经接近理想情况. 对于诸如加密和复杂系统仿真之类的应用程序，这是个好消息.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-185646-1.html