ACM通信
新闻
从两个糟糕的来源中提取的纯粹随机性
来源:丹·蒂尔特
真正的随机数对计算和密码学至关重要。虽然确定性算法可以生成看似随机的数字，但关键应用程序依赖于真正不可预测的物理过程。不幸的是，结果序列仍然可能包含隐藏的规律，因此理论计算机科学家长期以来一直在寻找“提取器”，从这些不完美的来源中产生完美的随机性。
30年前，人们就知道应该有很多方法来结合两个不完美的源来生成近乎完美的随机数，但直到现在，研究人员才明确地展示了如何创建这样的“双源提取器”。该作品在第48届会议上获得了最佳论文奖th去年6月，ACM计算理论研讨会(STOC 2016)汇集了计算机科学几个不同领域的发展。新泽西州普林斯顿大学高级研究所的Avi Wigderson说:“搜寻工作主要在过去的10到15年里进行，这是这项努力的高潮。”“无论是技术上还是数量上，这都是一个巨大的飞跃。”
没有找到条目