数学建模13：同余与随机数生成器

本讲导读

       利用计算机，针对所讨论的问题，借助随机数来进行模拟以汲取经验，再根据所得经验改进统计方法，这在一些复杂的统计过程中已经成为一种常用的技巧^[1]。这种经验分析的质量直接依赖于所采用的伪随机数发生器的性能。另外，随着计算机技术的发展，越来越多的大型物理问题和工程问题需要使用蒙特卡罗方法，而蒙特卡罗方法应用的核心问题之一便是如何构造高质量的伪随机数发生器。可见高质量的伪随机数发生器在实际应用中的重要性。

       本讲适合在讲授或学习完高中数学的解析几何、概率统计、复数章节后，作为数学建模材料，在日常教学中讲授或学习。如果在学习本讲之前有一些初等数论的基本知识，可以更好地理解本文各项定理的证明。

       本讲内容包括但不限于：

       1.伪随机数生成器的历史数理；

       2.传统的LCG、MRG、MCG三种生成器的定义、性质及其缺陷；

       3.衡量伪随机数生成质量的谱测试和图测试；

       4.一种改进的伪随机数生成器——指标并行生成器；（配算法结构图）。

参考文献及扩展延申读物：

[1]  Lih-Yuan Deng, Dennis K.J.Lin. Random number generation for the new century[J]. The American Statistician, 2000, 50(2): 145-150.

[2]  廖晓峰，肖迪等. 混沌密码学原理[M]，北京：科学出版社，2009，第1版，92-106.

[3]  张宝荣. 线性伪随机序列的综合与产生[J]. 微电子技术， 2005(18)：94-95.

[4]  赵学龙，王庆梅 等. 基于一维扩展元胞自动机的伪随机数发生器研究[J]. 计算机科学，2005，32(4)：137-139.

[5]  胡海朋. 一种新的伪随机数产生方法及其统计性能分析[D]. 博士：国防科学技术大学，2007.

[6] FIPS.FIPS140-2: Security requirements for Cryptographic Modules. 

http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf. 2001.

[7]  A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 800-22, 2001.

[8]  王莱，高质量伪随机数发生器及其谱测试[J]，核电子学与探测技术，1998，18(5)：336-390.

[9]  杨自强，魏公毅. 常见随机数发生器的缺陷及组合随机数发生器的理论与实践[J]. 数理统计与管理，2001，20(1)：45-51.

[10]  Zhu L.P. Lin L.N. Evaluating the Randomness Based on Spectral Density[J]. Chinese Journal of Applied Probability and Statistics, 2009, 25(2): 185-191.

[11]  潘承洞，潘承彪，初等数论[M]，北京：北京大学出版社，1992，第1版，232-269.

[12]  游宏，刘文德. 代数学[M]，北京：科学出版社，2009，32-41.

[13]  Sergey Brin, Rajeev Rastogi. Mining Optimized Gain Rules for Numeric Attributes[J]. IEEE Transitions on Knowledge and Data Engineering, 2003, 15(2): 324~338.

[14]  祝跃飞，张亚娟，椭圆曲线公钥密码导引[M]，北京：科学出版社，2006，第1版，129-132.

[15]  Don Johnson, Alfred Menezes, The Elliptic Curve Digital Signature Algorithm[Z], 1999.

[16]  Horster P, Michels M. Petersen H. Meta-ElGamel signature schemes based on the discrete logarithm problem[J]. Technical Report TR-94-6, Theoretical Computer Science and Information Security, TU Chemnitz-Zwichau, June, 1994.

[17]  Jian Zhao, Eckhard Koch. Embedding robust labels into images for copyright protection[J]. In: Proc. of the Int. Congress on Intellectual Property Rights for Specialized Information, Knowledge and New Technologies, Vienna, August 1995.

日常生活中的数学建模系列文章：

» 日常生活 01: 日常生活中的等差数列和等比数列

» 日常生活 02: 二次和三次函数样条、数据的插值

» 日常生活 03: 指数函数与对数函数的普适价值

» 日常生活 04: 三角函数与极小曲面

» 日常生活 05: 概率的加法与乘法原理、加权平均的递推

» 日常生活 06: 解析几何与带标签数据的模糊线性分类

» 日常生活 07: 进制观点下的分类、距离与解析

» 日常生活 08: 迭代预测的测不准原理与熵距

» 日常生活 09: 数据直径、荣格定理及凸集

» 日常生活 10: 欧式与离散几何的桥梁——皮克定理及其应用

» 日常生活 11: 暗室与艺廊——平面几何与照明

» 日常生活 12: 纽结与琼斯多项式