一种产生随机数的数学方法

陈华贤

关键词：随机数；函数；进制转换；无理数；超大整数

1引言

如今，各行业尤其是计算机领域对随机数的需求量很大，因此，迫切需要一种高效和低成本产生随机数的方法。但是，在传统的科学观点中，在计算机上是不可能产生真正的随机数的。美国著名计算机学家冯·诺依曼曾经说过：“任何人考虑用数学的方法产生随机数肯定是不合情理的”。能否找到一种产生随机数序列的数学方法，本文认为是可以的。事实上，随机数并不难获得。

2产生随机数的数学方法

2.1灵感来源

本数学方法的灵感来源于无理数。比如，针对无理数π，数学家对它进行了深入研究，即π是无限不循环小数，利用泰勒级数或者其他计算方法可以将其无限地计算下去。据悉，现在科学家已将π计算到小数点后万亿位。而π数位上的数字拥有的特点是：（1）无限性，即可以无限计算下去；（2）无周期性，没有周期不会出现循环；（3）随机性和不可预测性，数位上的数字没有特别的规律，而且相互独立，無法通过已知数位上的数字推测未知数位上的数字；（4）均匀性，每个数位上的数字（0～9）出现的概率均等，即每个数字出现的概率都接近10％；（5）可复现性，即π数位上的数字通过重复计算较易重现，对于加密算法而言，该特性使它不用占据大量的存储空间，在加密或者解密环节把数字重新计算出来即可，可以不提前储存。

从上文对无理数π的分析可见，π数位上的数字符合真随机数的特点，因此，可以把它们看成是随机数。同时，可以大胆推断：存在一类无理数，其数位上的数字也具有类似仃的特征，即无限性、无周期性、随机性、均匀性和可复现性。当然，基于此可以再引申：存在一类有理数，其周期很长，有成百上千位，在它们的某个周期内，数位上的数字会随机出现，即可以将它们看成是随机数。

2.2产生随机数具体的数学方法

既然无理数和有理数都可以作为随机数的来源，那么可以从求解无理数π的方法中得到启示。求解π的方法很多，最直接的方式就是用泰勒级数进行求值计算。而通过观察泰勒级数的形式，暂且不论它的数学本质，单就运算形式而言，可以发现它其实就是初等函数之间的加减乘除运算。这些基本数学运算和初等函数的计算方法在现代计算机上已经能够实现。另外，从获取随机数的角度来看，并不需要小数点，因此，π的小数点可以去掉。而π去掉小数点后，会变成一个无限长的超大整数。在此，把位数超过一百位的十进制数字称为超大整数，简称超大数。对于某个通过函数随机运算确定的超大数而言，和仃类似，它的数位上的数字出现是没有规律的，也无法预测，即无法通过已知数位上的数字推测未知数位上的数字。受此启发，可以利用现成的大数运算库，用随机设计的函数去计算超大数，进而得到随机数数字序列。

本数学方法的核心就是通过设计函数去计算超大整数，然后把超大整数数位上的数字看成随机数，从而达到本文的目的。同时，可以对计算出来的超大数进行进制转换，然后得到指定范围内的随机数。关于设计函数和进制转换的细节，下文将进一步讨论。

2.2.1设计初等函数求解超大数

显然初等函数有无限种形式且具有随机性，而自变量的值也不尽相同，存在差异。因此，有理由相信通过随机设计的函数计算出来的数值也具有随机性。这就是本文方法能够获取随机数的本质。在具体的上机实验中，采用微软．net的大数运算库。利用该运算库，结合本文设计的函数（包括多元函数），可以计算出位数高达百万位的超大整数。从实验结果来看，以此计算出来的超大数，其数位上的数字具有无限性、无周期性、随机性、均匀性和可复现性等特征。这些特征符合上文分析无理数π时所总结的性质。同时，在上机实验中获得的随机数样本能够通过相关统计学软件的测试。

可以看出，以上函数都是常见的初等函数的复合函数，它们是随机设计的。而通过随机设计的函数来计算超大数，并把超大数数位上的数字当成随机数来源的方法，简单便利，实现门槛低，这是本数学方法的创新之处。值得注意的是，在需要多个密钥的密码学应用场景下，函数可以设计成多元的，每个自变量对应一个密钥。多元函数体现了本文方法的灵活性。

