浙大城院数学建模4课件

第四章、线性代数模型第四章、线性代数模型 4.1 4.1 几个数学游戏几个数学游戏 4.2 Drer 4.2 Drer魔方魔方(或幻方或幻方)问题问题 4.3 4.3 密码的设计、解码与破译密码的设计、解码与破译 4.4 4.4考虑年龄结构的人口模型考虑年龄结构的人口模型(Leslie(Leslie模模型型)7/4/20241MCM 4.1 4.1 几个数学游戏几个数学游戏 向向量量、向向量量空空间间、矩矩阵阵等等都都是是线线性性代代数数中中的的重重要要概概念念，本本节节将将通通过过一一些些简简单单的的实实例例来来说说明明它它们们在在实实际际中中的的应用。应用。例例4.14.1 人、狗、鸡、米过河问题人、狗、鸡、米过河问题 这是一个人所共知而又十分简单的智力游戏。某人这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除了需要有人去划以外，要带狗、鸡、米过河，但小船除了需要有人去划以外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。要吃米，问此人应如何过河。要知道例要知道例4.14.1的答案并不困难。第一次，人只能带的答案并不困难。第一次，人只能带鸡过河。到了对岸，人只有自己回来，将鸡留在对岸，鸡过河。到了对岸，人只有自己回来，将鸡留在对岸，否则，又返回了初始状态。否则，又返回了初始状态。7/4/20242MCM 接接下下来来，人人可可以以带带狗狗过过河河，也也可可以以带带米米过过河河，但但回回来来时时有有一一定定要要将将鸡鸡带带回回，按按此此推推导导下下去去，读读者者不不难难找找到到过过河河方方法法。我我们们研研究究本本例例的的目目的的不不在在于于找找出出答答案案，而而是是想想设设计计出出一一种种让让计计算算机机自自行行搜搜索索寻寻找找答答案案的的方方法法。为为此此目目的的，我我们们先先把把例例1 1转转化化为为状状态态转转移移问问题题。首首先先，应应当当如如何何表表达达状状态态呢呢？不不同同的的情情况况应应采采取取不不同同的的方方法法，在在本本例例中中，人人鸡鸡狗狗米米都都只只有有两两种种可可能能状状态态，即即在在此此岸岸或或在在彼彼岸岸（不不在在此此岸岸）。我我们们将将用用向向量量来来表表示示状状态态，可可采采取取如如下下方方法法：一一物物在在此此岸岸时时相相应应分分量量取取1 1，而而在在彼彼岸岸时时则则相相应应分分量量取取为为0 0，例例如如（1,0,1,01,0,1,0）表表示示人人和和鸡鸡在在此此岸岸，而而狗和米则在彼岸。狗和米则在彼岸。7/4/20243MCM(i)(i)可可取取状状态态：根根据据题题意意，并并非非所所有有状状态态都都是是允允许许的的，例例如如（0,1,1,00,1,1,0）就就是是一一个个不不可可取取的的状状态态，因因为为狗狗会会咬咬鸡鸡。本本题题中中可可取取状状态态（即即系系统统允允许许的的状状态态）可可以以用用穷穷举举法法列列出来，它们是：出来，它们是：总总共共有有十十个个可可取取状状态态。对对一一般般情情况况，也也可可找找出出状状态态为为可可取取的的充充要要条条件件，让让计计算算机机根根据据充充要要条条件件来来检检查查得得到到的状态是否为可取状态。的状态是否为可取状态。7/4/20244MCM(ii)(ii)可可取取运运算算：状状态态转转移移需需要要经经过过状状态态运运算算来来实实现现。在在实实际际问问题题中中，摆摆一一次次渡渡即即可可改改变变现现有有状状态态。为为此此再再引引入入一一个个四四维维向向量量(转转移移向向量量)，用用它它来来反反映映摆摆渡渡情情况况。例例如如(1(1，1 1，0 0，0)0)表表示示人人带带狗狗摆摆渡渡过过河河。根根据据题题意意，允允许许使使用用的的转转移移向向量量只只能能有有(1(1，0 0，0 0，0)0)、(1(1，1 1，0 0，0)0)、(1(1，0 0，1 1，0)0)、（、（1 1，0 0，0 0，1)1)四个。四个。为为实实现现本本题题中中的的状状态态转转移移，规规定定一一个个状状态态向向量量与与转转移移向向量量之之间间的的运运算算。规规定定状状态态向向量量与与转转移移向向量量之之和和为为一一新新的的状状态态向向量量，其其运运算算为为对对应应分分量量相相加加，且且规规定定0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=01+1=0。例例如如(1(1，1 1，1 1，1)+(11)+(1，0 0，1 1，0)=0)=(0(0，1 1，0 0，1)1)，其其实实际际意意义义为为人人狗狗鸡鸡米米原原来来均均在在此此岸岸，人人带带鸡鸡过过河河，转转变变为为新新的的状状态态此此岸岸仅仅剩剩狗狗和和米米，(注注：此此处作这样的运算规定完全是为了与实际情况相符处作这样的运算规定完全是为了与实际情况相符)。7/4/20245MCM 在在具具体体转转移移时时，只只考考虑虑由由可可取取状状态态到到可可取取状状态态的的转转移移。问问题题化化为为：由由初初始始状状态态(1(1，1 1，1 1，1)1)出出发发，经经过过奇奇数数次次的的上上述述运运算算能能否否转转化化为为(0(0，0 0，0 0，0)0)的的转转化化问问题题，进而，如果能，我们还想知道具体应当如何转化进而，如果能，我们还想知道具体应当如何转化 。由由于于规规定定的的运运算算十十分分容容易易在在计计算算机机上上实实现现，这这样样一一来来就就把把一一个个数数学学游游戏戏转转化化为为了了一一个个可可以以在在计计算算机机上上计计算算的的数数学学问问题题(即即建建模模)。当当然然，像像本本题题这这样样简简单单的的问问题题，也可通过笔算方法求解，具体可如下进行分析也可通过笔算方法求解，具体可如下进行分析(第一次渡河第一次渡河)7/4/20246MCM(第二次渡河第二次渡河)以以下下可可继继续续进进行行下下去去，直直至至转转移移目目的的实实现现。上上述述分分析析实实际际上上采采用用的的是是穷穷举举法法，对对于于规规模模较较大大的问题是不宜采用的。的问题是不宜采用的。7/4/20247MCM例例4.2 4.2 夫妻过河问题夫妻过河问题 这这是是一一个个古古老老的的阿阿拉拉伯伯数数学学问问题题。有有三三对对夫夫妻妻要要过过河河，船船最最多多可可载载两两人人，约约束束条条件件是是根根据据阿阿拉拉伯伯法法律律，任任一一女女子子不不得得在在其其丈丈夫夫不不在在场场的的情情况况下下与与其其他他男男子子在在一起，问此时这三对夫妻能否过河？一起，问此时这三对夫妻能否过河？这一问题的状态和运算与前一问题有所不同，根这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同据题意，状态应能反映出两岸的男女人数，过河也同样要反映出性别，故可如下定义：样要反映出性别，故可如下定义：(i)(i)可可取取状状态态：用用H H和和W W分分别别表表示示此此岸岸的的男男子子和和女女子子数数，状状态态可可用用矢矢量量(H H，W W)表表示示，其其中中00H H、W W33。可可取取状状态态为为(0,(0,i i)，(i i,i i)，(3,(3,i i)，00i i33。(i i,i i)为为可可取取状状态，这是因为总可以适当安排而使他们是态，这是因为总可以适当安排而使他们是i i对夫妻。对夫妻。7/4/20248MCM(ii)(ii)可可取取运运算算：过过河河方方式式可可以以是是一一对对夫夫妻妻、两两个个男男人人或或两两个个女女人人，当当然然也也可可以以是是一一人人过过河河。转转移移向向量量可可取取成成(1 1）i im m,(1)1)i in n），其其中中m m、n n可可取取0 0、1 1、2 2，但但必必须须满满足足11m m+n n22。当当j j为为奇奇数数时时表表示示过过河河。当当j j为为偶偶数数时时表表示示由由对对岸岸回回来来，运运算算规规则则同同普普通通向向量量的的加加法法。问问题题归归结结为为由由状状态态(3,3)(3,3)经经奇奇数数次次可可取取运运算算，即即由由可可取取状状态态到到可可取取状状态态的的转转移移，转转化化为为(0,0)(0,0)的的转转移移问问题题。和和上上题题一一样样，我我们们既既可可以以用用计计算算机机求求解解，也也可可以以分分析析求求解，此外，本题还可用作图方法来求解。解，此外，本题还可用作图方法来求解。7/4/20249MCM在在在在H H H HW W W W平平平平面面面面坐坐坐坐标标标标中中中中，以以以以“”表表表表示示示示可可可可取取取取状状状状态态态态，从从从从A(3,3)A(3,3)A(3,3)A(3,3)经经经经奇奇奇奇数数数数次次次次转转转转移移移移到到到到达达达达OO(0(0(0(0，0)0)0)0)。奇奇奇奇数数数数次次次次转转转转移移移移时时时时向向向向左左左左或或或或下下下下移移移移动动动动1-21-21-21-2格格格格而而而而落落落落在在在在一一一一个个个个可可可可取取取取状状状状态态态态上上上上，偶偶偶偶数数数数次次次次转转转转移移移移时时时时向向向向右右右右或或或或上上上上移移移移动动动动1-21-21-21-2格格格格而而而而落落落落在在在在一一一一个个个个可可可可取取取取状状状状态态态态上上上上。另另另另外外外外，由由由由于于于于奇奇奇奇数数数数次次次次与与与与偶偶偶偶数数数数次次次次过过过过河河河河产产产产生生生生的的的的效效效效果果果果是是是是不不不不同同同同的的的的，为为为为了了了了区区区区分分分分起起起起见见见见，用用用用实实实实箭箭箭箭线线线线表表表表示示示示奇奇奇奇数数数数次次次次转转转转移移移移，用用用用虚虚虚虚箭箭箭箭线线线线表表表表示示示示第第第第偶偶偶偶数数数数转转转转移移移移，图图图图4-14-14-14-1给出了一种可实现的方案，故给出了一种可实现的方案，故给出了一种可实现的方案，故给出了一种可实现的方案，故7/4/202410MCM（图（图（图（图4-14-14-14-1）7/4/202411MCM 关关于于夫夫妻妻过过河河还还可可以以编编出出许许多多其其他他形形式式的的问问题题，下下面面我我们们来来讨讨论论一一些些同同样样有有趣趣的的问问题题。为为了了叙叙述述简简便便，先先约约定定一一些些符符号号，这这些些符符号号将将被被应应用用于于以以下下的的各各个个问问题题之之中中。记记想想过过河河的的夫夫妻妻对对数数为为n n，船船可可载载的的人人数数为为m m，n n对对夫妻过河所需的最少摆渡次数为夫妻过河所需的最少摆渡次数为k k。这三对夫妻是可以过河的。假如按这样的方案过这三对夫妻是可以过河的。假如按这样的方案过河，共需经过十一次摆渡。河，共需经过十一次摆渡。不不难难看看出出，在在上上述述规规则则下下，4 4对对夫夫妻妻就就无无法法过过河河了了，读读者者可可以以自自行行证证明明之之。类类似似可可以以讨讨论论船船每每次次可可载载三三人人的的情情况况，其其结结果果是是5 5对对夫夫妻妻是是可可以以过过河河的的，而而六六对对以以上上时时就就无无法法过过河河了了。假假如如船船每每次次可可以以载载四四人人，则则任任意意多多对对夫夫妻妻均均可可过过河河，最最易易看看出出的的一一个个方方案案是是让让一一对对夫夫妻妻当当船船员员工即可。工即可。7/4/202412MCM(问题问题1)1)2 2对夫妻要过河，船每次只能渡对夫妻要过河，船每次只能渡2 2人，应如何人，应如何过河，最少摆渡几次？过河，最少摆渡几次？(即即n=2n=2，m=2m=2，求，求k=?)k=?)本问题很容易解答，读者可自行完成本问题很容易解答，读者可自行完成(答案为答案为k=5)k=5)。(问题问题2)2)n n对夫妻要过河，船每次可载对夫妻要过河，船每次可载n-1n-1人，应如何过人，应如何过河，最少要摆几次渡？（河，最少要摆几次渡？（n=m-1n=m-1，求，求k=?k=?）。）。答案如下：答案如下：(1)n=3(1)n=3，m=2m=2，k=11;(2)n=4k=11;(2)n=4，m=3m=3，k=9k=9 (3)n5 (3)n5，m=n-1m=n-1，k=7k=7(问问题题3)3)18831883年年，吕吕卡卡斯斯(RcrationsRcrations)提提出出以以下下问问题题：n n对对夫夫妻妻要要过过河河，船船至至少少应应可可载载几几人人(m?)(m?)他他们们才才可可能能过河，最少摆渡次数为多少？过河，最少摆渡次数为多少？7/4/202413MCM德兰努瓦德兰努瓦(M.(M.DelannoyDelannoy)证明：证明：(问问问问题题题题4)4)4)4)德德德德丰丰丰丰特特特特内内内内(M.(M.(M.(M.De De De De FonteneyFonteneyFonteneyFonteney)指指指指出出出出，如如如如果果果果河河河河中中中中有有有有一一一一个个个个岛岛岛岛，那那那那么么么么，不不不不管管管管有有有有多多多多少少少少对对对对夫夫夫夫妻妻妻妻，只只只只要要要要有有有有一一一一只只只只可可可可载载载载2 2 2 2人人人人的的的的船船船船，他他他他们们们们均均均均能能能能过过过过河河河河(2(2(2(2对对对对、3 3 3 3对对对对时时时时不不不不需需需需要要要要岛岛岛岛），最最最最少少少少摆摆摆摆渡渡渡渡次数为。次数为。次数为。次数为。(1)n=2(1)n=2，m=2m=2，k=5k=5；(2)n=3(2)n=3，m=3m=3，k=11k=11(3)n=4(3)n=4，m=3m=3，k=9k=9；(4)n=5(4)n=5，m=3m=3，k=11k=11(5)n6(5)n6，m=4m=4，k=2n-3k=2n-3 更更更更难难难难的的的的还还还还可可可可以以以以考考考考虑虑虑虑如如如如下下下下一一一一类类类类问问问问题题题题：(1)(1)(1)(1)阿阿阿阿拉拉拉拉伯伯伯伯妇妇妇妇女女女女生生生生活活活活于于于于闺闺闺闺阁阁阁阁之之之之中中中中，她她她她们们们们应应应应不不不不会会会会划划划划船船船船，此此此此时时时时问问问问题题题题又又又又会会会会怎怎怎怎样样样样？(2)(2)(2)(2)阿阿阿阿拉拉拉拉伯伯伯伯男男男男子子子子可可可可以以以以娶娶娶娶妾妾妾妾，假假假假如如如如有有有有n n n n位位位位男男男男人人人人带带带带着着着着他他他他们们们们各各各各自自自自的的的的妻妻妻妻妾妾妾妾过过过过河河河河，问问问问题题题题的的的的结结结结果果果果又又又又会会会会变变变变成成成成怎怎怎怎样样样样？这这这这些些些些问问问问题题题题因因因因过过过过于于于于复复复复杂，我们就此搁笔，不再继续讨论下去了。杂，我们就此搁笔，不再继续讨论下去了。杂，我们就此搁笔，不再继续讨论下去了。杂，我们就此搁笔，不再继续讨论下去了。7/4/202414MCM 有有些些较较为为复复杂杂的的问问题题，开开始始时时常常常常给给人人以以一一种种变变幻幻莫莫测测的的感感觉觉。但但经经过过细细微微的的分分析析研研究究，可可以以发发现现其其中中存存在在着着某某些些内内在在的的关关系系。在在使使用用适适当当的的数数学学工工具具后，这些内在关系就被一一揭露出来了。后，这些内在关系就被一一揭露出来了。德德国国著著名名的的艺艺术术家家Albrecht Albrecht Drer(1471-1521)Drer(1471-1521)于于15141514年年曾曾铸铸造造了了一一枚枚名名为为“MelencotiaMelencotia I”I”的的铜铜币币。令令人人奇奇怪怪的的是是在在这这枚枚铜铜币币的的画画面面上上充充满满了了数数学学符符号号、数数字字及及几几何何图图形形。这这里里，我我们们仅仅研研究究铜铜币币右右上上角角的的数数字问题。字问题。4.2 4.2 DrerDrer魔方魔方(或幻方或幻方)问题问题7/4/202415MCM1 1、DrerDrer魔方魔方 这这是是一一个个由由自自然然数数组组成成的的方方块块，称称之之为为DrerDrer魔魔方方，其数字排列如下：其数字排列如下：什什么么是是魔魔方方？我我们们来来下下一一个个定定义义。我我们们所所谓谓的的魔魔方方是是指指由由1 1n n2 2这这n n2 2个个正正整整数数按按一一定定规规则则排排列列成成的的一一个个n n行行n n列的正方形。列的正方形。7/4/202416MCM 按按不不同同的的要要求求，它它可可以以具具有有某某些些特特定定的的性性质质，n n称称为为此此魔魔方方的的阶阶。例例如如，上上面面给给出出的的DrerDrer魔魔方方是是4 4阶阶的的，它它的的每每一一行行数数字字之之和和为为3434，每每一一列列数数字字之之和和为为3434，把把对对角角线线(或或反反对对角角线线)上上的的数数字字加加起起来来是是3434，每每个个小小方方块块中中的的数数字字之之和和也也是是3434，若若把把四四个个角角上上的的数数字字加加起起来来还还是是3434，多多么么奇奇妙妙！最最后后一一行行中中间间两两个个数数字字恰恰好好是是铜铜币币的的铸铸造造时间时间15141514年。年。构构造造魔魔方方是是一一个个古古老老的的数数学学游游戏戏，起起初初它它还还和和神神灵灵联联系系在在一一起起，带带有有深深厚厚的的迷迷信信色色彩彩。传传说说三三千千二二百百多多年年前前(公公元元前前22002200年年)，因因治治水水出出名名的的皇皇帝帝大大禹禹就就构构造造了了三三阶阶魔魔方方(被被人人们们称称“洛洛书书”)，至至今今还还有有人人把把它它当当作作符符咒咒用于某些迷信活动，用于某些迷信活动，7/4/202417MCM(被人称为洛书的被人称为洛书的3 3阶魔方阶魔方)大大约约在在十十五五世世纪纪时时，魔魔方方传传到到了了西西方方，著著名名的的科科尼尼利利厄厄斯斯阿阿格格里里帕帕(1486-1535)(1486-1535)先先后后构构造造出出了了3 39 9阶阶的的魔魔方。方。如如何何构构造造出出各各种种阶阶数数的的魔魔方方呢呢？假假如如你你知知道道方方法法，构造它其实并不困难。构造它其实并不困难。在在构构造造n n阶阶魔魔方方时时，首首先先要要看看清清n n是是奇奇数数还还是是偶偶数数，在构造时要巧妙地利用某种形式的对称性。在构造时要巧妙地利用某种形式的对称性。7/4/202418MCM 我我们们先先来来看看n n是是奇奇数数的的情情况况，奇奇数数阶阶魔魔方方的的构构造造方方法法如下：如下：首首先先，在在第第一一行行中中间间写写1 1；然然后后每每次次向向右右上上方方移移一一格格，依依次次填填由由小小到到大大排排列列的的下下一一个个数数，(注注：向向上上移移出出界界时时填填下下一一列列最最后后一一行行的的小小方方格格；向向右右移移出出界界时时填填第第一一列列上上一一行行的的小小方方格格，就就好好像像上上下下边边是是相相连连的的、左左右右边边也也是是相相连连的的一一样样)。此此外外，当当下下面面想想填填的的格格已已填填过过数数或或已已达达到到魔魔方方的的右右上上角角时时，改改填填刚刚才才填填的的格格子子正正下下方方的的小小方方格格，此此后后继继续续按按原原方方法法填填，直直至至完完全全填填完完所所有有小小方方格格。例如，按上述方法可构造出下面的例如，按上述方法可构造出下面的5 5阶魔方：阶魔方：7/4/202419MCM作作为为练练习习，请请你你给给出出一一个个7 7阶阶的魔方的魔方(见习题见习题)。偶偶数数阶阶的的魔魔方方可可以以利利用用奇奇数数阶阶魔魔方方拼拼接接而而成成，拉拉尔尔夫夫斯斯特特雷雷奇奇给给出出了了一一种种拼拼接接的的方方法法。限限于于篇篇幅幅的的限限止止，我我们们不不在在此此详详细细介介绍绍了了，作作为为一一个个例例子子，我我们们采用他的方法构造一个采用他的方法构造一个6 6阶的魔方。阶的魔方。第第一一步步 利利用用1-91-9，10-1810-18，19-2719-27及及28-3628-36构构造造出出4 4个个3 3阶的魔方，它们分别是：阶的魔方，它们分别是：7/4/202420MCM第第二二步步 利利用用图图11-911-9中中的的A A、B B、C C、D D容容易易拼拼出出一一个个6 6阶阶的的魔魔方方。为为了了保保证证性性质质的的成成立立，还还需需要要作作一一些些调调整整，如如果果你你有有兴兴趣趣，不不妨妨可可以以找找一一下下调调整整的的方方法法，(调调整整后后得到的得到的6 6阶魔方见图阶魔方见图4-24-2所示所示)7/4/202421MCM(图图4-24-2)7/4/202422MCM 上上述述方方法法并并非非构构造造魔魔方方的的唯唯一一方方法法，但但不不论论采采用用什什么么方方法法来来构构造造魔魔方方，都都应应当当尽尽可可能能利利用用某某种种形形式式的的对对称称性性。在在魔魔方方的的构构造造中中包包含含了了许许多多有有趣趣的的数数学学问问题题，但但由由于于很很多多人人研研究究过过这这些些问问题题，我我们们一一般般只只能能把把它它们们当当成成一些练习题。一些练习题。互互不不相相同同的的同同阶阶魔魔方方究究竟竟有有多多少少个个？人人们们知知道道，三三阶阶魔魔方方只只有有一一个个，当当然然，通通过过镜镜面面反反射射和和绕绕中中心心旋旋转转可可以以产产生生8 8种种不不同同的的表表现现形形式式。四四阶阶魔魔方方共共有有880880个个，而而通通过过反反射射与与旋旋转转可可有有70407040种种不不同同的的形形式式。没没有有人人知知道道五五阶阶或或更更高高阶阶魔魔方方的的数数量量。例例如如，对对五五阶阶魔魔方方，人人们们可可用用某某种种办办法法作作出出实实质质上上不不同同的的5760057600个个(不不含含反反射射与与旋旋转转而而得得出出的的)，如如加加上上用用其其他他方方法法构构造造的的，已已知知的的五五阶阶魔魔方方总总数数远远远远超超过过了了一一千千三三百百万万个个，魔魔方方数数量量随随阶阶数数n n增增长长已已达到了惊人的速度，令人目瞪口呆。达到了惊人的速度，令人目瞪口呆。7/4/202423MCM2 2、松驰问题的讨论、松驰问题的讨论 假假如如我我们们放放松松对对构构造造魔魔方方的的数数必必须须是是1-n21-n2的的要要求求而而允允许许它它们们取取任任意意实实数数，(就就像像将将整整数数规规划划或或0-10-1规规划划松松驰驰成成相相应应的的线线性性规规划划那那样样)，问问题题也也许许会会简简单单得得多多。我我们们仍仍要要求求它它们们具具有有某某些些特特定定的的性性质质，并并不不妨妨仍仍把把它它们们称称为为魔魔方方，当当然然，此此时时问问题题已已发发生生了了实实质质性性的的变变化化，不不再再是是原先讨论的问题了。原先讨论的问题了。为为简简单单起起见见，我我们们用用n n阶阶方方阵阵来来记记这这样样的的魔魔方方。易易见见，若若A A与与B B均均为为具具有有指指定定性性质质的的魔魔方方，则则对对任任意意的的实实数数和和，A+BA+B也也是是。这这一一性性质质表表明明，具具有有指指定定性性质质的的魔魔方方全全体体构构成成一一个个线线性性空空间间。根根据据线线性性代代数数知知识识，要要刻刻画画一一个个线线性性空空间间只只需需指指出出它它的的维维数数并并求求出出此此线线性性空空间间的的一一组组基底即可。基底即可。7/4/202424MCM不妨仍以不妨仍以4 4阶方阵为例。首先，定义阶方阵为例。首先，定义0-0-方与方与1-1-方如下：方如下：其其中中R R为为行行和和，C C为为列列和和，D D为为对对角角线线和和，S S为为小小方方块和。块和。现现在在，我我们们来来研研究究具具有有性性质质R=C=D=SR=C=D=S的的方方阵阵构构成成的的线线性性空空间间 ，类类似似于于构构造造n n维维欧欧氏氏空空间间的的标标准准基基，我我们们利利用用0 0和和1 1来来构构造造一一些些R=C=D=S=1R=C=D=S=1的的最最简简单单的的方方阵阵，不不难难看看出出，1 1在在第第一一行行中中共共有有4 4种种排排法法，为为保保持持上上述述性性质质的的成成立立，在在第第一一行行的的1 1取取定定后后，第第二二行行中中的的1 1尚尚有有两两种种取取法法。当当第第二二行行的的1 1也也取取定定后后，第第三三行行与与第第四四行行的的1 1就就完完全全定定位位了了，故故一一共共可可作作出出8 8个个不不同同的的最最简简方方阵阵，称称之之为为基基本本魔魔方方并并记记之之为为Q1Q1，Q8Q8。7/4/202425MCM7/4/202426MCM 显显然然，D D中中任任何何一一个个元元素素都都可可以以用用Q Q1 1，Q Q2 2，Q Q8 8来来线线性性表表示示，它它们们能能否否构构成成D D的的一一组组基基，关关键键在在于于它它们们是是否线性无关。否线性无关。容易看出容易看出 所所以以Q Q1 1，Q Q2 2，Q Q8 8这这8 8个个基基本本方方是是线线性性相相关关的的，即即至至少少存存在在一一个个Q Qj j，可可以以通通过过其其它它7 7个个基基本本方方的的线线性性组组合合得得到到，这这8 8个个基基本本方方的的地地位位是是等等同同的的，故故可可不不妨妨设设j=8j=8。下下面验证面验证Q Q1 1，Q Q2 2，Q Q7 7是否线性相关。是否线性相关。令令，即即 7/4/202427MCM 等等号号两两边边对对应应元元素素相相比比较较，得得r r1 1=r=r2 2=r=r7 7=0=0，所所以以Q Q1 1，Q Q2 2，Q Q7 7是是线线性性无无关关的的。Q Q1 1，Q Q2 2，Q Q7 7是是D D空空间间的的一一组组基基，D D中中任任何何元元素素都都可可以以由由Q Q1 1，Q Q2 2，Q Q7 7的的线线性性组组合合生生成成。可可以以这这样样认认为为：Q Q1 1，Q Q2 2，Q Q8 8 是是D D的的生生成成集集，但但不不是是最最小小生生成成集集，而而 Q Q1 1，Q Q2 2，Q Q7 7 是是D D的的最小生成集。最小生成集。7/4/202428MCM 现现在在，我我们们回回到到Albrecht Albrecht DrerDrer铸铸造造的的铜铜币币，以以Q Q1 1，Q Q2 2，Q Q7 7的的 线线 性性 组组 合合 表表 示示 铜铜 币币 上上 的的 魔魔 方方，D=D=d d1 1Q Q1 1+d+d2 2Q Q2 2+d+d7 7Q Q7 7，即解方程组，即解方程组 解得解得7/4/202429MCM3 3、D D空间的子空间和空间的子空间和D D空间的扩展空间的扩展 改改变变对对DrerDrer魔魔方方数数字字和和的的要要求求，我我们们可可以以利利用用线线性性子子空空间间的的定定义义，构构造造D D的的子子空空间间或或者者构构造造新新的的空空间间包包含含D D空间。这里，我们规定仅包含空间。这里，我们规定仅包含0 0方的向量空间维数为零。方的向量空间维数为零。(1)(1)要要 求求 数数 字字 方方 的的 所所 有有 数数 都都 相相 等等。这这 是是 集集 合合G=G=rE,rRrE,rR，G G是是以以GG=E=E为为基基的的一一维维向向量量空空间间，是是D D的一维子空间。的一维子空间。(2)(2)要要求求列列和和，行行和和及及每每条条主主、付付对对角角线线上上数数字字和和都都相相等，得到等，得到5 5维泛对角方的向量空间维泛对角方的向量空间B B。例如：。例如：7/4/202430MCMH=N=R=C=S=46H=N=R=C=S=46其其中中H H为为主主对对角角线线和和，N N为付对角线和。为付对角线和。它的基它的基BBBB为为7/4/202431MCM(3)(3)要要求求行行和和，列列和和及及两两条条对对角角线线上上的的元元素素和和相相等等，得得到到8 8维维向向量量空空间间Q Q，基基向向量量Q QB B=Q Q1 1，Q Q2 2，Q Q7 7，N N0 0，其中，其中Q Q1 1，Q Q2 2，Q Q7 7是是D D的基，的基，例如：例如：R=C=D=30R=C=D=307/4/202432MCM(4)(4)仅仅要要求求行行和和与与列列和和相相等等，可可以以得得到到1010维维向向量量空空间间，它它的的基基B B=Q Q1 1，Q Q2 2，Q Q7 7，N N1 1，N N2 2，N N3 3，其其中中Q Q1 1，Q Q2 2，Q Q7 7是是D D的基，而的基，而7/4/202433MCM(5)(5)如如果果我我们们对对数数字字没没任任何何要要求求，那那么么所所有有的的4444数数字字方方组组成成的的向向量量空空间间M M，它它的的维维数数是是1616，基基向向量量MBMB中中的的元元素素应应是是标标准准基基，(即即仅仅有有一一个个元元素素为为1 1，其其余余元元素素均均为为0 0的方阵的方阵)。Botsch(1976Botsch(1976年年)证证明明了了可可以以构构造造大大量量的的D D的的子子空空间间或或D D的的扩扩张张空空间间。对对于于1 1与与1616之之间间的的每每一一个个数数K K，都都存存在在K K维维的的4444方方的的向向量量空空间间，其其中中的的每每一一方方阵阵都都具具有有某某些些特定的性质。特定的性质。由上可知，有下式成立由上可知，有下式成立(向量空间向量空间)0 1 5 7 8 10 160 1 5 7 8 10 16(维数维数)7/4/202434MCM 4.3 4.3 密码的设计、解码与破译密码的设计、解码与破译 密密码码的的设设计计和和使使用用至至少少可可以以追追溯溯到到四四千千多多年年前前的的埃埃及及 、巴巴比比伦伦、罗罗马马和和希希腊腊，历历史史极极为为久久远远。古古代代隐隐藏藏信信息息的的方方法法主主要要有有两两大大类类：其其一一为为隐隐藏藏信信息息载载体体，采采用用隐隐写写术术等等；其其二二为为变变换换信信息息载载体体，使使之之无无法法为为一一般般人人所所理理解解。本本节节只只涉涉及及后后者者，介介绍绍一一些些采采用用数数学学工工具具对对信信息息加加密、解密的方法。密、解密的方法。在在密密码码学学中中，信信息息代代码码被被称称为为密密码码，加加密密前前的的信信息息被被称称为为明明文文，经经加加密密后后不不为为常常人人所所理理解解的的用用密密码码表表示示的的信信息息被被称称为为密密文文(ciphertextciphertext)，将将明明文文转转变变成成密密文文的的过过程程被被称称为为加加密密(enciphering)(enciphering)，其其逆逆过过程程则则被被称称为为解解密密(deciphering)(deciphering)，而而用用以以加加密密、解解密密的的方方法法或或算算法法则则被被称称为密码体制为密码体制(crytosystemcrytosystem)。7/4/202435MCM 记记全全体体明明文文组组成成的的集集合合为为U U，全全体体密密文文组组成成的的集集合合为为V V，称称U U为为明明文文空空间间，V V为为密密文文空空间间。加加密密常常利利用用某某一一被被称称为为密密钥钥的的东东西西来来实实现现，它它通通常常取取自自于于一一个个被被称称为为密密钥钥空空间间的的含含有有若若干干参参数数的的集集合合K K。按按数数学学的的观观点点来来看看，加加密密与与解密均可被看成是一种变换解密均可被看成是一种变换(或称映射或称映射)：取一：取一k kK K，u uU U，令令 ，v v为为明明文文u u在在密密钥钥K K下下的的密密文文，而而解解码码则则要要用用到到K K的的逆逆变变换换K K-1-1，。由由此此可可见见，密密码体系虽然可以千姿百态，但其关键还在于密钥的选取。码体系虽然可以千姿百态，但其关键还在于密钥的选取。随随着着计计算算机机与与网网络络技技术术的的迅迅猛猛发发展展，大大量量各各具具特特色色的的密密码码体体系系不不断断涌涌现现。离离散散数数学学、数数论论、计计算算复复杂杂性性、混混沌沌、，许许多多相相当当高高深深的的数数学学知知识识都都被被用用上上，逐逐步步形形成成了了(并并仍仍在在迅迅速速发发展展的的)具具有有广广泛泛应应用用面面的的现现代代密密码码学。学。7/4/202436MCM 早早期期密密码码大大体体可可分分三三类类：代代替替法法密密码码、移移位位密密码码和和代数密码。代数密码。代替法密码代替法密码 代代替替法法密密码码采采用用另另一一个个字字母母表表中中的的字字母母来来代代替替明明文文中中的的字字母母，明明文文字字母母与与密密文文字字母母保保持持一一一一对对应应关关系系，但但采采用用的的符符号号改改变变了了。加加密密时时，把把明明文文换换成成密密文文，即即把把明明文文中中的的字字母母用用密密文文字字母母表表中中对对应应位位置置上上的的字字母母取取代代。解解密密时时，则则把把密密文文换换成成明明文文，即即把把密密文文中中的的字字母母用用明明文文字字母母表表中中对对应应位位置置上上的的字字母母代代回回,解解密密过过程程是是加加密密过过程程的的逆逆过过程程。在在代代替替法法加加密密过过程程中中，明明文文字字母母表表、密密文文字字母母表表及及两两者者间间的的对对应应关关系系即即为为代代替替法法密密钥钥，密密钥钥既既可可以以采采用用标标准准字字母母表表，也也可可以以任任意意建建立立。例例如如，我我们们可可采采用用以以下下的明文字母表和密文字母表：的明文字母表和密文字母表：7/4/202437MCM明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJ 密密钥钥还还经经常常用用一一密密钥钥字字或或密密钥钥短短语语生生成成混混淆淆字字母母表表。密密钥钥字字或或密密钥钥短短语语可可以以存存放放在在识识别别码码、通通行行字字或或密密钥钥的的秘秘密密表表格格中中。混混合合一一个个字字母母表表，常常见见的的有有两两种种方方法法，这这两种方法都采用了一个密钥字或一个密钥短语。两种方法都采用了一个密钥字或一个密钥短语。方法一：方法一：a)a)选择一个密钥字或密钥短语，例如：选择一个密钥字或密钥短语，例如：constructconstructb)b)去掉其中重复的字母，得：去掉其中重复的字母，得：construconstruc)c)在修改后的密钥字后面接上从标准字母表中去在修改后的密钥字后面接上从标准字母表中去掉密钥中的已有字母后剩下的字母，得：掉密钥中的已有字母后剩下的字母，得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZCONSTRUABDEFGHIJKLMPQVWXYZ7/4/202438MCM 在在设设计计密密钥钥时时，也也可可在在明明文文字字母母表表中中选选择择一一个个特特定定字字母母，然然后后从从该该特特定定字字母母开开始始写写密密钥钥字字并并将将密密钥钥字字隐隐藏藏于其中。例如，对于上例，选取特定字母于其中。例如，对于上例，选取特定字母k k，则可得：，则可得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ KLMPQVWXYZCONSTRUABDEFGHIJ 方法二：方法二：a)a)选择一个密钥字或密钥短语，例如：选择一个密钥字或密钥短语，例如：constructconstruct b)b)去掉其中重复的字母，得：去掉其中重复的字母，得：construconstru c)c)这些字母构成矩阵的第一行，矩阵的后续各行由这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥字的字母后剩下的字母构成标准字母表中去掉密钥字的字母后剩下的字母构成7/4/202439MCMd)d)把所得矩阵中的字母按列的顺序选出，得：把所得矩阵中的字母按列的顺序选出，得：caivobjwndkxselytfmzrgpuhqcaivobjwndkxselytfmzrgpuhq按照此方法产生的字母表称为混淆字母表。按照此方法产生的字母表称为混淆字母表。7/4/202440MCM 在在代代替替法法加加密密中中，除除了了使使用用混混淆淆字字母母表表外外，还还可可以使用混淆数。混淆数由以下方法产生：以使用混淆数。混淆数由以下方法产生：a)a)选一密钥字或密钥短语，例如：选一密钥字或密钥短语，例如：constructconstructb)b)按按照照这这些些字字母母在在标标准准字字母母表表中中出出现现的的相相对对顺顺序序给给它它们们编号，对序列中重复的字母则自左向右编号，得：编号，对序列中重复的字母则自左向右编号，得：construct construct 143675928 143675928c)c)自自左左向向右右选选出出这这些些数数字字，得得到到一一混混淆淆数数字字组组：143675928143675928，混混淆淆字字母母表表由由从从小小到到大大的的顺顺序序取取矩矩阵阵中中相相应应列列得得出出,先先取取第第一一列列、再再取取第第8 8列列、，依依次次得得出出秘秘文字母表。文字母表。为为增增加加保保密密性性，在在使使用用代代替替法法时时还还可可利利用用一一些些其其他他技技巧巧，如如单单字字母母表表对对多多字字母母表表、单单字字母母对对多多字字母母、多多重重代代替等，这里就不再一一细说了。替等，这里就不再一一细说了。7/4/202441MCM移位密码体制移位密码体制 移移位位密密码码采采用用移移位位法法进进行行加加密密，明明文文中中的的字字母母重重新新排列，本身不变，只是位置改变了。排列，本身不变，只是位置改变了。现现在在所所知知的的最最为为古古老老的的加加密密方方法法天天书书就就是是移移位位法法的的一一种种。早早在在40004000多多年年前前，古古希希腊腊人人就就用用一一种种名名叫叫“天天书书”的的器器械械来来加加密密消消息息。该该密密码码器器械械是是用用一一条条窄窄长长的的草草纸纸缠缠绕绕在在一一个个直直径径确确定定的的圆圆筒筒上上，明明文文逐逐行行横横写写在在纸纸带带上上，当当取取下下纸纸带带时时，字字母母的的次次序序就就被被打打乱乱了了，消消息息得得以以隐隐蔽蔽。收收方方阅阅读读消消息息时时，要要将将纸纸带带重重新新绕绕在在直直径径与与原原来来相相同同的的圆圆筒筒上上，才才能能看看到到正正确确的的消消息息，在在这这里里圆圆筒筒的的直直径起到了密钥的作用。径起到了密钥的作用。7/4/202442MCM 另另一一种种移移位位法法采采用用将将字字母母表表中中的的字字母母平平移移若若干干位位的的方方法法来来构构造造密密文文字字母母表表，传传说说这这类类方方法法是是由由古古罗罗马马皇皇帝帝凯凯撒撒最最早早使使用用的的，故故这这种种密密文文字字母母表表被被称称为为凯凯撒撒字字母母表表。例例如如，如如用用将将字字母母表表向向右右平平移移3 3位位的的方方法法来来构构造造密密文文字字母母表，可得：表，可得：明文字母表：明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表：密文字母表：DEFGHIJKLMNOPQRTSUVWXYZABCDEFGHIJKLMNOPQRTSUVWXYZABC 使使用用这这一一密密文文字字母母表表加加密密，THANK THANK YOU YOU 被被加加密密成成 WKDQN BRXWKDQN BRX，起到了一定的保密作用。，起到了一定的保密作用。以以上上两两种种移移位位极极易易被被人人破破译译，为为打打破破字字母母表表中中原原有有的的顺顺序序还还可可采采用用所所谓谓路路线线加加密密法法，即即把把明明文文字字母母表表按按某某种种既既定定的的顺顺序序安安排排在在一一矩矩阵阵中中，然然后后用用另另一一种种顺顺序序选选出出矩矩阵中的字母来产生密文表。阵中的字母来产生密文表。7/4/202443MCM例例如如，对对明明文文：THE THE HISTORY HISTORY OF OF ZJU ZJU IS IS MORE MORE THAN THAN ONE ONE HUNDRED YEARS.HUNDRED YEARS.以以7 7列矩阵表示如下：列矩阵表示如下：THEHISTTHEHISTORYOFZJORYOFZJUISMOREUISMORETHANONETHANONEHUNDREDHUNDREDYEARSYEARS再按事先约定的方式选出密文。例如，如按列选出，得到再按事先约定的方式选出密文。例如，如按列选出，得到密文：密文：touthyhrihueeysanahomndrifoorsszrnetjeedtouthyhrihueeysanahomndrifoorsszrnetjeed7/4/202444MCM 使使用用不不同同的的顺顺序序进进行行编编写写和和选选择择，可可以以得得到到各各种种不不同同的的路路线线加加密密体体制制。对对于于同同一一明明文文消消息息矩矩阵阵，采采用用不不同同的的抄抄写写，得得到到的的密密文文也也是是不不同同的的。如如果果对对上上例例明明文文消消息息矩阵从左上角开始沿对角线抄写，得到的密文是：矩阵从左上角开始沿对角线抄写，得到的密文是：tohuretiyhhhsoiyuamfsennoztadorjrrneseedtohuretiyhhhsoiyuamfsennoztadorjrrneseed 在在使使用用上上述述方方法法时时矩矩阵阵的的规规模模必必须须事事先先约约定定，它它增增加加了了对对明明文文的的保保护护程程度度。当当明明文文超超过过规规定定矩矩阵阵的的大大小小时时，可可以以另另加加一一矩矩阵阵。当当需需要要加加密密的的字字母母数数小小于于矩矩阵阵大大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。小时，可以在矩阵中留空位或以无用的字母来填满矩阵。移移位位法法也也可可和和代代替替法法结结合合使使用用，并并使使用用约约定定的的单单词词或或短短语语作作密密钥钥，以以进进一一步步加加强强保保密密性性，这这就就是是钥钥控控列列序序加密法。加密法。7/4/202445MCM例例 如如，用用 密密 钥钥 字字 constructconstruct对对 明明 文文 MATHEMATICAL MATHEMATICAL MODELING IS USEFULMODELING IS USEFUL加密：加密：1 4 36 75 9 2 81 4 36 75 9 2 8CONSTRUCTCONSTRUCTMATHEMATIMATHEMATICALMODELICALMODELINGISUSEFUNGISUSEFUL L按混淆数的顺序选出各列，得到密文：按混淆数的顺序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEEMCNLTLFTLIAAGMDSHMSEOSIIUAEE 矩矩阵阵的的最最后后一一行行可可以以用用无无用用的的字字母母填填满满，但但若若不不加加字字母母，则则保保密密程程度度可可以以有有所所提提高高。移移位位法法的的使使用用可可重重复复多多次次，只只进进行行一一次次移移位位加加密密的的称称为为一一次次移移位位法法，经经多多次次移位的则称为多次移位法移位的则称为多次移位法。7/4/202446MCM代替法与移位法密码的破译代替法与移位法密码的破译 对对窃窃听听到到的的密密文文进进行行分分析析时时，穷穷举举法法和和统统计计法法是是最最基基本本的的破破译译方方法法，其其他他特特殊殊的的方方法法大大多多是是这这两两种种方方法法的的综合和改进。综合和改进。穷穷举举分分析析法法就就是是对对所所有有可可能能的的密密钥钥或或明明文文进进行行逐逐一一试试探探，直直至至试试探探到到“正正确确”的的为为止止。此此方方法法需需要要事事先先知知道道密密码码体体制制或或加加密密算算法法（但但不不知知道道密密钥钥或或加加密密的的具具体体办办法法）。破破译译时时需需将将猜猜测测到到的的明明文文和和选选定定的的密密钥钥输输入入给给算算法法，产产生生密密文文，再再将将该该密密文文与与窃窃听听来来的的密密文文比比较较。如如果果相相同同，则则认认为为该该密密钥钥就就是是所所要要求求的的，否否则则继续试探，直至破译。继续试探，直至破译。7/4/202447MCM 以以英英文文字字母母为为例例，当当已已知知对对方方在在采采用用代代替替法法加加密密时时，如如果果使使用用穷穷举举字字母母表表来来破破译译，那那么么对对于于最最简简单单的的一一种种使使用用单单字字母母表表单单字字母母单单元元代代替替法法加加密密的的密密码码，字字母母表表的的可可能能情情况况有有2626！种种，可可见见，单单纯纯地地使使用用穷穷举举法法，在在实实际应用中几乎是行不通的，只能与其它方法结合使用。际应用中几乎是行不通的，只能与其它方法结合使用。统统计计法法是是根根据据统统计计资资料料进进行行猜猜测测的的。在在一一段段足足够够长长且且非非特特别别专专门门化化的的文文章章中中，字字母母的的使使用用频频率率是是比比较较稳稳定定的的。在在某某些些技技术术性性或或专专门门化化文文章章中中的的字字母母使使用用频频率率可可能能有微小变化。有微小变化。在在上上述述两两种种加加密密方方法法中中字字母母表表中中的的字字母母是是一一一一对对应应的的，因因此此，在在截截获获的的密密文文中中各各字字母母出出现现的的概概率率提提供供了了重重要的密钥信息。要的密钥信息。7/4/202448MCM 根根据据权权威威资资料料报报道道，可可以以将将2626个个英英文文字字母母按按其其出出现现的频率大小较合理地分为五组：的频率大小较合理地分为五组：()()t,a,o,i,n,s,h,rt,a,o,i,n,s,h,r;()e;()e;()()d,ld,l;()()c,u,m,w,f,g,y,p,bc,u,m,w,f,g,y,p,b;()()v,k,j,x,q,zv,k,j,x,q,z;不不仅仅单单个个字字母母以以相相当当稳稳定定的的频频率率出出现现，相相邻邻字字母母对对和三字母对同样如此。按频率大小将双字母排列如下：和三字母对同样如此。按频率大小将双字母排列如下：th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,th,he,in,er,an,re,ed,on,es,st,en,at,to,nt,ha,nd,ou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,ofou,ea,ng,as,or,ti,is,er,it,ar,te,se,hi,of7/4/202449MCM使用最多的三字母按频率大小排列如下：使用最多的三字母按频率大小排列如下：The,ing,and,her,ere,ent,tha,nth,was,eth,for,dthThe,ing,and,her,ere,ent,tha,nth,was,eth,for,dth下面介绍一下统计观察的三个结果：下面介绍一下统计观察的三个结果：a)a)单词单词thethe在这些统计中有重要的作用；在这些统计中有重要的作用；b)b)以以e e，s s，d d，t t为结尾的英语单词超过了一半；为结尾的英语单词超过了一半；c)c)以以t t，a a，s s，w w为起始字母的英语单词约为一半。为起始字母的英语单词约为一半。对于对于a a），如果将），如果将thethe从明文中删除，那么从明文中删除，那么t t的频率将的频率将要降到第二组中其他字母之后，而要降到第二组中其他字母之后，而h h将降到第三组中，将降到第三组中，并且并且thth和和hehe