基于区间算法的随机数生成算法的设计

摘要

20世纪中叶以来，随着John von Neuman最早提出一种简单的随机数生成算法，其被越来越多的人所研究，发展也愈加迅速，并且在众多领域中都发挥着不可或缺的作用。由于人们对高质量随机数的需求的增加，各种随机数生成器相继问世。1997年，Han和Hoshi提出了一种随机数生成的算法——区间算法（Interval Algorithm）。该算法的思想源于Knuth和Yao，算法的本质是区间迭代，与算术编码的编解码过程有一定相似性。到现在为止，区间算法一直在被改进和优化，但还是存在许多问题，包括区间算法复杂性过高的问题，有限精度运算误差如何改善的问题，等等。
　　本文主要研究的就是区间算法，以区间算法为基础，提出了一种新的随机数生成算法。该算法在继承区间算法的优点的基础上，对算法进行了改进和优化，主要贡献如下:
　　1.优化了系统的体系结构。本文不再如原区间算法那样考虑M进制的输入和输出，而是直接考虑输入和输出都是二元的情况。这么做可以有效减小算法在进行区间分割，区间放大，进位传送等操作时的复杂性，提高算法的运行效率。为了实现算法的这一改变，输入和输出就需要一个转换模块，两个模块则可以通过一棵树的形式来实现，整个系统的复杂性就可以控制在一个理想的状态。
　　2.拓展了算法的模型。本文探讨了信源的部分信息通过泄密信道泄露给随机数的使用者的情况下（泄露的信息称为边信息），即使用者有边信息的情况下随机数生成器的设计问题。本文尝试了三种方法来改善边信息对算法带来的影响，分别为区间放大，区间交换和随机置换，对这些方法能否改善生成的随机数的质量获得了一些有益的结果和结论，进而提出了一种测试者端有边信息的随机数生成基本框架，即以区间算法模块和随机置换模块级联的方式。

目录

摘要

第一章 绪论

1．1 引言

1．2 区间算法的发展进程

1．3 本文主要章节内容安排

第二章 随机数的介绍

2．1 随机数的基本概念

2．2 随机数的产生方法

2．3 随机数的应用

2．4 本章小结

第三章 区间算法的介绍

3．1 一种随机数生成算法的模型及其基本属性

3．2 区间算法的基本原理

3．3 区间算法的两种实现方法

3．4 区间算法的性能分析

3．4．1 区间算法的一种显式表示

3．4．2 区间算法的性能分析结果

3．5 本章小结

第四章 基于区间算法的随机数生成算法

4．1 新区间算法的基本原理

4．2 新区间算法的优点

4．3 区间算法的性能测试算法

4．4 边信息存在条件下算法的优化

4．4．1 区间放大

4．4．2 区间交换

4．4．3 随机置换

4．5 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

攻读硕士学位期间发表的论文和参加的科研工作

附录

声明