[打听，优先权] 生成更好的随机数（关联：David Zuckerman, Eshan Chattopadhyay）

图1  David Zuckerman 教授，University of Texas at Austin

https://www.cs.utexas.edu/~diz/Images/zuckerman_david.jpg

https://www.cs.utexas.edu/~diz/

一、David Zuckerman 和 Eshan Chattopadhyay 在随机数生成方面取得理论突破，2016-05-17

https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/

Academics Make Theoretical Breakthrough in Random Number Generation

   David Zuckerman, a computer science professor, and Eshan Chattopadhyay, a graduate student, published a paper in March that will be presented in June at the Symposium on Theory of Computing. The paper describes how the academics devised a method for the generation of high quality random numbers. The work is theoretical, but Zuckerman said down the road it could lead to a number of practical advances in cryptography, scientific polling, and the study of other complex environments such as the climate.

   【机器翻译】计算机科学教授David Zuckerman和研究生Eshan Chattopadhyay于3月发表了一篇论文，将于6月在计算理论研讨会上发表。本文描述了学者们如何设计出一种生成高质量随机数的方法。这项工作是理论性的，但祖克曼表示，未来它可能会在密码学、科学民意调查以及气候等其他复杂环境的研究方面取得一些实际进展。

   “It would have been great to see any explicit two-source extractor for min-entropy rate below one half, let alone one that beats Bourgain’s rate of 0.499,” Goldreich said on the Weizmann website. “Handling any constant min-entropy rate would have been a feast (see A Challenge from the mid-1980s), and going beyond that would have justified a night-long party.”

   【机器翻译】Goldreich在魏茨曼网站上说：“如果能看到任何明确的双源提取器，其最小熵率低于一半，那就太好了，更不用说能击败Bourgain的0.499率了。”。“处理任何恒定的最小熵率都是一场盛宴（见20世纪80年代中期的挑战），超越这一点就可以举办一场通宵派对。”

二、打听：Zuckerman 和 Chattopadhyay 理论突破，后来国际上的反映？

   我有点吃惊的是，生成随机数，这样古老的课题居然也能成为科技新闻？

   1990年傻的“随机有理矩阵乘法的信息量 n³logn”，居然找不到地方贴出来？

   值得对照的是：2012年美国 SIAM 主席、皇家学会院士 Nick Trefethen ，还研究“高斯消元法 Gaussian elimination”为什么在实践中是数值稳定的？

三、重复：更好的伪随机数

3.1  我们的“更好的伪随机数”

   独立于 David Zuckerman 老师 2016年的理论结果，傻在更早的多年之前就想出来“各阶统计矩无限接近其理论值”的伪随机数，当然是利用现在的数字计算机程序。因为已经记不得是哪年了，2017年在硕士生同学帮助下，编出了计算机程序。

   《1000个均匀分布随机数 Uniformly distributed random numbers with a sample size 1000》

https://blog.sciencenet.cn/blog-107667-1383337.html

   该伪随机数《Uniformly_distributed_PSEUDO_random_numbers_1000.txt》文件可以从百度网盘下载：

   链接：https://pan.baidu.com/s/12iigZWkJjnQ7u1ZDUQO8Lw

   提取码：0epc

   《278个均匀分布随机数 Uniformly distributed random numbers with a sample size 278》

https://blog.sciencenet.cn/blog-107667-1383082.html

   我们的均匀分布伪随机数，原则上满足“密码学安全伪随机性”，原则上几乎可以做到“真随机性”：

https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=287834

   密码学安全伪随机性。其定义为，给定随机样本的一部分和随机算法，不能有效的演算出随机样本的剩余部分。

   真随机性。其定义为随机样本不可重现。实际上只要给定边界条件，真随机数并不存在，可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉（比如计算机当地的本底辐射波动值），可以认为用这个方法演算出来了真随机数。

https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=287834

   其中“真随机性”可以很快速地保证。

   缺点：

   （1）“统计学伪随机性。统计学伪随机性指的是在给定的随机比特流样本中，1的数量大致等于0的数量，同理，‘10’‘01’‘00’‘11’四者数量大致相等。类似的标准被称为统计学随机性。满足这类要求的数字在人类’一眼看上去‘是随机的。”受制于现有人类的相关成果，大体上还现有方法持平。

   （2）生成的速度为 O(nlgn)，比现有优秀方法慢了 lgn。

3.2  请教：改进“更好的伪随机数”

   我们的随机数，生成速度进一步提高，在数字计算机上几乎是不可能的。不知道将来的“量子计算机”？

   所以，我们今后改进的重点，主要是“统计学伪随机”：更随机。

   希望明显比现有的其它类方法“更”随机。

   所以，打听一下“更随机”方面有什么最新的国际进展？

