《浙大城院数学建模ppt课件.ppt》由会员分享，可在线阅读，更多相关《浙大城院数学建模ppt课件.ppt（89页珍藏版）》请在三一办公上搜索。
1、09:22:48,MCM,1,第四章、线性代数模型, 4.1 几个数学游戏 4.2 Drer魔方(或幻方)问题 4.3 密码的设计、解码与破译 4.4考虑年龄结构的人口模型(Leslie模型),09:22:48,MCM,2, 4.1 几个数学游戏,向量、向量空间、矩阵等都是线性代数中的重要概念，本节将通过一些简单的实例来说明它们在实际中的应用。,例4.1 人、狗、鸡、米过河问题,这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除了需要有人去划以外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。 要知道例4.1的答案并不困难。第一次，人只能带鸡过
2、河。到了对岸，人只有自己回来，将鸡留在对岸，否则，又返回了初始状态。,09:22:48,MCM,3,接下来，人可以带狗过河，也可以带米过河，但回来时有一定要将鸡带回，按此推导下去，读者不难找到过河方法。我们研究本例的目的不在于找出答案，而是想设计出一种让计算机自行搜索寻找答案的方法。为此目的，我们先把例1转化为状态转移问题。首先，应当如何表达状态呢？不同的情况应采取不同的方法，在本例中，人鸡狗米都只有两种可能状态，即在此岸或在彼岸（不在此岸）。我们将用向量来表示状态，可采取如下方法：一物在此岸时相应分量取1，而在彼岸时则相应分量取为0，例如（1,0,1,0）表示人和鸡在此岸，而狗和米则在彼岸。
3、,09:22:48,MCM,4,(i) 可取状态：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态，因为狗会咬鸡。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：,总共有十个可取状态。对一般情况，也可找出状态为可取的充要条件，让计算机根据充要条件来检查得到的状态是否为可取状态。,09:22:48,MCM,5,(ii) 可取运算：状态转移需要经过状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此再引入一个四维向量(转移向量)，用它来反映摆渡情况。例如(1，1，0，0)表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有(1，0，0，0)、(1
4、，1，0，0)、(1，0，1，0)、（1，0，0，1)四个。,为实现本题中的状态转移，规定一个状态向量与转移向量之间的运算。规定状态向量与转移向量之和为一新的状态向量，其运算为对应分量相加，且规定0+0=0，1+0=0+1=1，1+1=0。例如(1，1，1，1)+(1，0，1，0)=(0，1，0，1)，其实际意义为人狗鸡米原来均在此岸，人带鸡过河，转变为新的状态此岸仅剩狗和米，(注：此处作这样的运算规定完全是为了与实际情况相符)。,09:22:48,MCM,6,在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态(1，1，1，1)出发，经过奇数次的上述运算能否转化为(0，0，0
5、，0)的转化问题，进而，如果能，我们还想知道具体应当如何转化 。,由于规定的运算十分容易在计算机上实现，这样一来就把一个数学游戏转化为了一个可以在计算机上计算的数学问题(即建模)。当然，像本题这样简单的问题，也可通过笔算方法求解，具体可如下进行分析,(第一次渡河),09:22:48,MCM,7,(第二次渡河),以下可继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。,09:22:48,MCM,8,例4.2 夫妻过河问题,这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男
6、子在一起，问此时这三对夫妻能否过河？,这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同样要反映出性别，故可如下定义：,(i) 可取状态：用H和W分别表示此岸的男子和女子数，状态可用矢量(H，W)表示，其中0H、W3。可取状态为(0,i)，(i,i)，(3,i)，0i3。(i,i)为可取状态，这是因为总可以适当安排而使他们是i对夫妻。,09:22:48,MCM,9,(ii) 可取运算：过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移向量可取成(1）im, (1)in），其中m、n可取0、1、2，但必须满足1m+n2。当j为奇数时表示过
7、河。当j为偶数时表示由对岸回来，运算规则同普通向量的加法。问题归结为由状态(3,3)经奇数次可取运算，即由可取状态到可取状态的转移，转化为(0,0)的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还可用作图方法来求解。,09:22:48,MCM,10,在HW平面坐标中，以“”表示可取状态，从A(3,3)经奇数次转移到达O(0，0)。奇数次转移时向左或下移动1-2格而落在一个可取状态上，偶数次转移时向右或上移动1-2格而落在一个可取状态上。另外，由于奇数次与偶数次过河产生的效果是不同的，为了区分起见，用实箭线表示奇数次转移，用虚箭线表示第偶数转移，图4-1给出了一种可实
8、现的方案，故,09:22:48,MCM,11,（图4-1）,09:22:48,MCM,12,关于夫妻过河还可以编出许多其他形式的问题，下面我们来讨论一些同样有趣的问题。为了叙述简便，先约定一些符号，这些符号将被应用于以下的各个问题之中。记想过河的夫妻对数为n，船可载的人数为m，n对夫妻过河所需的最少摆渡次数为k。,这三对夫妻是可以过河的。假如按这样的方案过河，共需经过十一次摆渡。,不难看出，在上述规则下，4对夫妻就无法过河了，读者可以自行证明之。类似可以讨论船每次可载三人的情况，其结果是5对夫妻是可以过河的，而六对以上时就无法过河了。假如船每次可以载四人，则任意多对夫妻均可过河，最易看出的一个
9、方案是让一对夫妻当船员工即可。,09:22:48,MCM,13,(问题1) 2对夫妻要过河，船每次只能渡2人，应如何过河，最少摆渡几次？(即n=2，m=2，求k=?),本问题很容易解答，读者可自行完成(答案为k=5)。,(问题2) n对夫妻要过河，船每次可载n-1人，应如何过河，最少要摆几次渡？（n=m-1，求k=?）。,答案如下：(1)n=3，m=2，k=11; (2) n=4，m=3，k=9 (3)n5，m=n-1，k=7,(问题3) 1883年，吕卡斯(Rcrations)提出以下问题：n对夫妻要过河，船至少应可载几人(m?)他们才可能过河，最少摆渡次数为多少？,09:22:48,MCM
10、,14,德兰努瓦(M. Delannoy)证明：,(问题4) 德丰特内(M. De Fonteney)指出，如果河中有一个岛，那么，不管有多少对夫妻，只要有一只可载2人的船，他们均能过河(2对、3对时不需要岛），最少摆渡次数为。,(1)n=2，m=2，k=5； (2)n=3，m=3，k=11(3)n=4，m=3，k=9； (4)n=5，m=3，k=11(5)n6，m=4，k=2n-3,更难的还可以考虑如下一类问题：(1)阿拉伯妇女生活于闺阁之中，她们应不会划船，此时问题又会怎样？(2)阿拉伯男子可以娶妾，假如有n位男人带着他们各自的妻妾过河，问题的结果又会变成怎样？这些问题因过于复杂，我们就此
11、搁笔，不再继续讨论下去了。,09:22:48,MCM,15,有些较为复杂的问题，开始时常常给人以一种变幻莫测的感觉。但经过细微的分析研究，可以发现其中存在着某些内在的关系。在使用适当的数学工具后，这些内在关系就被一一揭露出来了。,德国著名的艺术家Albrecht Drer(1471-1521)于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题。, 4.2 Drer魔方(或幻方)问题,09:22:48,MCM,16,1、Drer魔方,这是一个由自然数组成的方块，称之为Drer魔方，其数
12、字排列如下：,什么是魔方？我们来下一个定义。我们所谓的魔方是指由1n2这n2个正整数按一定规则排列成的一个n行n列的正方形。,09:22:48,MCM,17,按不同的要求，它可以具有某些特定的性质，n称为此魔方的阶。例如，上面给出的Drer魔方是4阶的，它的每一行数字之和为34，每一列数字之和为34，把对角线(或反对角线)上的数字加起来是34，每个小方块中的数字之和也是34，若把四个角上的数字加起来还是34，多么奇妙！最后一行中间两个数字恰好是铜币的铸造时间1514年。,构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前(公元前2200年)，因治水出
13、名的皇帝大禹就构造了三阶魔方(被人们称“洛书”)，至今还有人把它当作符咒用于某些迷信活动，,09:22:48,MCM,18,(被人称为洛书的3阶魔方),大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯阿格里帕(1486-1535)先后构造出了39阶的魔方。,如何构造出各种阶数的魔方呢？假如你知道方法，构造它其实并不困难。,在构造n阶魔方时，首先要看清n是奇数还是偶数，在构造时要巧妙地利用某种形式的对称性。,09:22:48,MCM,19,我们先来看n是奇数的情况，奇数阶魔方的构造方法如下：,首先，在第一行中间写1；然后每次向右上方移一格，依次填由小到大排列的下一个数，(注：向上移出界时填下一
14、列最后一行的小方格；向右移出界时填第一列上一行的小方格，就好像上下边是相连的、左右边也是相连的一样)。此外，当下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，此后继续按原方法填，直至完全填完所有小方格。例如，按上述方法可构造出下面的5阶魔方：,09:22:48,MCM,20,作为练习，请你给出一个7阶的魔方(见习题)。,偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫斯特雷奇给出了一种拼接的方法。限于篇幅的限止，我们不在此详细介绍了，作为一个例子，我们采用他的方法构造一个6阶的魔方。,第一步 利用1-9，10-18，19-27及28-36构造出4个3阶的魔方，它们分别
15、是：,09:22:48,MCM,21,第二步 利用图11-9中的A、B、C、D容易拼出一个6阶的魔方。为了保证性质的成立，还需要作一些调整，如果你有兴趣，不妨可以找一下调整的方法，(调整后得到的6阶魔方见图4-2所示),09:22:48,MCM,22,(图4-2 ),09:22:48,MCM,23,上述方法并非构造魔方的唯一方法，但不论采用什么方法来构造魔方，都应当尽可能利用某种形式的对称性。在魔方的构造中包含了许多有趣的数学问题，但由于很多人研究过这些问题，我们一般只能把它们当成一些练习题。,互不相同的同阶魔方究竟有多少个？人们知道，三阶魔方只有一个，当然，通过镜面反射和绕中心旋转可以产生8
16、种不同的表现形式。四阶魔方共有880个，而通过反射与旋转可有7040种不同的形式。没有人知道五阶或更高阶魔方的数量。例如，对五阶魔方，人们可用某种办法作出实质上不同的57600个(不含反射与旋转而得出的)，如加上用其他方法构造的，已知的五阶魔方总数远远超过了一千三百万个，魔方数量随阶数n增长已达到了惊人的速度，令人目瞪口呆。,09:22:48,MCM,24,2、松驰问题的讨论,假如我们放松对构造魔方的数必须是1-n2的要求而允许它们取任意实数，(就像将整数规划或0-1规划松驰成相应的线性规划那样)，问题也许会简单得多。我们仍要求它们具有某些特定的性质，并不妨仍把它们称为魔方，当然，此时问题已发
17、生了实质性的变化，不再是原先讨论的问题了。,为简单起见，我们用n阶方阵来记这样的魔方。易见，若A与B均为具有指定性质的魔方，则对任意的实数和，A+B也是。这一性质表明，具有指定性质的魔方全体构成一个线性空间。根据线性代数知识，要刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底即可。,09:22:48,MCM,25,不妨仍以4阶方阵为例。首先，定义0-方与1-方如下：,其中R为行和，C为列和，D为对角线和，S为小方块和。,现在，我们来研究具有性质R=C=D=S的方阵构成的线性空间 ，类似于构造n维欧氏空间的标准基，我们利用0和1来构造一些R=C=D=S=1的最简单的方阵，不难看出，1在
18、第一行中共有4种排法，为保持上述性质的成立，在第一行的1取定后，第二行中的1尚有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，Q8。,09:22:48,MCM,26,09:22:48,MCM,27,显然，D中任何一个元素都可以用Q1，Q2，Q8来线性表示，它们能否构成D的一组基，关键在于它们是否线性无关。,容易看出,所以Q1，Q2，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到，这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，Q7是否线性相关。,令， 即,09
19、:22:48,MCM,28,等号两边对应元素相比较，得r1=r2=r7=0，所以Q1，Q2，Q7是线性无关的。Q1，Q2，Q7是D空间的一组基，D中任何元素都可以由Q1，Q2，Q7的线性组合生成。可以这样认为： Q1，Q2，Q8是D的生成集，但不是最小生成集，而 Q1，Q2，Q7是D的最小生成集。,09:22:48,MCM,29,现在，我们回到Albrecht Drer铸造的铜币，以Q1，Q2，Q7的线性组合表示铜币上的魔方，D= d1Q1+d2Q2+d7Q7，即解方程组,解得,09:22:48,MCM,30,3、D空间的子空间和D空间的扩展,改变对Drer魔方数字和的要求，我们可以利用线性子
20、空间的定义，构造D的子空间或者构造新的空间包含D空间。这里，我们规定仅包含0方的向量空间维数为零。,(1) 要求数字方的所有数都相等。这是集合G=rE,rR，G是以G=E为基的一维向量空间，是D的一维子空间。,(2) 要求列和，行和及每条主、付对角线上数字和都相等，得到5维泛对角方的向量空间B。例如：,09:22:48,MCM,31,H=N=R=C=S=46,其中H为主对角线和，N为付对角线和。,它的基BB为,09:22:48,MCM,32,(3) 要求行和，列和及两条对角线上的元素和相等，得到8维向量空间Q，基向量QB= Q1，Q2，Q7，N0，其中Q1，Q2，Q7是D的基，,例如：,R=C
21、=D=30,09:22:48,MCM,33,(4) 仅要求行和与列和相等，可以得到10维向量空间，它的基B= Q1，Q2，Q7，N1，N2，N3，其中Q1，Q2，Q7是D的基，而,09:22:48,MCM,34,(5) 如果我们对数字没任何要求，那么所有的44数字方组成的向量空间M，它的维数是16，基向量MB中的元素应是标准基，(即仅有一个元素为1，其余元素均为0的方阵)。,Botsch(1976年)证明了可以构造大量的D的子空间或D的扩张空间。对于1与16之间的每一个数K，都存在K维的44方的向量空间，其中的每一方阵都具有某些特定的性质。,由上可知，有下式成立,(向量空间),0 1 5 7
22、8 10 16,(维数),09:22:48,MCM,35, 4.3 密码的设计、解码与破译,密码的设计和使用至少可以追溯到四千多年前的埃及 、巴比伦、罗马和希腊，历史极为久远。古代隐藏信息的方法主要有两大类：其一为隐藏信息载体，采用隐写术等；其二为变换信息载体，使之无法为一般人所理解。本节只涉及后者，介绍一些采用数学工具对信息加密、解密的方法。,在密码学中，信息代码被称为密码，加密前的信息被称为明文，经加密后不为常人所理解的用密码表示的信息被称为密文(ciphertext)，将明文转变成密文的过程被称为加密(enciphering)，其逆过程则被称为解密(deciphering)，而用以加密、
23、解密的方法或算法则被称为密码体制(crytosystem)。,09:22:48,MCM,36,记全体明文组成的集合为U，全体密文组成的集合为V，称U为明文空间，V为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合K。按数学的观点来看，加密与解密均可被看成是一种变换(或称映射)：取一kK， uU，令 ，v为明文u在密钥K下的密文，而解码则要用到K的逆变换K-1， 。由此可见，密码体系虽然可以千姿百态，但其关键还在于密钥的选取。,随着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、，许多相当高深的数学知
24、识都被用上，逐步形成了(并仍在迅速发展的)具有广泛应用面的现代密码学。,09:22:48,MCM,37,早期密码大体可分三类：代替法密码、移位密码和代数密码。,代替法密码,代替法密码采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即把明文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回,解密过程是加密过程的逆过程。在代替法加密过程中，明文字母表、密文字母表及两者间的对应关系即为代替法密钥，密钥既可以采用标准字母表，也可以任意建立。例如，我们可采用以
25、下的明文字母表和密文字母表：,09:22:48,MCM,38,明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJ,密钥还经常用一密钥字或密钥短语生成混淆字母表。密钥字或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。混合一个字母表，常见的有两种方法，这两种方法都采用了一个密钥字或一个密钥短语。,方法一： a)选择一个密钥字或密钥短语，例如：constructb)去掉其中重复的字母，得：construc)在修改后的密钥字后面接上从标准字母表中去掉密钥中的已有字母后剩下的字母，得：,明文字母表 ABCDEFGHIJK
26、LMNOPQRSTUVWXYZ密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZ,09:22:48,MCM,39,在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥字并将密钥字隐藏于其中。例如，对于上例，选取特定字母k，则可得：,明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ,方法二： a)选择一个密钥字或密钥短语，例如：construct b)去掉其中重复的字母，得：constru c)这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥字的字母后剩下的字母构成
27、,09:22:48,MCM,40,d)把所得矩阵中的字母按列的顺序选出，得：,caivobjwndkxselytfmzrgpuhq,按照此方法产生的字母表称为混淆字母表。,09:22:48,MCM,41,在代替法加密中，除了使用混淆字母表外，还可以使用混淆数。混淆数由以下方法产生：,a)选一密钥字或密钥短语，例如：constructb)按照这些字母在标准字母表中出现的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得：,construct 143675928,c)自左向右选出这些数字，得到一混淆数字组：143675928，混淆字母表由从小到大的顺序取矩阵中相应列得出,先取第一列、再取第8
28、列、，依次得出秘文字母表。 为增加保密性，在使用代替法时还可利用一些其他技巧，如单字母表对多字母表、单字母对多字母、多重代替等，这里就不再一一细说了。,09:22:48,MCM,42,移位密码体制,移位密码采用移位法进行加密，明文中的字母重新排列，本身不变，只是位置改变了。,现在所知的最为古老的加密方法天书就是移位法的一种。早在4000多年前，古希腊人就用一种名叫“天书”的器械来加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同的圆筒上，才能看到正确的消息，在这
29、里圆筒的直径起到了密钥的作用。,09:22:48,MCM,43,另一种移位法采用将字母表中的字母平移若干位的方法来构造密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的，故这种密文字母表被称为凯撒字母表。例如，如用将字母表向右平移3位的方法来构造密文字母表，可得：,明文字母表： ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表： DEFGHIJKLMNOPQRTSUVWXYZABC,使用这一密文字母表加密，THANK YOU 被加密成 WKDQN BRX，起到了一定的保密作用。,以上两种移位极易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定
30、的顺序安排在一矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。,09:22:48,MCM,44,例如，对明文：THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.以7列矩阵表示如下：,THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS,再按事先约定的方式选出密文。例如，如按列选出，得到密文：,touthyhrihueeysanahomndrifoorsszrnetjeed,09:22:48,MCM,45,使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写，得到的密
31、文也是不同的。如果对上例明文消息矩阵从左上角开始沿对角线抄写，得到的密文是： tohuretiyhhhsoiyuamfsennoztadorjrrneseed,在使用上述方法时矩阵的规模必须事先约定，它增加了对明文的保护程度。当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。,移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就是钥控列序加密法。,09:22:48,MCM,46,例如，用密钥字 construct对明文MATHEMATICAL MODELING IS USEFUL加密：,1 4
32、 36 75 9 2 8CONSTRUCTMATHEMATICALMODELINGISUSEFUL,按混淆数的顺序选出各列，得到密文：,MCNLTLFTLIAAGMDSHMSEOSIIUAEE,矩阵的最后一行可以用无用的字母填满，但若不加字母，则保密程度可以有所提高。移位法的使用可重复多次，只进行一次移位加密的称为一次移位法，经多次移位的则称为多次移位法。,09:22:48,MCM,47,代替法与移位法密码的破译,对窃听到的密文进行分析时，穷举法和统计法是最基本的破译方法，其他特殊的方法大多是这两种方法的综合和改进。,穷举分析法就是对所有可能的密钥或明文进行逐一试探，直至试探到“正确”的为止。
33、此方法需要事先知道密码体制或加密算法（但不知道密钥或加密的具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。,09:22:48,MCM,48,以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表单字母单元代替法加密的密码，字母表的可能情况有26！种，可见，单纯地使用穷举法，在实际应用中几乎是行不通的，只能与其它方法结合使用。,统计法是根据统计资料进行猜测的。在一段足够长且非特别专门化的文章中，字母的使用频率是比较稳定的。在某些技术性或专
34、门化文章中的字母使用频率可能有微小变化。,在上述两种加密方法中字母表中的字母是一一对应的，因此，在截获的密文中各字母出现的概率提供了重要的密钥信息。,09:22:48,MCM,49,根据权威资料报道，可以将26个英文字母按其出现的频率大小较合理地分为五组：,() t,a,o,i,n,s,h,r; () e; () d,l; () c,u,m,w,f,g,y,p,b; () v,k,j,x,q,z;,不仅单个字母以相当稳定的频率出现，相邻字母对和三字母对同样如此。按频率大小将双字母排列如下：,th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,e
35、a,ng,as,or,ti,is,er,it,ar,te,se,hi,of,09:22:48,MCM,50,使用最多的三字母按频率大小排列如下：,The,ing,and,her,ere,ent,tha,nth,was,eth,for,dth,下面介绍一下统计观察的三个结果：a) 单词the在这些统计中有重要的作用；b) 以e，s，d，t为结尾的英语单词超过了一半；c) 以t，a，s，w为起始字母的英语单词约为一半。 对于a），如果将the从明文中删除，那么t的频率将要降到第二组中其他字母之后，而h将降到第三组中，并且th和he就不再是最众多的字母了。,以上对英语统计的讨论是在仅涉及26个字母的
36、假设条件下进行的。实际上消息的构成还包括间隔、标点、数字等字符。总之，破译密码并不是件很容易的事。,09:22:48,MCM,51,希尔密码,代替密码与移位密码的一个致命弱点是明文字符和密文字符有相同的使用频率,破译者可根据统计出来的字符频率中找到规律，进而找出破译的突破口。要克服这一缺陷，提高保密程度就必须改变字符间的一一对应。1929年，希尔利用线性代数中的矩阵乘积运算，打破了字符间的对应关系，设计了一种被称为希尔密码的代数密码。为了便于计算，希尔首先将字符变换成数，例如，对英文字母，我们可以作如下变换：,A B C D E F G H I J K L M N O P Q R S T U
37、V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0,09:22:48,MCM,52,希尔密码的基本思想很简单，将密文分成n个一组，用对应的数字代替，就变成了一个个n维向量。如果取定一个n阶的非奇异矩阵A(此矩阵为主要密钥)，用A去乘每一向量，即可起到加密的效果，解密也不麻烦，将密文也分成n个一组，同样变换成n维向量，只需用A-1去乘这些向量，即可将他们变回原先的明文，(因为 )。,在具体实施时，读者很快会发现一些困难：(1)为了使数字与字符间可以互换，必须使用取自025之间的整数(2)由线性
38、代数知识， ，其中A*为A的伴随矩阵，这说明在求A的逆矩阵时可能会出现分数。不解决这些困难，上述想法仍然无法实现。解决的办法是引进同余运算，并用乘法来代替除法，(如同线性代数中用逆矩阵代替矩阵除法一样)。,09:22:48,MCM,53,让我们从最简单的情况做起，令n=1，用数 去乘025中的数，以26为模取同余，并要求存在 0，.，25，使得 ，有 (mod26)，或要求存在 ，使得 (mod26)。经简单的分析即可发现，并非所有025中的数都可用作这里的 ，事实上我们可证明下面的定理：,定理4.1 ，若 使得 (mod26)，则必有 ，其中 为 与26的最大公因子。,09:22:48,MC
39、M,54,证 任取 ，令 ，于是 (mod26)又故 ，由 的任意性可知必有 (mod26)，即上式又说明必有 ，不然它将整除1，而这是不可能的。,此外，我们还不难证明这样的还是由唯一确定的。事实上设有,和,则 故必有 ，也因为即,09:22:48,MCM,55,由定理，026中除13以外的奇数均可取作这里的 ，下表为经计算求得的逆元素,1 3 5 7 9 11 15 17 19 21 23 25 1 9 21 15 3 19 7 23 11 5 17 25,例4.3 取a = 3用希尔密码体系加密语句THANK YOU,步1 将THANK YOU转换成(20,8,1,14,11,25,15,
40、21)步2 每一分量乘以3并关于26取余的(8,24,3,16,7,23,19,11) 密文为HXCPG WSK 现在，我们已不难将方法推广到n为一般整数的情况了，只需在乘法运算中结合应用取余，求逆矩阵时用逆元素乘来代替除法即可。,09:22:48,MCM,56,例4.4 取 则 ，用A加密THANK YOU，再用A-1对密文解密,解： (希尔密码加密)用相应数字代替字幕，划分为两个一组并表示为向量：,用矩阵A左乘各向量加密（关于26取余）得,得到密文 JXCPI WEK,09:22:48,MCM,57,(希尔密码解密)用A-1左乘得到的向量，即可还原为原来的向量，读者可自行检验之。 希尔密码
41、是以矩阵法为基础的，明文与密文的对应由n阶矩阵A确定。矩阵A的阶数是事先约定的，与明文分组时每组字母的字母数量n相同，如果明文所含字数与n不匹配，则最后几个分量可任意补足。,A-1的求法,方法1 利用公式 ，例如，若取 ，则 ， (mod26) ，即,09:22:48,MCM,58,方法2 利用行初等变换的高斯消去法。将矩阵(A, E)中的矩阵A消为E，则原先的E即被消成了，如 的逆矩阵可如下求：,写出 ， ，用9乘第二行化第二行的3为1：,在从第一行减去第二行的2倍，并取同余得,此时，括号内左边的矩阵为单位阵，而右边的矩阵即为要求的,09:22:48,MCM,59,希尔密码系统的解密必须知道
42、该体系是用矩阵加密的并依赖于以下几把钥匙(key)：,Key1 矩阵A的阶数n，即明文是按几个字母划分的。,Key2 变换矩阵A，只有知道了A才可能推算出,Key3 明文和密文由字母表转换成n维向量所对应的非负整数表(上面为方便起见，我们采用了字母的自然顺序，事实上，在采用希尔密码时，我们仍可兼用代替法，以便增加破译的难度)。,09:22:48,MCM,60,希尔密码的破译,希尔密码体系为破译者设置了多道关口，加大了破译难度。 破译和解密是两个不同的概念，虽然两者同样是希望对密文加以处理得到明文的内容，但是他们有一个最大的不同破译密码时，解密必需用到的钥匙未能取得，破译密码的一方需要依据密文的
43、长度，文字的本身特征，以及行文习惯等等各方面的信息进行破译。破译密码虽然需要技术，但更加重要的是“猜测”的艺术。“猜测”的成功与否直接决定着破译的结果。,破译希尔密码的关键是猜测文字转换成n维向量所对应的字母表，最重要的是获得加密矩阵A。,09:22:48,MCM,61,由线性代数的知识可以知道，矩阵完全由一组基的变换决定，对于n*n矩阵A，只要猜出密文中n个线性无关的向量 (i=1, 2, , n)对应的明文 (i=1, 2, , n)，即可确定A，将密码破译。,在实际计算中，可以利用以下方法：,令,取矩阵Q|P,经过一系列初等行变换，将由密文决定的n维矩阵Q化为单位阵I(n*n)的时候，由
44、明文决定的矩阵P自动化为 ：,则,，初等行变换,09:22:48,MCM,62,例如有密文：goqbxcbuglosnfal,根据英文的行文习惯以及获取密码的途径和背景，猜测是两个字母为一组的希尔密码，前四个明文字母是dear；则前两组明文字母de和ar 对应的二维向量是：,按同一对应整数表，密文中对应这两组的二维向量是：,利用这一逆矩阵，可对截获密文进行解密，破译出的电文是Dear Mac God forbid。,这只是对最简单的情况进行的举例，如果加密矩阵的阶数大于2，需要的密文应该有较长长度，所需进行的计算量也是很大的，但在猜测到P1,P后求解加密矩阵的计算量却并不算大，是与n2同阶的。
45、,09:22:48,MCM,63,本节中介绍的希尔密码体制是以矩阵法为基础的，实际上，希尔首先提出的是联立方程法，而后经简化提出了利用矩阵进行运算的希尔密码，由线性代数知识，这一点不难理解。 希尔密码加密、解密、破译的过程中有两个要素非常重要：第一是字母与n维向量进行转换所依据的非负整数表，本节中所举的是最自然的情况；当然如果依据其它的整数表也是完全可以进行的，其情况将会更复杂一些，破译的难度就会增大。 第二个要素是加密矩阵，如何定义、求解这个矩阵对于密码的加密和破译更加关键。如前所述，加密时应选择对应行列式的值与26没有公因子的矩阵，使用时可以任意选择。,09:22:48,MCM,64, 4
46、.4考虑年龄结构的人口模型(Leslie模型),对Logistic模型的批评意见除了实际统计时常采用离散变化的时间变量外，另一种看法是种群增长不应当只和种群总量有关，也应当和种群的年龄结构有关。不同年龄的个体具有不同的生育能力和死亡率，这一重要特征没有在Logistic模型中反映出来。基于这一事实，Leslie在20世纪40年代建立了一个考虑种群年龄结构的离散模型。,由于男、女性人口(或雌、雄性个体)通常有一定的比例，为了简便起见，建模时可以只考虑女性人数，人口总量可以按比例折算出来。将女性按年龄划分成m+1个组，即0,1,m组，例如，可5岁(或10岁)一组划分。将时间也离散成间隔相同的一个个
47、时段，即5年(或10年)为一个时段。,09:22:48,MCM,65,记j时段年龄在i组中的女性人数为N(i,j)，bi为i组每一妇女在一个时段中生育女孩的平均数，pi为i组女性存活一时段到下一时段升入i+1组的人数所占的比例(即死亡率di=1-pi)同时假设没有人能活到超过m组的年龄。实际上可以这样来理解这一假设，少量活到超过m组的妇女(老寿星)人数可以忽略不计，她们早已超过了生育期，对人口总量的影响是微小的而且是暂时性的，对今后人口的增长和人口的年龄结构不产生任何影响，假设bi、pi不随时段的变迁而改变，这一假设在稳定状况下是合理的。如果研究的时间跨度不过于大，人们的生活水平、整个社会的医
48、疗条件及周围的生活环境没有过于巨大的变化，bi、pi事实上差不多是不变的，其值可通过统计资料估算出来。,09:22:48,MCM,66,根据以上假设可以得出以下j+1时段各组人数与j时段各组人数之间的转换关系：,显然，,简记,09:22:48,MCM,67,并引入矩阵,则方程组(4.28)可简写成,矩阵A被称为Leslie矩阵(或射影矩阵)，当矩阵A与按年龄组分布的初始种群向量N0=(N(0,0)， N(1,0)， ，N(m,0)T一经给定时，其后任一时段种群按年龄分布的向量即可用(4.29)式迭代求得,09:22:48,MCM,68,人口(或种群)的增长是否合理不仅仅取决于人口的总量是否过多
49、或过少，还取决于整个的年龄结构是否合理即各年龄段人口数的比例是否恰当。通过对Leslie矩阵A的研究，可以得到许多十分有用的信息。,女性有一定的生育期，例如k组以后的女性不再生育，则有bk0，bk+1，bm均为零(初始若干个bi也可能为零)，此时A可简记为,其中A1和A2分别为k+1阶和m-k阶方阵，于是,09:22:48,MCM,69,因为A3是一个下三角阵且对角元素全为零，由高等代数中的哈密顿一凯莱定理，当jm-k时必有 ，此时Aj的最后m-k列均为零向量。其实际意义为t=0时已超过育龄的女性，其目前的存在对若干年后的人口分布已毫无影响，她对人口发展的贡献将由她在此前所生育的女孩来完成，这
50、一点当然是十分显然的。f(A1,A2,A3)为某一用A1、A2、A3表达的表示式，Aj的这一子块较为复杂，并直接反映出k+1组以后各组的年龄结构，对它的讨论可以导出避免社会老龄化的条件。,现在，我们来研究一下Leslie矩阵，并进而研究时间充分长后种群的年龄结构及数量上的趋势。,09:22:48,MCM,70,容易看出A1是非奇异的，因为,事实上，不难直接验证：,09:22:48,MCM,71,由Aj的分块结构可知，对A1及Nj+1的前k+1个分量 也成立。为叙述方便，不妨仍记 为Nj，并记A1为A，简略讨论一下前k+1组人口数量的变化情况。,由于人口生育率和死亡率与年龄之间存在着固定的关系，