2.2.2利用函数矩阵来计算超大数

如图1所示，由函数构成的矩阵简称函数矩阵，显然它与2.2.1节讨论的初等函数一样，具有无限种形式。它的横向为初等函数的加减乘除；纵向是对横向计算结果1至结果n的字符串连接，即对横向计算出来的超大数字直接进行首尾相连。在此，用符号“&”表示字符串连接运算。之所以用字符串连接，是为了提高求值效率，同时加强随机性。另外，如果把该方法应用到密码学领域，即对数据进行加密，字符串连接运算也可以增强密码安全性，使加密算法更难被破解[2]。

函数矩阵的形式本身具有随机性，也可以采用多个自变量（即多元函数矩阵）来快速计算超大整数。建议利用随机化的系数初始化函数矩阵，然后将数字代入函数矩阵求值即可。如何设计函数矩阵，并使性能最优化还需要进一步讨论。

下文举例说明用函数矩阵计算超大数，进而获取随机数的方法。假如是一元函数矩阵，那么可以设计函数矩阵如下：

2.2.3进制转换

在以上两个例子中，所得随机数集合都是0～9范围内的整数，如何才能得到指定范围内的随机数集合？比如，要得到O～p的随机数集合，设p为大于等于1的正整数。其实处理方式也很简单，对计算出来的超大数进行进制转换即可。把超大数转换为二进制，因为二进制数字中数位上只能是0～1的数字，所以可得0和1的随机数集合：把超大数转换为十六进制，而十六进制数字数位上的数字范围是0～15，因此，可以得到0～15的随机数集合。总之，把超大数转换为p+l进制后，可以得到0～p的随机数集合。

需要注意的是，p需要远小于超大数才能使进制转换后的随机数集合更加均匀，这是基本的逻辑推理，下文将继续讨论均匀性。同一个超大数可以转换为不同进制，得到不同的随机数集合。

表3是采用上文设计的函数矩阵（x）循环计算超大数，并依次对各超大数进行进制转换后，获得随机数集合中各数字出现的次数统计表。其中，设进制数p+1=2，即p为1。

设进制数p+1=16，即p为15时，数字出现次数统计如表4所列。

从上机实验结果来看，若采用的数学函数和进制数相同，则生成的随机数数量越多，随机数分布的概率将更加均匀。这其实就是均匀性，也是本数学方法生成的随机数的特性之一。

以上结论有实验数据支持，下文采用的仍然是函数矩阵（x），当进制数为2时，各数量级的随机数样本的数字出现情况统计如表5、表6、表7所列，可见实验得到的随机数确实是很均匀的。

在实验中，可以观察到变异系数c（变异系数c=（标准偏差SD/平均值Mean）×100%）的值随着随机数数量级的增加而减少，如下表8所列。

从理论上说，进制转换并没有限制进制数的上限，满足进制数远小于当前的超大数即可，而超大数本身也没有大小限制。因此，利用本文方法生成的随机数并无大小限制。这种特性也是传统随机数算法所没有的，属于本文方法的創新点之一。总之，进制转换解决了如何均匀地获取指定范围内随机数的问题。

2.3所得随机数样本的统计检验

采用IBM公司的SPSS软件对随机数样本进行统计检验，如图2、图3所示。SPSS为IBM公司推出的一系列用于统计学分析运算、数据挖掘、预测分析和决策支持任务的软件产品及相关服务的总称，有Windows和Mac OS X等版本。实验所用版本是28.0.1.1（15），对本数学方法生成的某个随机数样本进行检测，结果符合随机性假设，这也是本数学方法的技术佐证。在一般场合，也可以通过随机数校验算法对获得的随机数进行检验，验证其随机性。

3对本数学方法的计算机算法描述

因为本数学方法的灵感来源于无理数，所以把实现它的计算机算法命名为无理数随机数生成算法。本算法很灵活．可以采用不同的函数来计算超大数（图4），因此，拥有无限多个实例。要注意的是，下文算法实例中用到了大数运算库Biglnteger，其中BigInteger.Pow方法表示对大数进行幂函数运算。以下是某个实例的具体算法描述：省略流程图。但是要注意，可以计算超大数的函数很多，getBigNumFun只是其中一种，而这样的函数也不难设计。从数学形式上看，没必要用到微积分，但微积分学中的泰勒级数理论给了我们很重要的启示。过程myChangeFormat（图5）表示对计算出来的超大数进行进制转换，并把进制转换后的该超大数各数位上的数字存储到数据列表dList中，从而得到一定范围内的随机数集合。它们的伪代码如下：

