柏森，周龙福，郭辉，闫兵

（1. 重庆工程学院软件学院，重庆400056；2. 重庆通信学院信息工程系，重庆400035；3. 61541部队，北京 100094）

基于随机序列统计特性的伪随机序列生成方法

柏森1,2，周龙福1，郭辉3，闫兵2

（1. 重庆工程学院软件学院，重庆400056；2. 重庆通信学院信息工程系，重庆400035；3. 61541部队，北京 100094）

在现有生成伪随机序列的方法中，产生的伪随机序列存在均衡性、游程特性不够好的问题。根据随机序列的统计特性，在骑士巡游问题 SemiHam求解算法的基础上，提出了基于随机序列统计特性的伪随机序列生成方法。首先，对棋盘中的格子设定不同长度的0、1游程值；然后，再用骑士巡游问题SemiHam求解算法产生的Hamilton圈对设定游程值的棋盘进行扫描；最后，取出0、1游程值，得到伪随机序列。实验结果表明，该算法产生的伪随机序列满足随机序列统计特性，且随机性较好。

伪随机序列；随机序列统计特性；SemiHam算法；NIST SP800-22随机性测试

1 引言

在数据加密的应用中，人们希望得到真正的随机序列，但能否重复产生真正的随机序列，一直是争论的问题。由于伪随机序列能够重复产生和处理[1]，并且具有良好的随机特性，在数据加密[2]、卫星导航[3]、扩频通信[4]、探地雷达[5]等方面都有广泛的应用。因此，伪随机序列的生成方法一直是研究的重点问题之一。

良好的伪随机序列应具有真随机序列的统计特性[6]：伪随机序列中0和1的数量相等或相差1个；游程个数为序列长度的，长度为l的游程个数占总游程个数的。目前产生伪随机序列的方法主要有混沌[7～10]、有限域[11]、自动细胞机[12]等，但这些方法产生的伪随机序列不能完全满足真随机序列的统计特性。……