第1章 混沌理论基础与混沌密码学的发展

混沌是一种貌似无规则的运动，指在确定性非线性系统中，不需要附加任何随机因素也可能出现类似的随机行为（内在随机性）[1]。混沌科学是随着现代科学技术的迅猛发展，尤其是在计算机技术的出现和普遍应用的基础上发展起来的新兴交叉学科。在物质世界中，混沌现象无处不在，大至宇宙，小至基本粒子，无不受混沌理论的支配。数学、物理、化学、生物、哲学、经济学、社会学、音乐、体育等领域中均存在混沌现象，它打破了不同学科之间的界线，是涉及系统总体本质的一门新兴学科。

在现代社会，最早研究混沌理论的学者是法国数学家庞加莱（H. Poincare），他于1913年在研究能否从数学上证明太阳系的稳定性问题时，把动力学系统和拓扑学有机地结合起来，并提出三体问题在一定范围内的解是随机的，这实际上是一种保守系统中的混沌。1927年，丹麦电气工程师Van del Pol在研究氖灯张弛振荡器的过程中，发现了一种重要的现象并将它解释为“不规则的噪声”，即所谓Van del Pol噪声。1954年，前苏联概率论大师柯尔莫哥洛夫（Kolmogorov），在探索概率起源的过程中，提出了KAM定理的雏形，为早期明确不仅耗散系统有混沌现象而且保守系统也有混沌现象的理论铺平了道路。1963 年，美国麻省理工学院的气象学家洛伦兹（Lorenz）在研究大气环流模型的过程中，提出了“决定论非周期流”的观点，讨论了天气预报的困难和大气湍流现象，给出了著名的洛伦兹方程[2]。这是第一个在耗散系统中由一个确定的方程导出混沌解的实例，从此以后，关于混沌理论的研究正式揭开了序幕。

1.1 混沌理论基础

1.1.1 混沌的定义

混沌一词最早由李天岩(Li T Y)和约克(Yorke J A)于1975年提出。他们在“周期三意味着混沌”的文章中给出了混沌的一种数学定义[3]，现称为Li-Yorke定义：

区间I上的连续自映射 f(x)，如果满足下面条件：

① f 的周期点的周期无上界；

② 闭区间I上存在不可数子集S，满足：

1）∀x,y∈S,x≠y时，；

2）∀x,y∈S，；

3）∀x∈S和 f 的任意周期点y，有；

则称f在S上是混沌的。

在此定义中，前两个极限说明子集的点 x, y∈S 相当分散又相当集中；第三个极限说明子集不会趋近于任意周期点，所以此定义只预言了非周期轨道的存在，但不涉及这些非周期点的集合是否具有非零测度，也不涉及哪个周期是稳定的。所以Li-Yorke定义的缺陷在于集合S的勒贝格测度可能为零，即此时的混沌是不可观测的，而人们感兴趣的是可观测的情形，即S有一个正的测度。

根据Li-Yorke定义，美国学者Richard H. Day认为混沌系统应具有如下性质[1]：第一，存在所有阶的周期轨道；第二，存在一个不可数集合，该集合只含有混沌轨道，且任意两个轨道既不趋向远离也不趋向接近，而是两种状态交替出现，同时任一轨道不趋于任一周期轨道，即该集合不存在渐近周期轨道；第三，混沌轨道具有高度的不稳定性。

1989年Devaney R. L给出了混沌的又一种定义[1]：

设V是一个度量空间，连续映射 f ∶V →V，如果满足下面3个条件，则称 f 在V上是混沌的：

1）对初值的敏感依赖性：存在δ＞0，对于任意的ε＞0和任意x∈V，在x的ε邻域内存在y和自然数n,使得d(fn(x),fn(y))＞δ；

2）拓扑传递性：对于V 上的任意一对开集 Z , Y∈V , 存在 k＞0，使fk(Z)∩Y ≠Φ；

3）f的周期点集在V中稠密。

对于初值的敏感依赖性，意味着无论x,y离得多么近，在 f 的作用下，两者的轨道都可能分开较大的距离，而且在每个点x附近都可以找到离它很近而在 f 的作用下最终分道扬镳的点y。对这样的 f，如果用计算机计算它的轨道，任何微小的初始误差，经过若干次迭代以后都将导致计算结果的失效。

拓扑传递性意味着任一点的邻域在 f 的作用之下将“撒遍”整个度量空间V，这说明 f 不可能细分或不能分解为两个在 f 下不相互影响的子系统。

