线性代数智能化教学系统第8节.ppt

流动问题 希尔密码 第2.8节 矩阵的应用 平面图形变换 齐次坐标 2.8.1 流动问题 流动问题主要有人口流动和物资流动问题，本例 是人口流动问题，物资流动问题参阅习题． 例1 设某中小城市及郊区乡镇共有30万人从事 农、工、商工作，假定这个总人数在若干年内保持 不变，而社会调查表明： （１）在这30万就业人员中，目前约有15万人从 事农业，9万人从事工来，6万人从事经商： （2）在务农人员中，每年约有20%改为务工， 10%改为经商； （3）在务工人员中，每年约有20%改为务农， 10%改为经商； （4）在经商人员中，每年约有10%改为务农， 10%改为务工； 现在想预测1，2年后从事各业人员的人数，以及经 过多年后，从事各业人员总数之间的发展趋势。 解 设 xi , yi , zi 表示第 i 年后分别从事农、工、 商的人员总数，则 x0 = 15， y0 = 9， z0 = 6，现要 求 x1 ， y1 ， z1 和 x2 ， y2 ， z2 ，并考察当 n 年后 xn , yn , zn 的发展趋势． 根据题意，一年后从事农、工、商的人员总数为 即 其中 将 x0 = 15， y0 = 9， z0 = 6 代入上式，得 即一年后从事农、工、商的人员的人数分别为12.9 万人、9.9万人、7.2万人． 当 n = 2时，有 进而推得 即 n 年后从事农、工、商的人员的人数由 An 决定． 2.8.2 希尔密码 1929年，希尔利用线性代数中的矩阵乘积运算， 为了便于计算，希尔首先将字符变换成数. 设计了一种被称为希尔密码的代数密码． 对英文字母，可以作如下变换： 例如， 0 25 24 23 22 21 20 19 18 17 16 15 14 Z Y X W V U T S R Q P O N 13 12 11 10 9 8 7 6 5 4 3 2 1 M L K J I H G F E D C B A 希尔密码的基本思想： 将明文分成 n 个一组，用对应的数字代替，就变 如果取定一个 n 阶的可逆矩阵 成了一个个 n 维向量. 将密文分成 n 个一组，同样变成 n 维向量，只需 A（此矩阵称为密钥），用 A 去乘每一个向量，即可 起到加密的效果. 用 A–1 去乘这些向量，即可将它们变回原先的明文. 两个问题： 1）为了使数字与字符间可以互换，必须使用取自 0 ~ 25之间的整数； 2）在解密时要用到逆矩阵，而 可能会出现分数． 解决的办法：引进同余运算，并用乘法来代替除法． 考虑最简单的情况. 令 n = 1，用数 a 去乘 0 ~ 25 中的数，以 26 为模取同余， 并要求有 使得 或要求存在 a –1，使得 a –1a ? 1 (mod 26)， 经简单的分析即可发现，并非所有0 ~ 25 中的数 都可用来作为这里的 a， 事实上我们可以证明下面的 a –1 ? { 0, … , 25 }， ? p ? { 0, … , 25 }，有a –1ap ? p (mod 26). 称 a –1 为 a 的逆元素． 定理 ： 定理 a ? { 0, … , 25 }，若 ? a–1 ? { 0, … , 25 }, 使得 a a–1 = a–1a = 1 (mod 26)，则必有gcd{a, 26} = 1， 其中gcd{a, 26} 为 a 与 26 的最大公因数． 由定理可知，0 ~ 26 中除 13 以外的奇数均可取作 这里的 a，下面列出经计算求得的逆元素． 25 17 5 11 23 7 19 3 15 21 9 1 a–1 25 23 21 19 17 15 11 9 7 5 3 1 a 对于 n 为一般整数的情况，只需在乘法运算中结 合应用取余，求逆矩阵时用逆元素乘来代替除法即可． 希尔密码是以矩阵法为基础的，明文与密文的对 应由 n 阶矩阵 A 确定． 的，与明文分组时每组字母的字母数量 n 相同. 果明文所含字数与 n 不匹配，则最后几个分量可任意 补足． 矩阵 A 的阶数是事先约定 如 希尔密码在解密时，用 A–1 左乘密文向量，即 可还原为原来的明文向量． A–1 的求法可利用公式 ， 例如，若取 则 |A| = 3， 查表知 |A| 的逆元素为 9，于是 即 例2 设明文为HPFRPIHTNECL，密钥矩阵为 试用希尔密码体系给明文加密． 实验系统 例3 设密文为DXNANIURJUOD，密钥矩阵为 试将密文还原为明文． 实验系统 2.8.3 平面图形变换 1.线性变换 定义 10 变换（或映射）T 称为线性的，若 (i) 对 T 的定义域中的一切向量u，v，有 T (