参考资料：

[1] Threatpost, 2016-05-17 12:25, Academics Make Theoretical Breakthrough in Random Number Generation

https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/#:~:text=Two%20University%20of%20Texas%20academics%20have%20made%20what,have%20longstanding%20implications%20for%20cryptography%20and%20computer%20security.

[2] MIT CSAIL TOC, Theory of Computation MIT CSAIL, Friday, April 15, 2016 - 1:30pm to 4:30pm, DAVID ZUCKERMAN: EXPLICIT TWO-SOURCE EXTRACTORS AND RESILIENT FUNCTIONS

https://toc.csail.mit.edu/node/950

[3] Eshan Chattopadhyay, David Zuckerman. Explicit two-sourceextractors and resilientfunctions [J]. Annals of Mathematics, 2019, 189(3): 653-705

doi:  10.4007/annals.2019.189.3.1

https://annals.math.princeton.edu/2019/189-3/p01

https://annals.math.princeton.edu/wp-content/uploads/annals-v189-n3-p01-s.pdf

[4] Eshan Chattopadhyay, David Zuckerman. Explicit two-source extractors and resilient functions [C]. STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, Pages 670 - 68

doi:  10.1145/2897518.2897528

https://dl.acm.org/doi/10.1145/2897518.2897528

[5] Nick Trefethen. The Smart Money’s on Numerical Analysts [J]. 2012, 45(9): ? 为什么没有页码

https://archive.siam.org/pdf/news/2024.pdf

https://archive.siam.org/news/news.php?id=2024

[6] Zheng-Ling Yang, Reng-Xiang Liu, Zhen-Zhen Li, Jin-Yi Hou, Jun Zhang. An explicit analytical estimation of the validity of the Tanimoto similarity by confidence intervals in mathematical statistics [C]. 2018 13th World Congress on Intelligent Control and Automation (WCICA), 2018-07: 979-984

doi:  10.1109/WCICA.2018.8630700

https://ieeexplore.ieee.org/document/8630700/authors#authors

[7] 中国科学院科学智慧火花，杨正瓴，2023-04-24 00:51，通过“拼接”来提高随机数的性能

https://idea.cas.cn/zhhh/gcjskxygjs/gcjskxygjs_dzyxx/info/2023/525531.html

[8] 科普中国，2021-12-31，随机数

https://www.kepuchina.cn/article/articleinfo?business_type=100&classify=0&ar_id=287834

   统计学伪随机性。

   密码学安全伪随机性。

   真随机性。

[9] 2022-12-23，随机数生成/random number generation/尚轶伦，中国大百科全书，第三版网络版[ED/OL]

https://www.zgbk.com/ecph/words?SiteID=1&ID=296338&Type=bkzyb&SubID=81652

[10] Random and pseudo-random numbers. Encyclopedia of Mathematics.

https://encyclopediaofmath.org/wiki/Random_and_pseudo-random_numbers

[11] random number generation, britannica

https://www.britannica.com/science/random-number-generation

相关链接：

[1] 2025-04-17 22:50，[往日（21）, 优先权]：多年前已经完成，但一直没有发表的部分研究结果

https://blog.sciencenet.cn/blog-107667-1482422.html

[2] 2024-09-12 22:49，[打听] “大贝尔实验合作组（The BIG Bell Test Collaboration）使用的“随机数”

https://blog.sciencenet.cn/blog-107667-1450874.html

[3] 2023-10-30 22:03，[资料，惊悚，恐怖] 用几千条生命换来的“真随机数”（2），或许是上万条！

https://blog.sciencenet.cn/blog-107667-1407816.html

[4] 2023-04-08 23:18，[优先权？] “比你的更好”随机数生成要点

https://blog.sciencenet.cn/blog-107667-1383480.html

[5] 2023-04-07 19:57，1000个均匀分布随机数 1000 Uniformly distributed random numbers

https://blog.sciencenet.cn/blog-107667-1383337.html

[6] 2023-04-05 18:41，[讨论，擂台] 比真随机数更好的伪随机数（以[0,1] 区间上的均匀分布随机数为例）

https://blog.sciencenet.cn/blog-107667-1383089.html

[7] 2022-07-02 16:37，往日（14）：曾经“最好”的伪随机数，目前继续求教中

https://blog.sciencenet.cn/blog-107667-1345572.html

[8] 2021-01-29 13:44，[擂台] 地球上最好的100个和270个正态分布随机数

https://blog.sciencenet.cn/blog-107667-1269582.html

感谢您的指教！

感谢您指正以上任何错误！

感谢您提供更多的相关资料！