第六章代数模型.ppt

生小兔问题 植物基因的分布 常染色体的隐性疾病 信息加密与解密 森林管理问题 1.2 现实世界中兔子数量的变化 问题分析 根据理想情形兔子数量的变化规律，可知此时为 设P1(n), P2(n), P3(n)分别表示第n代植物总数中基因型为AA,Aa,aa的植物所的百分比， P(n)为第n代植物中的基因分布向量，即 P(n)=( P1(n), P2(n), P3(n) )T, n=0,1,2，…… 显然， P1(n)+P2(n)+P3(n)=1。 4.2 早期密码 练习 答 逆矩阵为 4.3 RSA公开密钥体制 一.线性规划的实例与定义 例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则 x1 、x2应满足 二、线性规划的标准形式 如果根据实际问题建立起来的线性规划问题并非标准形 式，可以将它如下化为标准形式： 三、线性规划的图解法 三、基本解与基本可行解 四、基本可行解与极点的等价定理 （线性规划基本定理） 线性规划（5.3）具有以下性质： （1）若可行域R≠Φ，则必存在一个基本可行解。 （2）若问题存在一个最优解 ，则必存在一个最优的基本可行解。 如 ， (用9乘第二行并取同 余) ， 第一行减去第二行 的2倍并取同余，得 ， 左端矩阵已化为单位阵，故右端矩阵即为 A-1 希尔密码系统的解密依赖于以下几把钥匙 （key）： Key1 矩阵A的阶数n，即 明文是按几个字母来 划分的。 Key2 变换矩阵A，只有知 道了A才可能推算出Key3 明文和密文由字母表 转换成 n维向量所对 应的非负整数表（上 面，为方便起见，我 们采用了字母的自然 顺序）。 希尔密码体系为破译者设置了多道关口，加大了破译难度。破译和解密是两个不同的概念，虽然两者同样是希望对密文加以处理而得到明文的内容，但是他们有一个最大的不同——破译密码时，解密必需用到的钥匙未能取得，破译密码的一方需要依 据密文的长度，文字的本身特征，以及行文习惯 等等各方面的信息进行破译。破译密码虽然需要技术，但更加重要的是“猜测”的艺术。“猜测”的成功与否直接决定着破译的结果。 破译希尔密码的关键是猜测文字被转换成成几维向量、所对应的字母表是怎样的，更为重要的是要设法获取密钥矩阵A。 （希尔密码的破译） 由线性代数的知识可以知道，矩阵完全由一组基的变换决定，对于n阶矩阵A，只要猜出密文中n个线性无关的向量 (i=1, 2, …, n) 对应的明文 (i=1, 2, …, n)是什么 ，即可确定A，并将密码破译。 在实际计算中，可以利用以下方法： 令 则 ， 取矩阵[Q | P],经过一系列初等行变换，将由密文决定 的n维矩阵Q化为n阶单位阵 I的时候，由明文决定的矩 阵P自动化为 (A-1)T，即 ： 例5 有密文如下:goqbxcbuglosnfal;根据英文的行文习惯以及获取密码的途径和背景，猜测是两个字母为一组的希尔密码，前四个明文字母是dear，试破译这段秘文。 解： 前两组明文字 母de和ar 对应的二维向量是： 按同一对应整数表，密文中对应这两组的二维向量是： ， ， 由此可得 对应上例则有 , 利用这一逆矩阵，可对截获密文进行解密，破译出的电文是Dear Mac God forbid. 这只是对最简单情况进行的举例，如果加密矩阵的阶数大于2，需要的密文应该有较长长度，所需的计算量也是很大的。破译的关键是猜中n及n个独立的n维向量，其后求解加密矩阵的计算量仅为O(n2 )。 希尔密码体制中有两个要素非常重要： 第一是字母 与n维向量进行转换所依据的非负整数表，本节中所举的是最自然的情况；当然如果依据其它的整数表也是完全可以进行的，其情况将会更复杂一些，破译的难度就会增大。 第二个要素是加密矩阵，如何定义、求解这个矩阵对于密码的加密和破译更加关键。唯一的要求是加密时应选择行列式值与 26无公因子的矩阵。 取 用A加密meet, 再求其逆矩阵对其解密 传统的密码通讯只能在事先约定的双方间进行，双方必须掌握相同的密钥，而密钥的传送必须使用另外的“安全信道”。这样如果要使 n个用户都能够秘密的交换信息，则每