一般而言，上述两条是随机系统的特征，但第三条——周期点集的稠密性，却又表明系统具有很强的确定性和规律性，绝非一片混乱，而是形似紊乱实则有序，这也正是混沌的耐人寻味之处。

除了上述对混沌的定义之外，还有诸如Smale马蹄、横截同宿点、拓扑混合以及符号动力系统等定义。然而，迄今为止，混沌一词还没有一个公认的普遍适用的数学定义[4, 5]。多数学者认为，给出混沌的精确定义是一件相当困难的事情，因为：不使用大量的技术术语不可能定义混沌；从事不同领域的人使用的混沌定义有所不同。突变论的创始人Thom更是认为“混沌”不可能有严格的数学定义。当前，尽管混沌尚无精确的定义，但从事不同领域研究的学者却已基于各自对混沌的理解进行了研究并谋求各自的应用。

1.1.2 混沌的运动特征

混沌运动是确定性非线性系统所特有的复杂运动形态，出现在某些耗散系统、不可积Hamilton保守系统和非线性离散映射系统中。混沌是一种不稳定的有限定常运动，它的定常状态不是通常概念下确定性运动的三种状态：静止（平衡）、周期运动和准周期运动，而是一种始终局限于有限区域且轨道永不重复的、形态复杂的运动。为了与其他复杂现象相区别，混沌运动有着自己独有的特征[6-9]：

① 有界性：混沌是有界的，它的运动轨道始终局限于一个确定的区域，这个区域称为混沌吸引域。无论混沌系统内部多么不稳定，它的轨道都不会走出混沌吸引域。所以从整体上说混沌系统是稳定的。

② 内随机性：在完全确定的系统内部产生的随机性被称为内随机性。混沌常被称为自发混沌、确定的随机性等，主要强调的就是混沌现象产生的根源在系统自身，而不是外部的影响。内随机性的另一方面是局部不稳定性。所谓稳定性是指系统受到微小扰动后保持原状态的属性或能力。所谓局部不稳定性是指系统运动的某些方面（如某些维度上）的行为强烈地依赖于初始条件。即初始条件的任何微小变化，经过混沌系统的不断放大，都有可能对其未来的状态造成极其巨大的差别。正是由于混沌轨道的不稳定性和对初始条件的敏感性，故不可能对混沌系统的长期行为进行预测。

③ 分维性质：混沌具有分维性质，但其非整数维不是用来描述系统的几何外形，而是用来描述系统运动轨道在相空间的行为特征。系统变化在相空间中可用一条轨道线来描述。混沌运动在相空间中某个区域内无限次的折叠，构成一个有无穷层次的自相似结构——奇怪吸引子。

④ 普适性：在混沌的转变中出现某种标度不变性，代替通常的空间或时间周期性。所谓普适性，是指不同系统在趋向混沌时所表现出来的共同特性，它不以具体的系数及系统的运动方程而变。普适性有两种，即结构的普适性和测度的普适性。前者是指趋向混沌的过程中轨线的分岔情况与定量特性不依赖于该过程的具体内容，而只与它的数学结构有关；后者是指同一迭代在不同测度层次之间的嵌套结构相同，结构的形态只依赖于非线性函数展开的幂次。

⑤ 遍历性：混沌运动在其混沌吸引域内是各态历经的，即在有限时间内混沌轨道经过混沌区内每一个状态点。

1.1.3 混沌的判断准则

混沌来自于系统的非线性性质，但是非线性只是产生混沌的必要条件而非充分条件。那么，对于一个给定系统该如何判断它是否具有混沌特性？以及能否用数学语言说明混沌运动并对它进行定量刻画呢？这是混沌学研究的重要课题之一。下面将介绍几种常用的可作为混沌诊断与判据的方法[1, 6-11]。

① Lyapunov指数

对于非线性动力学系统的完善定性描述，由于可能出现不规则运动而成为一个似乎是不可能解决的问题。如果附加应用统计方法，情况会好一些。目前在表征混沌运动方法方面，显示出重大意义的统计特征值之一是Lyapunov指数。它是相空间中相近轨道的平均收敛性或平均发散性的一种度量。

设F是Rn→Rn上的n维映射，它决定着一个n维离散动力系统：

将系统的初始条件设为一个无穷小的n维的球，由于演变过程中的自然变形，球将变为椭球。将椭球的所有主轴按其长度顺序排列，那么第i个Lyapunov指数根据第i个主轴的长度Pi(n)的增量加速率定义为：

