（应用数学专业论文）基于混沌理论的无穷维伪随机数发生方法及其统计特征.pdf

捅姜伪随机数广泛应用于信息安全、军事、商业、计算机网络等领域中，发挥着巨大作用。随着信息时代中高科技的迅猛发展，对发生随机序列的方法也提出了更高的要求，如何产生具有优良统计特征和高安全性的随机序列，已成为国内外学者广泛关注和深入研究的热门课题。混沌是非线性动力系统中一种确定的、类似随机的现象。由于它具有非周期、类噪声、宽频谱、对初始条件敏感等特性，与随机序列基本相似，因而它特别适用于发生随机序列。本文在混沌理论的基础上，提出了一种无穷维伪随机数发生方法，对其进行了较为深入的研究，并尝试在图像加密技术方面的应用，主要研究工作包括：1 深入地研究伪随机数的发生方法及其发展过程，并进行归纳总结。同时，分类分析了几种常见的随机序列发生方法的优缺点，并给出了伪随机数序列统计特征的几种检验方法。2 对简单的混沌映射模型，主要是一维l o g i s t i c s 混沌映射和一维无限折叠混沌映射，进行了较为详细的理论分析，针对其存在安全性能低，易攻破，初始值要求严格等缺点，阐述了组合混沌映射的方法。在研究组合线性发生器的基础上，解释了无穷维伪随机数的概念。并通过对组合混沌映射的扩展，提出了一种新的基于混沌理论的无穷维伪随机数发生方法。3 采用m a t l a b 编程进行仿真实验，利用基于混沌理论的无穷维伪随机数发生方法产生了若干随机序列。统计检验结果表明，产生的随机序列具有优良的统计特征、高度稳定性和高安全性等性能。另外，在与其他方法的比较之下，该方法显得更加优秀。经过对该方法应用在图像加密技术上的可行性分析，本文尝试利用其产生的随机序列加密图像，仿真结果显示，加密效果良好，具有很高的安全性。关键词：混沌；组合混沌映射；无穷维伪随机数；统计特征；图像加密a b s t r a c tt h er a n d o ms e q u e t i c e sa r ew i d e l yu s e di ni n f o r m a t i o ns e c u r i t y , m i l i t a r y ,c o m m e r c i a l ，c o m p u t e rn e t w o r k sa n do t h e ra r e a s t h e ya r ep l a y i n gas i g n i f i c a n tr o l ei no u rw o r l d w i t ht h er a p i dd e v e l o p m e n to fh i g ht e c h n o l o g yi nt h ei n f o r m a t i o na g e ，h o wt og e n e r a t et h er a n d o ms e q u e n c e sw i t he x c e l l e n ts t a t i s t i c a lc h a r a c t e r i s t i c sa n dl l i g l ls e c u r i t yh a sb e c o m et h eh o tr e s e a r c hw h i c hh a sa t t r a c t e dw o r l dw i d ea t t e n t i o n sa n di n d e p t hs t u d i e sf r o ms c h o l a r sa th o m ea n da b r o a d w i t ht h ei n t r o d u c t i o no fc h a o st h e o r y , c h a o si sac e r t a i n ，r a n d o m 1 i k ep h e n o m e n o ni nt h en o n l i n e a rd y n a m i cs y s t e m b e c a u s eo fi t sn o n p e r i o d i c b r o a d b a n ds p e c t r u m ，n o i s e l i k e ，s e n s i t i v i t yt oi n i t i a lc o n d i t i o n sa n do t h e rc h a r a c t e r i s t i c s ，w h i c ha r eb a s i c a l l ys i m i l a rt or a n d o ms e q u e n c e ，i t sv e r ys u i t a b l ef o rg e n e r a t i n gr a n d o ms e q u e n c e i nt h i sp a p e r , al 【i n do fi n f i n i t ed i m e n s i o np s e u d or a n d o mn u m b e rg e n e r a t o rb a s e do nc h a o st h e o r ya r ep r o p o s e da n da n a l y z e dc o m p r e h e n s i v e l y t h em a i nr e s e a r c hw o r ki n c l u d e d ：1 t h em e t h o d so fg e n e r a t i n gp s e u d o r a n d o mn u m b e ra n dd e v e l o p i n gp r o c e s sa r es u m m a r i z e d t h ea u t h o ra n a l y z e dt h ea d v a n t a g e sa n dd i s a d v a n t a g e so fs e v e r a lc o m m o nm e t h o d s ，a n ds e v e r a lt e s t i n gm e t h o d so fs t a t i s t i cc h a r a c t e r i s t i c so fp s e u d o r a n d o ms e q u e n c e s 2 c h a o si sa ne x c e l l e n tt o o lf o rg e n e r a t i n gr a n d o ms e q u e n c e s ad e t a i l e dt h e o r e t i c a la n a l y s i si sc o n d u c t e df o rt h es i m p l ec h a o t i cm a pm o d e l ，i n c l u d e do n ed i m e n s i o n a ll o g i s t i e sa n di n f i n i t ef o l d e dc h a o t i cm a p f o ri t ss h o r t c o m i n g ss u c ha sl o ws e c u r i t i e s ，e a s yt ob r e a k ，s e r i o u sa b o u tt h ei n i t i a lv a l u e ，w ee x p l o r et h em e t h o do fc o m b i n e dc h a o t i cm a p s b a s e do nt h er e s e a r c ha b o u tc o m b i n e dl i n e a rg e n e r a t o r , t h ec o n c e p to ft h ei n f i n i t ed i m e n s i o nr a n d o mi se x p o s e d t h r o u g he x p a n d i n gt h ec o m b i n e dc h a o t i cm a p s ，an e wi n f i n i t ed i m e n s i o np s e u d or a n d o mn u m b e rg e n e r a t o ri sp r o p o s e di nd e t a i l 3 i nt h es i m u l a t i o ne x p e r i m e n t s an u m b e ro fr a n d o ms e q u e n c e sa r eg e n e r a t e du s i n gm a t l a bp r o g r a m m i n g t h es t a t i s t i c a lt e s tp r o v e st h a tt h er a n d o ms e q u e n c e sh a v ee x c e l l e n ts t a t i s t i c a lc h a r a c t e r i s t i c s ，h i 【g hs t a b i l i t ya n dh i g hs e c u r i t yp r o p e r t i e s b e s i d e s ，i nc o m p a r i s o nw i t ho t h e rm e t h o d s t h i sm e t h o di sm o r eo u t s t a n d i n g t h r o u g ht h ef e a s i b i l i t ya n a l y s i so ft h em e t h o du s e di ni m a g ee n c r y p t i o nt e c h n i c a l ，t h i sp a p e ra t t e m p t st ou s er a n d o ms e q u e n c e sg e n e r a t e db yt h em e t h o dt oe n c r y p tt h ei m a g e t h er e s u l t ss h o wt h a tt h ep e r f o r m a n c e so fe n c r y p t i o na n dd e c r y p t i o na r ev e r yg o o d ，a n dt h ee n c r y p t i o nt e c h n o l o g yi sh i 曲l ys e c u r e k e y w o r d s ：c h a o s ；c o m b i n e dc h a o t i cm a p ；i n f i n i t ed i m e n s i o np s e u d or a n d o mn u m b e r ；i m a g ee n c r y p t i o n ；s t a t i s t i c a lf e a t u r e s独创性声明本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。关于论文使用授权的说明本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留、送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。( 保密的论文在解密后应遵守此规定)签名：纽趔导师签名：同期遮幺缇啤武汉理工大学硕士学何论文第1 章绪论1 1 课题研究背景及研究意义1 1 1 课题研究背景在当今全球信息化时代的背景下，对我们全世界的所有人来说，信息既是时间，也是财富，它已成为各个国家、企业和社会团体利益的重要组成部分和推动整个社会发展的重要战略资源。随着计算机技术、通信技术和网络技术的飞速发展，网络信息系统已经成为一个企业、一个集团乃至一个国家寻求发展的基础设施。近些年来，i n t e m e t 发展速度极快，计算机通信已逐渐成为人们进行信息交流的一条主要途径。网络购物、网络防伪、网上交易、电子商务、电子政务、电子税务、电子银行、电子海关、电子证券、网上拍卖等等一系列应用信息系统已经深入人们的同常生活中【3 2 3 7 1 。很多信息都可以迅速而方便地在网上发布和传输，但这同时也带来了信息安全的隐患，信息安全不仅关系到个人的隐私问题，关系到企业的商业机密和生存问题，也关系到一个国家的安全问题。因此，信息的安全与保密显得尤为重要，加密就成为保护信息数据和加强知识产权保护等等的重要手段。在信息安全领域内，所有公开的加密算法的安全性都依赖于密钥的安全性，而密钥的安全性则和随机数密切相关。除了作为信息安全核心的加密算法外，网络通信中还广泛使用了各种安全协议【l 刚。在这些协议中，为了进行身份认证，避免攻击偷听等，也需要加入随机数进行加密。可见，随机数的产生是信息技术和网络安全等领域中不可缺少的重要环节，这就迫切需要对随机序列的生成方法进行深入研究，来产生性能优良，高安全性的随机序列。1 1 2 研究意义在现实生活中，普遍存在着各种各样的随机现象。例如，抛一枚硬币观察其正反面出现的情况，电话交换台在一小时之内接到的呼唤次数，某企业的一批产品中出现次品的个数等等。随机现象可谓随处可见，随机序列的应用也是无处不在，有时由于太过频繁而可能被忽略。只要不是单个物体、事件或者现象，理论上都可能存在随机问题。从人们的日常学习、生活和工作，到国家的正常运行；从构成物体的基本粒子到整个世界和宇宙；从科学研究到艺术审美；从通讯技术到金融市场，随机现象覆盖的领域、深度、宽度和广度，已经大大的超出了武汉理t 大学硕士学位论文人们的想象。随机数的产生是信息技术和网络安全等领域中不可缺少的重要环节，其性能将会直接影响到整个信息系统的性能。在现代工程实践中，随机序列已广泛地应用于通信、雷达、导航、航空航天、定位跟踪、密码学以及自动控制、计算机安全等领域中【3 4 】。正是因为随机数的这些重要性，随机序列的产生长期以来都是广大学者研究的热点。基于混沌理论的伪随机数发生器产生的伪随机数具有优良的统计特性和安全性等特点，且产生方式简单，快速。事实上，随机序列并不是一个孤立的问题，它与数学、通信、计算机等许多领域都有这紧密的联系，它既有很强的理论背景，又有很强的应用背景。因此从事这方面的研究具有非常重要的实际意义。1 2 国内外研究现状由于随机序列的发生在信息安全、军事、商业等领域中发挥着重要作用，国内外对随机序列发生方法的研究也越来越重视。同时，伪随机数的产生长期以来都是各国统计学家研究的热点。传统的方法是用人工的方法，如采用抽签，掷骰子，摇号，抽牌或从搅乱的罐中取出标有号码的球等等。这些方法虽然可行，但是在进行大量的随机模拟实验时，远远不能满足需要。随着计算机的计算能力的不断提高和广泛应用，利用计算机来产生伪随机数成了一种重要的尝试。一种常用的方法是物理方法，即在计算机上安装一台物理随机数发生器，把具有随机性质的物理过程变换为伪随机数，这样得到的伪随机数随机性和均匀性都很好，完全符合随机数的特性。但是，利用这种方法得到的实验结果数据不能重复，加上物理随机数发生器的稳定性经常需要进行检查和维修，因而大大降低了它的使用价值。另外一种使用计算机来产生随机数的方法就是数学方法，这是目前使用最广，发展最快的一类方法。它利用数学公式迭代产生随机数，利用这种方法产生的随机数严格说来不是真正的随机数，通常称为伪随机数【2 0 1 。所谓的“伪随机数”并不意味是假的随机数，只是它与理想随机性有一定的偏差，但是随机序列若能通过一系列的统计检验，即如果具有真正随机数的大部分统计性质，那也就可以把它们当作真正随机数使用了。这种方法经济又实惠，而且产生随机数的速度极快。这种方法也是本文的主要研究对象。目前国际上关于发生伪随机数有很多热门的理论和方法，呈现出百家争鸣的态势，国外很多科学家提出了各式各样的伪随机数发生方法。在国内，中国科学院研究生院的冯凯锋、吕述望和刘振华等人开展了量子随机数发生器的研究工作；北京工业大学的冯艳、杨振海等人也提出了一种利用无理数无限不循环特性来发生随机数的模型【1 9 j ；佟晓筠，崔明根提出了基于复合非线性混沌系统的伪随机数产生算、法【6 j ；而电子科技大学的张传武、彭启琼等人在此基础上进行了深化2武汉理丁大学硕十学位论文研究，提出了基于具有本原多项式的9 0 1 5 0 加性细胞自动机的随机数发生器模型一等等。自从混沌理论深入到各个研究领域而成为一门新兴交叉的学科以来，在利用混沌理论作为随机数发生器的模型方面掀起了一股新的浪潮。国外已有研究表明，混沌系统是一类性能优良的随机数产生器模型【8 1 。在国内，我国的学术界对这方面的研究也很重视，已经有相当一批有实力的科研机构投入到这一领域的研究中来。例如，上海交通大学的邱跃洪等人提出了一种基于一维无限折叠混沌映射的均匀分布混沌伪随机数发生器【2 2 】；谢邦勇的基于素数的混沌伪随机数发生器【2 5 】；浙江大学超大规模集成电路设计研究所的俞俊等人选取分段线性的混沌表达式来设计真随机数发生器【2 8 】；清华大学微电子学研究所的黄谆等人通过利用电容上电荷的再分配原理实现了一个离散混沌随机数发生器。然而，这些随机数发生方法大多是基于简单一维的混沌映射模型，如l o g i s t i c 、c h e b y s h e v 、t e n t等，它们的安全性能并不显著，可以被一些混沌时间序列预测方法预测；但是，混沌是一门复杂深奥的理论，除上述简单混沌映射模型外，还有很多高维混沌模型，虽然它们有很高的复杂性，但是实际应用比较困难。若能够用简单一维混沌映射模型产生具有与高维模型一样性质的伪随机数序列，例如我们组合多个一维混沌映射模型产生多维伪随机数序列。采用它们作为伪随机数的发生方法，其产生的伪随机数既满足良好的复杂性和抗预测性能，也比较容易实现，从而方便实际应用。1 3 本文研究的主要内容及创新点本文主要讨论了基于混沌理论的无穷维伪随机数发生方法，其研究内容涉及到高等数理统计、混沌学、算法设计、保密通信等领域的理论知识。通过对混沌理论在伪随机数领域的研究，更好地了解到混沌映射模型的本质，通过组合混沌映射进行扩展，提出了基于混沌理论的无穷维伪随机数产生方法，编程实现并测试其随机序列的统计特性，并尝试在图像加密上的应用，具有一定的理论价值和应用价值。本文的主要内容和创新之处可以概述如下：1 深入研究并归纳了伪随机数的各种发生方法和混沌理论，在一维混沌映射模型的基础上，阐述了组合混沌映射的方法。2 在研究组合发生器的基础上，解释了无穷维伪随机数的概念。通过对组合混沌映射的扩展，提出了一种新的无穷维伪随机数发生方法。3 进行仿真实验，验证了该方法发生的伪随机数序列具有优良的统计特性、稳定性和安全性等性能，并能良好地应用于图像加密技术中。武汉理t 入学硕十学位论文1 4 本文的结构安排针对本文所做的研究内容和方向，各章节的安排如下：第二章中，深入地研究随机序列的产生方法及发展过程，并进行归纳总结，简单分析了常见的随机序列产生方法的优缺点。第三章中，弓l 入混沌理论，资料表明混沌是一种产生随机序列的优良工具。对简单的混沌映射模型进行理论分析，针对其存在密钥少，不安全，易攻破的缺点，提出了组合混沌映射的概念。在对组合线性发生器的研究的基础上，阐述了伪随机数的无穷维理论。并通过对组合混沌映射的扩展，提出了基于混沌理论的无穷维伪随机数产生方法。第四章中，采用m a t l a b 编程进行仿真实验，发生伪随机数序列，测试其统计特性、稳定性和安全性等性能。并尝试其在图像加密上的应用。第五章中，我们将对本文进行总结，并提出一些今后进一步工作的展望。4武汉理t 大学硕士学位论文第2 章常见伪随机数发生方法及其统计检验方法在数学，物理，工程技术，生产管理等方面问题的研究中，我们通常要以计算机为手段，采用统计模拟的方法。统计模拟方法是利用计算机产生各种不同的随机变量的抽样序列，从而建立给定问题的概率统计模型。并通过该模型，给出此问题中各种数量指标的估计值，以达到解决问题的目的。产生随机数的方法大致可分三类，即随机数表方法、物理方法和数学方法。目前，最为常用的是数学方法。用数学方法产生随机数是通过数学递推式运算实现的，因此，由此产生的随机数常称为伪随机数瞳4 川。从产生的机理上讲，它们并不具有随机性。但是这些由公式计算出来的“随机数”是否真的可以当作统计上的随机序列加以使用? 由统计假设的知识可以知道，若一个序列服从某种特殊分布，那么该序列就能够通过一系列相应的检验，因此，我们可以对该分布作一系列分布假设，如果经检验后某假设成立，则有理由认为此序列服从该分布，而不用关心其产生的机理；同样，如果经统计检验结果与该假设矛盾，那么即使该序列产生的机理是随机的，也不能将它作为给定分布的抽样序列来使用。也就是说，只要由计算机算出的序列通过了统计假设检验，我们就可以认为该序列是随机的。统计假设检验实际上给出了一个判断随机性的标准。2 1 产生伪随机数的一般方法2 1 1 随机数表从0 ，l ，9 这十个数字中，以相同概率独立地抽取一个，称为随机数字。由一系列的随机数字组成的表称为随机数表。由随机数表便可以构成任意位数的随机数。这种随机数表很多，1 9 2 7 年t i p p e t t 造出了具有4 1 0 0 0 个随机数字的表，并由剑桥出版社出版。这张已在t i p p e r 所在的伦敦大学应用统计系广泛使用的表，被称为t i p p e t t 随机数表。它是第一张公开发表的随机数字表；随后，1 9 3 8年数学家r a f i s h e r 和f 雅特斯发表了1 5 0 0 0 个补充随机数字，选自对数展开的第9 位至1 9 位小数。这些数字是通过一个涉及两副纸牌的程序获得的。1 9 3 9 年m c k e n d e l l 和b b a b i n g t o n s m i t h 用高速转盘建立了有10 0 0 0 0 个数字的随机数表。1 9 4 2 年，j g 皮特曼和r 谢菲尔发表了来自选择征兵役制抽签的1 6 0 0 个随机数字。1 9 4 9 年，洲际贸易委员会f 简称i c c ) 发表了一张由一个被称为复合随机化的过程生成的1 0 5 ，0 0 0 个随机数字的表。1 9 5 5 年兰德( r a n d ) 公司利用电子装5武汉理t 大学硕十学位论文置产生了含有一百万个数字的随机数表，制作这样大的表，目的是为了适应在用实验概率程序解决问题的过程中，对随机数同益增长的需要。在计算机上使用随机数表的方法是将随机数表输入机器中。这类方法的主要缺点是，随机数的容量往往很有限，不能满足需要。2 1 2 物理方法在计算机上安装一台物理随机数发生器后就可以直接在计算机上产生随机数。由于计算机多采用二进制，故以某种物理现象的发生与否( 也可以是否达到某种物理量的界限) 分别记为o 和1 ，用这种办法产生的0 和l 填满计算机中某一单元数字部分的所有二进制位，当发生于不发生的概率p 与口相同时，就可以得到( o ，1 ) 上均匀分布的随机数。这种物理的随机源可取质点放射源、电子管或晶体管的固有噪声等，只需采取措施保证p = 口= 1 2 即可。使用物理随机数发生器在计算机上得到需要的随机数，可节省产生随机数的时间，提高机器的使用效率。但随机数发生器需要检验和维修以保持其稳定性。另外，这种随机数不能重复发生，从而不能对模拟问题进行复算检查。最重要的是，这种随机数列有数量是否充分的问题，以及有偏差和相关性的问题，这是一个好的独立同分布的均匀随机变量所不应该有的。这些缺陷，大大降低了这类方法在计算机上使用的价值。2 1 3 数学方法数学方法就是应用数学公式迭代产生随机数，这是目前使用最广、发展最快的一类方法。当然在一台确定性的计算机上由某些数学公式得到的一列随机数不是随机的。但是，如果对公式或随机数发生方法一无所知的话，则期望这些属于一个独立同分布的均匀随机变量观测值无法辨别是可能的。因此，这罩所讨论的随机数被称为伪随机数。本文就是基于数学原理来产生伪随机数的。2 2 常见伪随机数发生器利用计算机产生伪随机数的方法称为伪随机数发生器，也是目前使用最广、发展很快的一类方法 3 0 , 4 1 】。它的特点是占用的内存少、速度快又便于复算。一个用递推公式产生具有均匀分布随机变量的独立抽样序列性质的数学方法，即一个好的伪随机数发生器应当具备以下几点：1 ) 产生的数列要具有均匀总体随机样本的统计性质，如分布的均匀性，抽样的随机性、数列问的独立性等；6武汉理工大学硕十学位论文2 ) 产生的数列要有足够长的周期，以满足模拟计算的需要；3 ) 产生数列的速度快，占用计算机的内存少，具有完全可重复性。2 2 1 线性同余法目前应用最广泛的随机数发生器之一是线性同余发生器，简称l c g ( l i n e a rc o n g r u e n c eg e n e r a t o r ) 方法。它是由l e h m e r 在1 9 5 1 年提出的，此方法利用数论中的同余运算来产生随机数，故称为同余发生器。线性同余发生器包括混合同余发生器和乘法同余发生器。一个普通混合同余发生器的循环公式如下：x n = 慨川+ c ) m o d m ，n = 1 , 2 ，3 ，( 2 一1 )我们作运算= x n m 可以得到0 到l 之闻均匀分布的随机数列。当c = 0 时，它是一个乘法同余发生器，应用更加广泛：矗= a x r lm o dm ，n = 1 , 2 ，3 ，( 2 - 2 )在乘法同余发生器中有三个基本参数：初始值，乘数a ，模m 。当基本参数给定后，伪随机数将周期性的不断循环产生。伪随机数序列的周期不超过m 。在计算机中，伪随机数序列的周期受机器字长的影响。当计算机二进制字长为k 时，由一个单独的线性同余发射器产生的伪随机数序列的周期不超过2 。统计学家发生如果我们取模为小于2 的一个素数，伪随机数的统计特性将会大大的提高。当k = 3 5 时，取模为m = 2 3 5 3 1 = 3 4 3 5 9 7 3 8 3 3 7 ，x o 为一个任意小于m 的整数，此时的l c g 为：x n = 3 1 2 5 x n 一( m o d3 4 3 5 9 7 3 8 3 3 7 ) 。常见的统计软件包中均匀随机数发生器在大多数情况下使用素数为模乘法l c g 。l c g 方法存在着一些缺点。一方面，l c g 方法产生的均匀随机数作为m ( m 1 ) 维均匀随机向量时具有明显的规律性，相关系数较大；另一方面，l c g方法产生的均匀随机数列的周期r 与计算机的字长有关。2 2 2 反馈位移寄存法1 9 6 5 年，t a u s w o r t h e ( 陶思沃思) 基于对寄存器进行位移( 递推) ，直接在存储单元中形成随机数的思想，提出了反馈位移寄存器法( f e e d b a c ks h i f tr e g i s t e rm e t h o d s ) ，简称f s r 方法或f s r 发生器。其计算公式如下；口t2 k p 口i p + c p - ! 口i p + l + + c i 口i 1 ) m o d 2 ，忙o j( 2 3 )对寄存器中的二进制数码口。作递推运算，其中p 是给定正整数，c 。= l ，c i = 0 或1 ( i = 1 ，p 一1 ) 为给定常数。给定初值似卅口叫l ，一，口。) ，此递推公式产生了一个由0 和l 组成的序列 口， ，我们按下面的方式用k 产生一个整数序列k ：，= m 2 k - i , o = l ，2 州3 )k = l7，( 2 4 )武汉理工大学硕士学位论文其中，是预先给定的一整数，现然，对任意f ，有o 一 - 2 7 。令= x , 2 7 ，( f = l ，2 3 ) ，我们就得到了【o ，1 ) 上的序列纯 ，并可将其作为【0 ，1 ) 上的相互独立同均匀分布的随机数序列。通过改变p 及c 。，c ：，c p 的值；将得到不同的f s r发生器。f s r 虽然具有速度快、与计算机字长无关、多维均匀性好等优点，但是其序列的随机性对初始值的依赖性很强。2 2 3 非线性与逆同余法8 0 年代末开始，许多学者讨论称之为逆同余的一类新发生器，这是非线性同余类中最有前途的一种。( 1 ) 非线性同余发生器记z m = o ，l ，m l ，这是一个m 阶有限域，同余发生器有如下形式：x 州= f ( ，) m o d m ，= x i m ，f = o ，l ，。其中x i z ，而是z ，上的一个整数值。若f ( x i ) = a x i + c ，则上式就是前节定义的线性同余发生器。在非线性同余中fj l r ! l 糇e z 肼上的一个排列多项式，这时有沙( o ) ，( 1 ) ，厂( 膨一1 ) ) = z m 。( 2 ) 逆同余发生器逆同余发生器是非线性同余类中目前研究得最多，并且也是最有自 f 途的一种。对于c z 材( m 为素数) ，定义巧= l m o d m 且石z m ( 若c = 0 ，定义石= o ) ，这是称石为c 关于模m 的乘法逆。下面是逆同余发生器的递推式( 常数口，b z w ) ：x f + l = l 崩，+ b m o d m ，扛0 ，l ，。2 2 4 组合发生器尽管人们提出了各种随机数发生器，但是每种发生器都有自己的缺点，如果希望得到周期更长，随机性更好的均匀随机数，有人建议先以一个随机数发生器产生的随机数列为基础，再用另一个发生器对随机数列进行重新排列得到的新数列作为实际使用的随机数，这种把多个独立的发生器以某种方式组合在一起来产生随机数，希望能够比任何一个单独的随机数发生器得到周期更长、统计性质更优的随机数，这就是组合发生器的思想。( 1 ) 二个发生器的组合最著名的组合发生器是组合同余发生器，用第二个l c g “搅乱 由第一个l c g 产生的随机数，它是由m a c l a r e n 和m a r s a g l i a 在1 9 6 5 年提出的，其算法如下；假设有2 个同余发生器，它们分别产生的序列x i ) 和) ，构造一个k 元素表t = ( t if ：，t t ) ，开始时，r 用扛， 的前k 个数构成，并令刀= l ，然后执行以下步骤：8武汉理t 大学硕十学位论文1 ) 产生下一个x 和y ( 即b ， ， 中除前面用过的数以外的下一个随机数) ；2 ) 在y 中随机选取一个整数，要求l j k ；3 ) 令= t ，然后再用第二个l c g 产生一个随机数y ，令f ，= y ，刀= 以+ l ；4 ) 重复( 2 ) ( 3 ) ，得随机数列 x n ，即为组合同余发生器产生的数列。若第一个l c g 的模为m ，令= x n m ，则 ) 为均匀随机数。在上述算法中，第二个l c g 的目的是用它产生的y 打乱 x ， 的排列次序，增强了其随机性，周期增大的性质。根据打乱次序的原则，我们还可以构造其它组合发生器，如w e s t l a k e 组合发生器，b a y s 和d u r h a m 提出的用一个l c g 和一个f s r 发生器组合起来的发生器等，在此不多作介绍了。总之，这种组合大大增加了单个发生器的周期和随机性，算法实现也较简单。g r e e n w o o d 在1 9 7 6 年用两个满周期的混合同余发生器构成组合同余发生器，两个混合式发生器的周期都为2 ，时，组合同余发生器的周期达到2 p ( 2 p 1 ) 。 2 ) 多个发生器的组合1 9 7 4 年，s a l f i 提出了由多个发生器的组合产生随机数的方法。首先，我们构造疗个达到最大周期2 的线性同余发生器，这n 个发生器的乘子a ，a ：，a 。选取互不相同，满足口i = o ，口2 = 1 ，并使得2 9 一口l ，2 9 一口2 ，2 9 一口。，( 1 q 五) - 口，否定域形= “0 五抛= l ，2 ，3 ) 。由随机数序列扛， 计算“- ，”：，“，的值，若m a ，则认为产生的随机数序列的特征量与均匀总体的特征量没有显著差异；否则，由于b 0 的特征量与均匀总体特征量有显著差异，故不能认为& ， 是均匀总体的简单样本。2 3 2 均匀性检验随机数的均匀性检验又称为频率检验，它用来检验由某个发生器产生的随机数序列扛， 是否均匀地分布在( 0 ，1 ) 区间上，也就是检验经验频率与理论频率的差异是否显著。此时我们假设娥：扛， 均匀地分布在( 0 ，1 ) 上。下面我们用z 2 检验的方法来寻找此假设下的统计量及其分布。我们先将( o ，1 ) 等分成后个子区间o ，：，量即有：u ，。= ( o ，1 ) 。1 0武汉理- 1 人学硕士学位论文记扛， 中落入区间，上的样本个数为：玎，o = l ，2 ，七) 这样就将& ， 分成了后组，其中第组o = 1 , 2 ，k ) 由落入，中的点组成，显然，在h o 的假设下，样本落入区间的概率乞= i 1 ，令样本落在任一个区间的平均数肌= 啤= i n ，其中n 是序列扛， 的长度。由z 2 分布的知识阮习可以知道：铲骞学= 专* 一譬) 2仁5 ，上式渐近服从z 2 亿一1 ) ，其中z 2 及其渐近分布就是要求的检验统计量及其渐近分布，由此可以给定显著性水平仿，查z 2 分布表得临界值后，即可说明其均匀性。2 3 3 独立性检验独立性检验主要检验随机数列k y _ f , 的统计相关性是否显著，检验的方法有多种，我们通常采用的是相关系数检验法，本文运用此种方法进行独立性检验。两个随机变量的相关系数反映它们之间线性相关程度，若两个随机变量独立，则它们的相关系数必为零( 反之不一定) ，故可以利用相关系数束检验随机数的独立性。设，x 2 ，x n 是一组待检验的随机数，假设矾：自相关系数p = 0 ，考虑样本的后阶自相关系数【1 】：n = 丢喜g ，一元( x j - s 伍- 1 2 ，m 坍( 2 - 6 )其中，= o + 后) m o d 拧，s 2 = 寺喜( 一一孑) 2 。记g = 吉喜_ x ，则n = c g 一膏2 ，s 2 ( g 一三) 壶可以证明：e ( g ) = i 1 ；玩r 心) = 西1 石3 ，这时检验假设娥：e 慨) = o 可以用检验假设h 。：e ( q ) = i 1 来代替，检验统计量取为铲m a x ( c _ 1 i1 3 幺，朋 ，( q 一丢) 怎u 亿7 ，汞i 用公式f 2 7 1 中的统计量“。可进行相关性检验。武汉理工大学硕： ：学位论文第3 章基于混沌理论的无穷维伪随机数发生方法自从混沌理论深入到各个研究领域而成为一门新兴交叉学科以来，人们对利用混沌系统生成随机序列产生了浓厚的兴趣，掀起了一股新的热潮。有研究表明，混沌系统是一类天然的性能优良的随机序列发生器模型。它的非周期、类噪声、宽频谱、对初始条件的敏感等特性与随机序列的性质是基本吻合的，在这方面的研究引起了学术界的广泛关注，已经有相当一批有实力的科研机构投入到这一领域的研究中来。然而混沌是- f - 复杂深奥的理论，除简单混沌映射模型外，还有很多更为复杂的混沌系统。基于混沌理论产生随机数，生成方式简单，快速，易于实现，初始化参数的微小改变将导致伪随机数序列的很大变化，使得系统具有很高的安全性。本课章将对简单的混沌映射模型进行理论分析，针对其存在密钥少，不安全，易攻破，初始值要求严格等缺点，阐述了组合混沌映射的方法。在对组合线性发生器研究的基础上，解释了无穷维伪随机数的概念。并通过对组合混沌映射的扩展，提出了一种新的基于混沌理论的无穷维伪随机数发生方法。3 1 混沌的定义及其基本特性3 1 1 混沌的定义近5 0 年以来，研究学者对混沌系统运动的规律及其在社会科学和自然科学中的应用有了更加深刻的认识。虽然如此，但目前为止，还是没有确定一个普遍认可的比较严谨的标准数学定义。这是因为混沌系统本身非常复杂，而从不同的角度理解会得到不同的认识。各个领域的科学家对混沌系统做出了不同的定义，他们从各个侧面反映了混沌系统的性质，其中l i - y o r k e 的混沌定义f 2 9 3 1 1 是最具代表性、影响力最深远的。早在1 9 7 5 年，华人数学家李天岩和y o r k e 在论文周期三意味着混沌中第一次明确给出了混沌系统的种数学定义。l i y o r k e 定理：设厂b ) 是【口，6 】上的连续自映射，若厂b ) 有3 周期点，则对任何正整数n ，厂( x ) 有n 周期点。混沌定义如下：闭区间，上的连续自映射厂( x ) ，如果满足下列条件，便可确定它有混沌现象：( 1 ) 厂b ) 的周期点的周期无上界。g ) 具有任意正整数周期的周期点，即对任意自然数以，有x i ，使f 4 x ) = x ( 非不动点的以周期点) ；( 2 ) 闭区间，上存在不可数子集s ，满足：对任意x ，y s ，当x y 时，有1 2武汉理t 入学硕十学位论文l i m s u p l 厂“( x ) - s “卜o ；对任意x , ys ，有l i m i n f i f ”g ) 一f “) i = 0 ；对任意i y s 和的任一周期点少，有l i m s u p f ”g y 二7 ”) | 0 。根据上面介绍的定理和定义，对团区间，上的连续函数厂b ) ，如果存在一个周期为3 的周期点时，就一定存在任何正整数的周期点，即一定存在任何j 下整数的周期点，即一定出现混沌现象。一般地，如果一个比较接近实际情况的确定性的系统仍具有貌似随机的行为，就可以认为此系统是混沌的。一个随时间而变化的系统，称为动力学或动态系统，它的状态可由一个或几个数值变量确定。在一些动力学系统中，两个只有细微差别的初始状态经过很长时间后会变得毫无相似之处，可称这种系统具有对初始条件的敏感依赖性，而对初始条件的敏感依赖性也可作为混沌的一个定义。3 1 2 混沌的基本特性与其它一些复杂现象相别，混沌有着其独有的特征【4 2 , 4 4 】：( 1 ) 混沌的统计特征混沌系统对初始值具有极端敏感性，它具有正的l y a p u n o v 指数。l y a p u n o v指数衡量在相空间中初始条件不同的两条相邻轨迹随时问按指数律收敛或发散的程度。在l y a p u n o v 意义下，系统不稳定，即系统的长期特性不可预测。( 2 ) 混沌的有界性与混沌相对应的点的集合在相空f 日j 中具有有限一个分布，这个区域称为混沌吸引域。无论混沌系统内部多么不稳定，它的轨线都不会走出吸引域。所以整体上说混沌系统是稳定的。( 3 ) 混沌的内随机性系统处于混沌状态，是由系统内部动力学随机性产生的不规则行为，与系统外部因素无关。( 4 ) 混沌的分维性混沌运动是有限范围内形态复杂的非周期运动，运动轨线具有多叶多层的结构，分维性是描述其复杂性的指标。( 5 ) 混沌的普适性普适性指不同的系统在趋向混沌念时所表现出来的某些共同特征，它不以具体的系统方程或参数而变。具体体现为几个混沌普适常数，如著名的f e i g e n b a u m常数。普适性是混沌内在规律的一种体现。( 6 ) 混沌的遍历性混沌运动在其混沌吸引域内各态历经，即在有限的时间内混沌轨道经过混沌区内每一个状态点。武汉理丁大学硕十学位论文3 2 几种常见的混沌系统模型混沌系统大体有两类：以状态方程描述的离散时间系统和以微分方程描述的连续时间系统。接下来本文将介绍几种经典的发生伪随机数的混沌模型，按照维度分为一维模型和高维模型【3 j 6 1 。3 2 1 一维经典混沌映射模型( 1 ) 一维l o g i s t i c 映射模型：厂g ) = 脬( 1 一x )( 3 1 )式中0 4 ，称为分形参数。当3 5 6 9 9 a 4 时，系统结果处于混沌状态。( 2 ) t e n t 映射模型：确= i | ：肌口) ： x 删k ao 1 0 或a = 1 , b 0 5 时，所得序列就可以通过均匀性统计检验。3 2 2 高维经典混沌映射模型( 1 ) h e n o n 映射模型：1 4武汉理= 人学硕士学位论文i + i = l 一群+ 只【咒+ ，= 帆式中，a , b 为混沌参数。考虑h e n o n 映射的离散一维差分方程：+ l = l 一瞩2 + 魄一i当参数d = 1 4 ，b = 0 3 时系统处于混沌状态。( 2 ) l o r e n z 微分方程模型：( 3 - 6 )( 3 - 7 )害= 口一工)d y i ：一滋一少( 3 - 8 ) r x=一滋一 ，出生：肼一6 zd t。式中，当a = 1 0 ，b = 8 3 ，= 3 4 时系统处于混沌状态。由于多维模型的复杂，为了方便研究，本文只对维经典混沌映射模型进行研究，主要是一维l o g i s t i c 映射和一维无限折叠混沌映射，在下一节有更详细的介绍。3 3 组合混沌映射模型本节首先详细介绍一维l o 昏s t i c 混沌映射和一维无限折叠混沌映射的理论知识，然后阐述了组合混沌映射的概念。3 3 1 一维l o g i s t i c 混沌映射l o g i s t i c 混沌映射是一类非常简单却被广泛研究的动力系统，其定义与公式( 3 i ) 相同，如下：以卅= 肛t ( 1 一x i )其中，0 2 5 6 9 9 4 5 6 时，序列x 0 ，_ ，吒如同分布在区间( o ，1 ) 上的随机数，称为混沌态。有研究【h , 2 6 , 3 6 j 表明，当且仅当z = 4 时，映射具有最强的混沌特性，所以在后面的研究中我们一般取= 4 。1 5武汉理j ：人学硕十学忸论文“图3 - 1l o s i s i t i c 混沌映射的倍周期分岔图我们给定以初值代入混沌映射模型中，选代得到一个序列扛。 如图3 - 2 所示，该运动轨迹既不收敛也不呈周期运动状态，而是表现出一种“杂乱无章”的形式。图3 - 2l o g i s t i c 混沌映射产生的混沌序列时序图旨ijij；iiioijlllolliiijiimmmmi?iii4川舢竺!”川i卜=：0i雌钏川jij=|川盎躲辨l0_i?三，iii_jji州iiii筑l，iiiiiiij)9”iiiiiij，f，洲锨_：_川，盎。一iiji蒯iiii=_iiii，lljfo ii=二二i，i二j，|i，；，21；iijlji=l0二二州!三兰倒酣if怡i iiii“iiiiijjijijj!ii删粕；=jiii川i一