4本数学方法的优缺点分析

与传统的随机数算法相比，本文方法具备的主要优势是：（1）无周期性，把生成超大数的函数设计成非周期性的即可，而这样的函数有很多，有很大的选择空间；（2）无限性，只要计算和存储资源足够，在生成超大数的函数理论上可以无限计算下去，因此，可以产生无限多数量的随机数；（3）可复现性，本文方法灵活应用数学函数，函数形式不唯一，而且只要确定函数形式和自变量，那么计算出来的超大数就是确定的，因此，本文方法获取的随机数很容易复现，不需要物理采集和占用存储，简便且效率高；（4）随机数无大小限制，因为超大数在理论上是无大小限制的，因此，进制数也应该没有大小限制，所以，只要计算和存储资源允许，我们能够得到任意数量和任意大小的随机数集合；（5）灵活性强、实现简便、代价低，本数学方法完全可以在民用计算机上实现，是一种低门槛、低成本，大批量获得随机数的新方式，又因为任何人都可以定制生成随机数的函数，因此，它具有很强的灵活性；（6）随机性和均匀性都很强，函数形式和自变量的随机性造就了超大数的随机性，而既然是随机的，那么各数字的出现概率也应该相等，即均匀性。

本数学方法的不足之处在于理论上需要继续完善，主要是随机性和均匀性的严格数学证明。在实际应用中，可以增加随机性和均匀性的检验环节，对本数学方法产生的随机数集合进行检验，从而在一定程度上弥补理论上的不足。

5本数学方法的应用展望

5.1本数学方法可以改良一次一密算法

因为本文方法可以生成概率均匀的随机数集合，所以可以改良当前安全性高但实用性不强的一次一密算法。一次一密算法是具备完善保密性、安全性较高的对称加密算法。一个加密方案是完善保密的，即使攻击者拥有无限计算资源，也不可能从密文中分析出关于明文的任何信息。此前，如果采用一次一密算法对1GB的文件进行加密，则生成和管理1GB大小的密钥，造成存储空间的极大浪费。而如果采用本数学方法，保存生成超大数的函数和相关变量即可，在需要加密或解密时，再计算出随机数，能节省50%左右的存储空间。因此，本数学方法最直接的应用在于改良一次一密算法。当然，概率分布均匀的随机数集合的应用还很多，可以逐步发掘它的潜力。

5.2本数学方法可以检验量子计算机的计算正确性

目前，已有研究者用计算π的超精密值（通常是小数点后万亿位以上）来验证计算机的准确性。如上文所述，π去掉小数点后其实就是一个超大数，而本文方法可以通过设计某个函数（或函数矩阵）来计算超大数，因此，可以用该方式去检验量子计算机的正确性。因为拥有大量位数（如万万亿位十进制形式）的超大数不容易获得，需要通过超级计算机计算得到。而显然只要对比量子计算机的计算结果与传统超级计算机的计算结果是否一致，就能检验量子计算机的计算正确性。本数学方法生成的超大数没有大小限制且具有可复现性，因此它为相关检验工作提供了便利，是一种比较新的思路。

5.3本数学方法可以抵御量子计算机的威胁

因为量子计算机的强大计算能力，传统的非对称加密算法（如RSA）已经可以在较短时间内被它破解，因此，迫切需要一种新的加密机制保护关键数据。一次一密算法是传统的对称加密算法，具有完善保密性，可以抵御量子计算机的攻击。上文提道，本数学方法可以大大改良一次一密算法，因此，未来可能会广泛采用改良后的一次一密算法对关键数据进行加密，因为它的安全性较高。

5.4对本数学方法的总结

总之，本数学方法的技术可行性较强、应用前景广阔，需要多加研究和讨论，使其不断完善。本文方法既有理论支撑，也有技术支持，偏重技术实现。本文方法可以直接应用于密码学，能以较低的代价换取较高的安全性方面的收益，不失为一种新的加密方案，尤其在民用和商用等非关键数据的加密方面完全可以胜任。