Lyapunov指数是与相空间的轨道收缩或扩张相关联的，在Lyapunov指数小于零的方向上轨道收缩，运动稳定，对初值不敏感；而在Lyapunov指数为正的方向上，轨道迅速分离，对初值敏感。通常将这 n个Lyapunov指数按从大到小的顺序进行排列，将它们称之为Lyapunov指数谱：

LE1 ≥ LE2 ≥ …≥ LEn

对于混沌，必定有一个Lyapunov指数是正的。因此，人们只要在计算中得知吸引子中有一个正的Lyapunov指数，即使不知道它的具体大小，也可以马上判定它是奇怪吸引子，而运动是混沌的。

由于工程中常通过计算最大Lyapunov指数来判断系统是否是混沌的，因此这里简要介绍一下一维混沌系统、差分方程组和微分方程组计算Lyapunov指数的方法。

1）一维混沌系统计算Lyapunov指数

考虑一维映射：xn+1=F(xn)，假设xn有偏差dxn，并导致xn+1偏差dxn+1，则：

xn+1+dxn+1=F(xn+dxn)≈F(xn)+dxn · F′(xn)，即dxn+1=dxn · F′(xn)

设轨道按指数规律分离，即

其中LE为Lyapunov指数。为了得到稳定的值，通常要取足够的迭代次数：

因此

2）差分方程组计算Lyapunov指数

设Rn空间上的差分方程：xi+1= f(xi)，f 为R n上的连续可微映射。f 的Jacobi矩阵为：

令

将Ji的n个复特征根取模后，依从大到小的顺序排列为：

那么，f 的Lyapunov指数定义为

该定义是计算差分方程组的最大Lyapunov指数LE1的理论基础。

3）微分方程组计算最大的Lyapunov指数

设在由给定微分方程组所确定的相空间中，选取两条相轨迹起点差距为d0，经过时间τ后，呈指数分离，差距为dτ，即

则Lyapunov指数为

数值计算时，从一条参考轨迹上找一个起点，算出相邻相轨的d0、dτ，若dτ不按指数增长，另找新起点计算d0、dτ，为避免计算时出现发散，经过时间τ后，选取一个新起点，但与参考相轨迹的距离保持为d0。这样每次都是从距离为d0的两个状态出发，得到一系列d1,d2,…,dj,…最后按下式平均，得到最大Lyapunov指数：

当d0很小，而循环次数n极大时，只要τ不太大，计算结果就与τ的大小无关。利用计算机可以实现这种算法，得到一个可靠的LE1，进而可以判断系统运动是否为混沌的。

② Kolmogorov熵

考虑一个n维动力系统，将它的相空间分割为多个边长为ε的n维立方体盒子，对于状态空间的一个吸引子和一条落在吸引域中的轨道x(t)，取时间间隔为一个很小量t，令P(i0,i2,…id)表示起始时刻系统轨道在第i0格子中，t=1时在第i1个格子中…，t=d时在第id个格子中的联合概率，则Kolmogorov熵定义为

由K熵的取值可以判断系统运动的无规则程度。对于确定性系统规则运动（包括不动点、极限环、环面），其K熵为0；对于随机运动，其K熵趋于无穷；当K熵为一正数时则为混沌运动，且K熵值越大，混沌程度越严重。

③ 功率谱法

功率谱是一种表征复杂时间序列特征的统计量，是研究混沌的一种重要手段，也是计算机实验和实验室观测分岔和混沌的重要方法。下面简要介绍实际测量功率谱的计算方法。

在实际测量中得到的往往是按等时间间隔t的时间序列x1, x2, …, xN。对此序列人为地加上周期边界条件xN+j = xj, 对任意的j，计算其自相关函数，即离散卷积

再对cj做离散傅里叶变换，计算其傅里叶系数：

pk表示第k个频率分量对xi的贡献，即功率谱的本来意义。利用快速傅里叶变换，更有效的计算功率谱的方法是不经过自相关函数，直接求xi的傅里叶系数，即

然后，计算，由许多组{xi}得到一批，计算其平均值即可得到前面定义的功率谱pk。

对于周期运动，功率谱只在基频及其倍频处出现尖峰。准周期对应的功率谱在几个不可约的基频以及由它们叠加的频率处出现尖峰。混沌运动的功率谱为连续谱，会出现噪声背景和宽峰。

④ 庞加莱截面法

通过相空间的几何直观方法可表述动力学系统的各种形态。利用这种相图的方法可以把复杂运动简化。但是对于有些复杂运动，利用此方法进行研究是非常困难的，比如某些倍周期运动的倍数是很高的，其轨道看起来可能很乱，很难与非周期运动相区别，此时可用庞加莱截面方法进行研究。

在多维相空间(x1,dx1/dt,x2,dx2/dt,…,xn,dxn/dt)中适当选取一截面，在此截面上某一对共扼变量如x1,dx1/dt取固定值，称此截面为庞加莱截面。运动轨迹与此截面的交点称为庞加莱点。设记录得到的庞加莱点依次为P0,P1,…,Pn,…。原来相空间的连续轨迹在庞加莱截面上便表现为一些离散点之间的映射Pn+1=TPn，由它们可得到关于运动特性的信息。只考虑庞加莱截面上的稳态图像，当庞加莱截面上只有一个不动点和少数离散点时，可判定运动是周期的；当庞加莱截面上是一封闭曲线时，可判定运动是准周期的；当庞加莱截面上是成片的密集点，且有层次结构时，可判定运动处于混沌状态。

⑤ 分维数分析法

分形理论是描述混沌信号的另一种手段。分形是没有特征长度但具有一定意义的自相似图形的总称。分形最主要的特性是自相似性，即局部与整体存在某种相似。

混沌的奇怪吸引子是轨道在相空间中经过无数次靠拢和分离，来回拉伸与折叠形成的几何图形，具有无穷层次的自相似结构。这种几何结构可用分维来描述，因此可以通过计算奇怪吸引子的空间维数来研究它的几何性质。

分维定义很多，常有以下几种形式：

1）盒维数：这是应用较广泛的维数概念之一。设 A是 Rn空间的任意非空有界子集，对每一ε ＞ 0，N(A, ε)表示用来覆盖A的半径为ε的最小封闭球数，如极限存在，则称：

为盒维数。在实际计算中，可以构造一些边长为ε的盒子，然后计算不同ε值的盒子与A相交的个数N(A, ε)，然后以-ln ε为横轴，lnN(A,ε)为纵轴描出[-ln ε, ln N(A,ε)]，根据这些点组成的图形的斜率，便可以估计图形A的盒维数。

2）相似维数：由所有局部与整体相似的图形所组成的集合被称为自相似集。相似维数的定义为：

其中，m是自相似集F中的相似子集的个数，c为相似比例系数。

3）关联维数：关联维数是从实验数据中直接测定的一种维数，它较易计算，故应用很广，为描述复杂分形提供了一种新的手段。1983年，Grassberger和Procaccia提出了从时间序列中计算吸引子的关联维数的G-P算法。现简要介绍如下：

对于n维重构混沌动力系统，奇怪吸引子由点yj = (xj , xj+t , xj+2t , …, xj+(n-1)t)所构成。在构造好矢量yj之后，需要先定义它们之间的距离。不妨将两个矢量的最大分量差作为距离，即，并规定：凡是距离小于给定正数r的矢量，称为关联矢量。设重构相空间中有N个点(即矢量)，计算其中有关联的矢量对个数，它在一切可能的N2种配对中所占的比例称为关联积分

式中θ为Heaviside单位函数：

关联积分Cn(r)在r→0时与r存在以下关系：

式中D称为关联维数，恰当选取r，使得D能够描述混沌吸引子的自相似结构。由于式(2.19)有近似数值，故可得关联维数的计算关系

4）Lyapunov维数：从几何直观考虑，正Lyapunov指数代表的方向对吸引子起支撑作用，而负Lyapunov指数对应的收缩方向，在抵消膨胀方向的作用后，提供吸引子维数的非整数部分。因此，将Lyapunov指数从最大的LE1开始，把后继的Lyapunov指数一个个加起来。若加到LEK时，和为正数，而加到下一个LEK+1后，和变成负数，则可以用线性插值来确定维数的非整数部分。吸引子的Lyapunov维数定义为：

式中k为成立的最大整数。

Lyapunov维数对描述混沌吸引子非常有用，对n维相空间来说有以下结论：

定常吸引子：LE1 ＜ 0, LE2 ＜ 0, …, LEn ＜ 0，此时Lyapunov维数为0，对应于平衡点（不动点）。

周期吸引子：LE1 = 0, LE2 ＜ 0, LE3 ＜ 0, …, LEn ＜ 0，此时Lyapunov维数为1，对应于极限环（周期点）。

准周期吸引子：LE1 = 0, LE2 = 0, …,LEk = 0, LEk+1 ＜ 0, …,LEn ＜ 0，此时Lyapunov维数为k，对应于环面（准周期吸引子）。

混沌吸引子：有0＜k＜n且Sk＜-LEk+1=|LEk+1|，此时Lyapunov维数总是分数（k ＜dk+1 ＜ k+1）。