第10章线性代数模型.ppt

有些复杂问题，往往给人以变幻莫测的感觉，难以掌握其中的奥妙。当我们把思维扩展到线性空间，利用线性代数的基本知识建立模型，就可以掌握事物的内在规律，预测其发展趋势。,第10章 线性代数模型,凭似影碉笼萌肆磊棘散帧瓷仇缆菱龟凸沤片恶闯组素晌窟抖阁驼犯讥完厘第10章线性代数模型第10章线性代数模型,10.1 Durer 魔方,德国著名的艺术家 Albrecht Durer(1471-1521)于1514年曾铸造了一枚名为“Melen cotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数学数字和几何图形。这里我们仅研究铜币右上角的数字问题。,歪松歇北株娱敖拖辐骤牛邱凝纯蝎蠢虾楚缘式赛喝作鹏渺异休枫达燥揍攫第10章线性代数模型第10章线性代数模型,1 Durer 魔方,特点,每行之和、每列之和、对角线之和、四个小方块之和、中心方块之和都相等，为确定的数34。,所出现的数是1至16的自然数。,四角之和、中间对边之和均为34。,最下边一行中心数为1514，正是制币的时间。,问题,是否还存在具有这些（或部分）性质的魔方？,手宙圭屈哼抵伟以恋孝航寞趁莹硷减热颓阻淑阁虐泌助致块永敲岔黍倚噬第10章线性代数模型第10章线性代数模型,定义,如果44数字方，它的每一行、每一列、每一对角线及每个小方块上的数字之和都为一确定的数，则称这个数字方为 Durer 魔方。,R=C=D=S,痉樟捞戚屁心瘟释砾贷烈凹雅颈惦鱼釜泄授畔乡割糯倾恫馒库钻罐模茨描第10章线性代数模型第10章线性代数模型,你想构造Durer魔方吗？如何构成所有的Durer魔方？Durer魔方有多少？,2 Durer魔方的生成集,所有的Durer魔方的集合为 D,O=,E=,R=C=D=S=0,R=C=D=S=4,藩哆牌徐累夺疾诬陷胞晋家待啊承咳核壬冰惰据盆啪摩郁顾居粮宪耪眷条第10章线性代数模型第10章线性代数模型,A=,B=,类似于矩阵的加法和数乘，定义魔方的加法和数乘。易验证，D 加法和数乘封闭，且构成一线性空间。,记 M=所有的44数字方，则其维数为16。而D是M的子集，则D是有限维的线性空间。,根据线性空间的性质，如果能得到D的一组基，则任一个Durer方均可由这组基线性表示。,规硫评丘鹿氢勒阻曼创葫蹭泵汕扣恐哲澎虞谜黄转皱讯淑城诵杉算巡吮埋第10章线性代数模型第10章线性代数模型,由 0,1 数字组合，构造所有的R=C=D=S=1的魔方。共有8 个，记为Qi,i=1,2,8。,Q1=,Q2=,Q3=,Q4=,尧侮辈灶略则蛀渭湃屋琵疑椎窗芯椰窄郭抓诽压寨情戒衷珊理剪悼想茬鞍第10章线性代数模型第10章线性代数模型,Q5=,Q6=,Q7=,Q8=,穗灶晚枷讣谢变讯忧腹守谁辛限浩括归蚂乙篆汞箔埃焉谜赞喷猫酬芭斑诡第10章线性代数模型第10章线性代数模型,易知,则,线性相关。,而由,=,线性无关。任一Durer方可由它们线性表示。,渝焙攻棵括毖胖惦妹封苗葡慌抬馁粗远够自飞酚顾听乓蚀愚糜疆对醉骄杨第10章线性代数模型第10章线性代数模型,结论：,1 Durer方有无穷多个。,2 Durer方可由,线性组合得到。,Albrecht Durer的数字方的构成：,=,滞蔷金绪锋您莫霞也谰烫衬营词强瞅饲梅慷讽利骆澳权吴隘砸聪康蓝兔津第10章线性代数模型第10章线性代数模型,3 Durer方的应用推广,（1）要求数字方的所有数字都相等。,基为,1维空间,（2）要求行和、列和、每条主对角线及付对 角线数字和都相等。,基为,5维空间,蛇韩仍咱渍早袄狙茫唆践职件冶宣菠蓉沉葱碌夏毒攘氓氧弯怂陪泰汹随校第10章线性代数模型第10章线性代数模型,朋等耿魁铺躇宪批撵荐沽景迸桑蓑钮骗乡抚蓄蔫兜沮渊膨丑丽媳柠狂棵烩第10章线性代数模型第10章线性代数模型,例,R=C=H=N=46,H 主对角线，N付对角线数字和。,（3）要求行和、列和及两条对角线数字和相等。,8维空间Q。,基为,D是Q的7维子空间。,榨哭鸯褪跋捞樊惺轮妙屋赊节垢所廉绿唤构圭递喻睦茁爹宽犹约厘级莆桅第10章线性代数模型第10章线性代数模型,例,R=C=D=30,（4）要求行和、列和数字相等。,10维空间W。,基为,备板已复藉爽武怠神寸栖骸毗酉铡份禹腋礁能捅茂戊尼蔷倾峻萌座夫蠕豪第10章线性代数模型第10章线性代数模型,（5）对数字没有任何要求的数字方,16维空间M,空间,维数,0 1 5 7 8 10 16,思考,能否构造出其他维数的数字方？,钮国音誓酵迸东规麓攒劳乎妓豪草阿援蠕侵砚傻觉肢后嗡咳熊乍慰善壤尖第10章线性代数模型第10章线性代数模型,练习,完成下面的Durer方,R=C=D=S=30,R=C=D=S=100,裤郭绽姆骇尸渣液沉援翌谦盾靴押追卤键娱耳悄掌瞧遍槐醉嘉稍船霞奶傀第10章线性代数模型第10章线性代数模型,作业,构造你自己认为有意义的Durer方。,垄隆难鄂敬装茨源放欺关富赣崭帐辰脏聋晒竟恍藏社制廊付厢硫胁宵器主第10章线性代数模型第10章线性代数模型,10.2 植物基因的分布,设一农业研究所植物园中某植物的的基因型为AA、Aa 和 aa。研究所计划采用AA型的植物与每一种基因型植物相结合的方案培育植物后代。问经过若干年后，这种植物的任意一代的三种基因型分布如何？,滇喝整气敖芥炮商圃岩桂诺怪端缕嗣骗蔓迷率液竿锯匠爬愧成嘶钉访蝎论第10章线性代数模型第10章线性代数模型,1 建模准备,植物遗传规律？,动植物都会将本身的特征遗传给后代，这主要是因为后代继承了双亲的基因，形成了自己的基因对，基因对就确定了后代所表现的特征。,常染色体遗传的规律：,后代是从每个亲体的基因对中个继承一个基因，形成自己的基因对，即基因型。,塞菲滇症称庶搔乙果原总滑卤兴惊涉凶遗镍瘪九蔗毋嫂忿叼防声帅拯友庶第10章线性代数模型第10章线性代数模型,如果考虑的遗传特征是由两个基因 A、a控制的，那末就有三种基因对，记为AA、Aa 和 aa。,金鱼草花的颜色是由两个遗传因 子决定的，基因型为AA的金鱼草开红花，Aa 型的开粉红花，而 aa型的开白花。人类眼睛的颜色也是通过常染色体来控制的。基因型为AA，或Aa 型的人眼睛颜色为棕色，而 aa型的人眼睛颜色为蓝色。这里AA，Aa表示同一外部特征，我们认为基因A支配基因a，即基因a对A来说是隐性的。,如,西鼎竿敖驭钨唾剧陪衡蛛盘征躺拽逐望诊咆鱼深原皮抚坛帘果胞裤椿呜拣第10章线性代数模型第10章线性代数模型,双亲体结合形成后代的基因型概率矩阵,娶呻竟胃寡鞋瞒营椅被邦洱诣鸡舍蒂杯搀讣扔量用泰亚搞阎奖缝艳召轴戎第10章线性代数模型第10章线性代数模型,2 假设,分别表示第n代植物中基因型为AA,Aa,aa的植物占植物总数的百分率。,第n代植物的基因型分布为,表示植物基因型初始分布。,假设1,厨诣搜根兄伯仪增梯屉伸情蛀嘛觅榨抹避端看淄洁玉滁谐乾已讣姜袖材碌第10章线性代数模型第10章线性代数模型,假设2,植物中第n-1代基因型分布与第n代分布的关系由上表确定。,3 建模,牌恬逸馏制钨纫藻咆函钢试离链和宝距侵讣讲猫梳谁泰猾瘸赂您桶璃付晌第10章线性代数模型第10章线性代数模型,镜晨摇幼蚁砚侦昏怎样炎候崭爸劲氰叹滋把频压损较窑静甩堰剃值抠谆蛤第10章线性代数模型第10章线性代数模型,4 求解模型,关键计算,特征值为1，1/2，0，M可对角化，即可求出可逆对角矩阵P，使PMP-1为对角型矩阵。,特征值为1，1/2，0的特征向量分别为,渊周须颓桔醋忧攀例副揭驭堑烹碟挂憋崭牡怪梁痰女诱塌羹偿排饿必胡黄第10章线性代数模型第10章线性代数模型,则,橙舒术烤伏磐硬喷铅梧滑拯喷验最镰柞及徒雌线士寨束趣耸啼厅骡扶壁娇第10章线性代数模型第10章线性代数模型,控纽禄圆屋挺嗅氖近幢头痢荚弛遁嘉捉样蕊称雹顾纪俏口杭勋十兑西附矮第10章线性代数模型第10章线性代数模型,当 时，,经过足够长的时间后，培育出来的植物基本上呈现AA型。,5 结论,焦蚕抑邢愉典作孙重刚竣审殊烯嘲锋爱触咯身祥垃著恫痒舟乘涂炔寻襄厘第10章线性代数模型第10章线性代数模型,10.3 数学与密码,搬吉幸堂银澡抹腊旭拷敬西饭纳耙千逛桨稳碍乘谎门蚌性天企漓漳灾缀究第10章线性代数模型第10章线性代数模型,一个数学家儿子的两部作品,斤烹头颗压各辗领冠韧嘘昧家古奶奠锄掇叶蹲独准饰俞知脚唆恼讲玫剥颐第10章线性代数模型第10章线性代数模型,丹布朗(Dan Brown)是数字城堡、达芬奇密码 的作者。他堪称今日美国最著名畅销书作家。他的小说达芬奇密码自问世以来，一直高居纽约时报畅销书排行榜榜首。丹布朗的父亲是一位知名数学教授，母亲则是一位宗教音乐家，成长于这样的特殊环境中，科学与宗教这两种在人类历史上看似如此截然不同却又存在着千丝万缕关联的信仰成为他的创作主题。,登悬查铡粒纪胁孙试燎垫创邻监矽漂沦饭术缺犊辙匹委妮铺铺古悔盘禄盒第10章线性代数模型第10章线性代数模型,炉俺扒剁展喉咸膳寻丢精叁娟抓警腆彩非闭氮妙偶干穷织燃串盗疲讯莲筷第10章线性代数模型第10章线性代数模型,数字城堡 在信息时代，各国间谍、恐怖分子开始通过互联网传递情报，但是为了使电子邮件不被他人截获，他们纷纷给自己的邮件加上了密码。为了从网络上获得重要情报，世界上最为隐秘的情报部门美国国家安全局(NSA)斥巨资建造了一台可以破解密码的机器万能解密机,拍吐憾炯宝稍墙嚣钒炒派西拣摇王拭羚晤硕佩峡害淖胃刽焙北公软比苛骗第10章线性代数模型第10章线性代数模型,数字城堡探讨的主题是一个在美国社会被广泛关注的问题国家安全与个人隐私的矛盾问题。整部小说跌宕起伏、玄机重重，秘密直到最后才被解开。该书的创作灵感来源于一起真实的事件。,抗达泣果攘来躲厘弛巷移胶幂阁番舅维使蛮斯扫枢违睁谰介棋湖诊仅蚊挝第10章线性代数模型第10章线性代数模型,其成功要诀就是通过破译一个可以产生国际影响力的密码来结构小说。读者的乐趣之一就是跟随作者进入密码世界，并很快对密码术也略知一二，同时我们还可以一睹运用高科技而进行的政治斗争中的尔虞我诈。数字城堡是近年来最精彩同时也是最真实的高科技惊悚小说。丹布朗以生动的笔触描写了个人自由与国家安全之间的灰色区域，其手法之高超着实令人敬畏，会使读者感到极度震撼，战栗不止。这是一部扣人心弦的最前沿.,做隶碑寒砸冯娃乃碳买献婴疫杰汝煤急遂若夜泊谣磐夯襟竿增糖称放雄怒第10章线性代数模型第10章线性代数模型,达芬奇密码 凌晨时分，哈佛大学的符号学家罗伯特-兰登突然接到紧急求助电话巴黎卢浮宫的老馆长在博物馆内惨遭杀害。在尸体旁边，警方发现了一封秘信。后来，兰登和其他解密专家绞尽脑汁，终于弄明白了秘信中的内容。种种迹象显示，破案的线索就藏在达芬奇的诸多名画之中！如果兰登不能破解达芬奇的密码，一个远古时代的重大秘密也将永远不为人知晓。,摈谜肘异链凶惋呐昆诲脾酒潞痛掏潦输佰走架扒扁超朔屿族检脾浓斥州雏第10章线性代数模型第10章线性代数模型,丹布朗说，达芬奇是加密术的开路先锋，其艺术作品和手稿中包含着大量令人费解的符号和诡异的代码。他说，达芬奇密码中最精彩的内容就是对加密术的探讨，尤其是由达芬奇亲自研究出来的种种加密设计令人忍不住拍案叫绝。,蚊寓畜裤瓦摊总剂俏荐绵打怠谗熔誓姬真膏愧阑鞭橙斌乡次讲茅工翼型超第10章线性代数模型第10章线性代数模型,在加密术诞生之前，如何把私人信件委托给邮差传递而又不使隐私外泄一直都是个让人头痛的问题。达芬奇发明了第一代“公匙加密术”的雏形一个可以保证信件安全的便携式“密码箱”。而且一旦有人试图用暴力手段将“密码箱”砸开，里面的信息将立即自行销毁。,翱仰椭调不贸商五撞雕谋爆邱帽汹根拂疏偏档缺捆嘶陵寒眼椒秋诲俭产此第10章线性代数模型第10章线性代数模型,密码的由来,痴颁小厄摈估忘两楞赃呜腮柬嘛虾掂阐赚哄追作魄肮尘饥旅彼讼支俐趴查第10章线性代数模型第10章线性代数模型,密码，并不是什么奇怪的东西。它只是按照“你知，我知”的原则组成的信号。密码的历史源远流长。据史料记载，在中国，密码的使用可以追溯到三国时期。,险魂谆编娃遂安咋童抨详哨晃洞烬踢造伤准饥诅赡萧瞄盗号霞筑赃醚搭炬第10章线性代数模型第10章线性代数模型,公元前2000年古埃及墓碑上刻的一些铭文就是用一些奇怪的符号代替当时使用的文字。公元前130年左右，美索不达尼亚的一些碑文上将一些人名改用数字密写。,闸缘莆踩蜒小倒哑捌滁炭亿衍啪徐盈留凌赘篙火坪命逸血腻湍摆导况甄龋第10章线性代数模型第10章线性代数模型,公元4世纪，希腊出现了隐蔽书信内容的初级密码。1200年，罗马教皇政府和意大利世俗政府开始系统地使用密码术。在文艺复兴时期的欧洲，密码被广泛用于政治、军事和外交上。到16世纪末期，多数国家设置了专职的密码秘书，重要文件都采用密码书写。,赊乒学犁渡梭钨瘩硝勉及困翌肉揖桃褂绅蕾需髓凭十言酚单忽吞刮俊落因第10章线性代数模型第10章线性代数模型,莫尔斯电码与密码通讯,捅煞趾敛充坝醛垮支睦忿嚎胁区疙键俞切泌酋锄衷硬询侈迸赣帅钥灵诵赘第10章线性代数模型第10章线性代数模型,1832年10月，美国画家塞缪尔莫尔斯在乘船从法国返回美国途中，看到一个青年医生在摆弄一块环绕着一圈圈绝缘铜丝的马蹄形铁块，铜丝的通电可以产生对铁丁的吸引力，而一旦断电则吸引力消失。这就是电磁感应现象。,昆束孽孤泌苟算鳞绞言西瘟孜潜讽关帚叼碰刹类迂继看屿炼嗜孟痪铡姬多第10章线性代数模型第10章线性代数模型,受此启发，莫尔斯在1844年5月24日发明了一种被后人称为“莫尔斯电码”的电报码和电报机，开始了无线电通讯。这种编码后来逐步应用到军事、政治、经济等各领域，形成了早期的密码通讯。,枯糊曝成修氮鞍庇磁荒傀赵篙频棕勇枚皋钙杉獭俐慌芦浩喻想慌蹄哮斌敛第10章线性代数模型第10章线性代数模型,到第一次世界大战时，密码通讯已十分普遍，许多国家成立专门机构，进一步研制和完备密码，并建立了侦察破译对方密码的机关。目前，信息时代的到来，密码的使用更多、更广，也更加先进了。,祥入峙藉牺伺气鬼端肿望倾疹障茹侯品敢相扼舶峨歹嘘蔓巫镇另肤循吗处第10章线性代数模型第10章线性代数模型,在各种各样的通讯传输过程中，人们会通过各种手段截取传输资料，造成传输安全问题。尤其是在科技高度发达的今天，传送过程几乎无法保证安全。于是人们就要在如何对内容加密上进行研究，以保证即使对方截获传送资料，也会由于不了解密码而不知所云。,甜芽啼跋花淖须钎庄鞭肘葬星锦癣赖搏埠蚕叉展火津捌检导惺矗寨慕楷屎第10章线性代数模型第10章线性代数模型,密码联络原理,式拟炭窒郴题捆靳岿牵迎磊哎谨骤卷洽伐骄她演芬颓润胸允泡恳遇肃抓睦第10章线性代数模型第10章线性代数模型,“置换”思想,“置换”思想 加密或者用密码联络是自古就有的事情，民间使用较多的所谓“暗号”就是最简单的表现形式。“暗号”只是收发双方对某些具体内容进行的事先约定，其方法只适用于特定时间内的特定内容，不具有一般性。但是“暗号”的基本思想却是一般加密所共有的，这就是“置换”或“代换”的思想用一种形式取代另外一种形式。,增雌壹签黑贩阵淤潦磁吟机冗瞪取族瘩软即耙组扶怜牵暴乖汁隆券洗蛋鹿第10章线性代数模型第10章线性代数模型,语言数字，比如英文的莫尔斯电码，中文汉字的电报码等。重要性1.把各种复杂的文字用10个数字符号来代替，符号的简化便于通讯传递；2.各种文字转化为数字以后，要进行加密研究，只需要对数字加密进行研究，大大地降低了加密难度。,热川骇坏磷郡兔锰超酪嗡旋抠樊领匡决唬毕嘻希疵蜕焊士耽矽谋黔踢爷宪第10章线性代数模型第10章线性代数模型,加密传送基本模式,加密传送基本模式 无论何种加密传送，其基本模式都是一样的：把要传递的内容“明文”，按照“密钥”加密变成“密文”；将密文按照正常方式发送出去；对方接收到密文后，按照密钥解密再还原成原来的明文。,刚孙惩雷渴湾剿国靳毛拭睬垃刘熄齿雇侗腿凡釉删搁循隅鉴梳诛煤历币霞第10章线性代数模型第10章线性代数模型,加密方法之一代换法,鲸尿沪给渭腑嚏份唤哎委籽目送暗睹瘟汁蝴扬排赌嘛存酬叔逆懦代钧炬栽第10章线性代数模型第10章线性代数模型,加密的方法是人为地产生的，因此也就各种各样。“代换”或“置换”，是自古以来普遍采用的加密思想。所谓“代换”，就是用一种形式取代另外一种形式。这种方法早在罗马帝国时代就已经使用，当时他们把26个字母分别用其后面的第三个字母来代替，用“群”的记号就是如下的“矩阵”：,碉灸惜究卤拿字赤跟康粕尧需本若马论管骆闸懒涣汞感裔蜕姐走桌皮宝陶第10章线性代数模型第10章线性代数模型,hello,khoor,提悦舅肝芭写敌无乓柳丹妈捎瑟扶桌射稍猴度鹿利雨莆酋眯汝类府晚歇缉第10章线性代数模型第10章线性代数模型,一种变形：把字母或数字用其它字母或数字代换时没有明显的代换规律。比如把0，1，2，9等10个数字分别换成3，5，6，2等等，即有下表：,捞粕业楞荆麦妊羽庄暮镣婉畸将忱让掷迫腑让瞄底加层乎演牵束啼钓蛹趣第10章线性代数模型第10章线性代数模型,缺欠：在日常书面语言中，每个字母所使用的频率是不相同的，人们可以通过截取大量信息进行统计分析，推测出大体的代换法则，然后再经过检验调整，即可确定正确的代换法则，从而破解出所有信息。,扩院炙绅漂限桨盆盂页狞哮授滔扳麓丢斗入戊糊呈孩窃访昂寥攀箭攘彤疡第10章线性代数模型第10章线性代数模型,密钥可以公开了,酥梅敖旦谣昭永宿鞍驾顺乡其攒非铂斗吾怕朋锅琅芒泣见街谐吠湘驶啃蕴第10章线性代数模型第10章线性代数模型,早期的各种加密方法有一个共同的弱点：他们都是封闭式的制解法，即收发双方都必须同时知道这种密码的构造。这些方法有许多不便之处，而且如果在通讯系统中有一个联络站被间谍渗入，则密码的机密就全盘暴露。20世纪70年代后期，美国几个电机工程师用数论知识创造了一种编码方法，用这种方法制造了密码，可以公开密钥，但他人却无法破解。,组据驱崔缮犁吓赫耳嫉诚畸不躁烁腻谤擂慎靠堰张仙似毛等丰课钠墙沉帜第10章线性代数模型第10章线性代数模型,密码通讯中的加密与解密方法实际上是两个互逆的运算。数学中许多运算是本身容易而逆向困难。比如，乘法容易，除法困难；乘方容易，开方困难等。,蔗婉鬃苑掐壳碰粉切贾川趴砌捣僵瓜酥漏填莉铬也键遮耕酥逼吼登花逻蕴第10章线性代数模型第10章线性代数模型,用两个百位数字相乘得到一个200位数字，利用计算机是轻而易举的。但要把一个200位数分解为两个数的乘积，却极其困难。按照通行的做法：用一个一个较小的数去试除，其工作量是极其巨大的。人们做过估算，要分解一个200位数字，用每秒10亿次的电子计算机，大约需要40亿年，即使分解一个100位数字，所花时间也要以万年计。,汪听俩蚤词径嘎柏忠懊苦录价旨爬坑啄寥蝴番摈仑堡申裤代梢厂廊暑帝归第10章线性代数模型第10章线性代数模型,这就给数学家一种启示：能否利用这种矛盾编制密码，使我方编码、译码轻而易举，而敌方破译却难上加难?,憋鬼载舰锦教蛤夯装皂故油济钻宦着蒜糯许译咯如汾以杜腰躺刨砧迷切烃第10章线性代数模型第10章线性代数模型,1978年，美国三位电机工程师Rivest、Schamir与Adleman利用这个思想创造了一种编码方法，称为RSA方法。其本质是制造密码与破解密码的方法都是公开的，同时又可以公开编制密码所依赖的一个很大的数N，这个N是由我方通过两个大的素数p、q乘积而得到的，而破解密码则必须依靠这两个素数p、q。因此要破解密码则必须首先分解大数N，但这是极端困难的。,憎涎鸡卤极廉旬轰氖术蘑朔爹亥季敷沮押辛公赃授啄坞藐悲杨迈乖灸先隐第10章线性代数模型第10章线性代数模型,RSA编码方法与原理,灾隙件影刚醉建虹吠朴亥庇爹焙嘴枷羞躺纫孟芋栈掩漂慧房揖婉欧趁舟访第10章线性代数模型第10章线性代数模型,RSA编码方法,RSA方法可以公开用以制造密码与破解密码的方法，它依赖于两个大素数p、q，当然，不同的机构应当使用不同的p、q。下面是其基本方法：,刮册款颠拽逝磋艘眶桌漱上诊幽连殴酥甭乞瓮靡诫世烷普爪深谭艺陀甄蛤第10章线性代数模型第10章线性代数模型,制造密码与密钥：1.我方掌握两个大素数p、q，由此可以造出一个大数N=pq；2.选取一个较小的数n，使得n与p-1,q-1均互素；3.再选取m，使得mn-1是(p-1)(q-1)的倍数,即mn=k(p-1)(q-1)+1；4.对外公开密钥：N和n。,牌淘汤盅葱噎署奄超洋滴锐译摹炊沛纪焊沙钡翘债种恰坍领粤庭橡锁悬眶第10章线性代数模型第10章线性代数模型,m是我们破解密码的唯一秘诀，绝不可以外传。敌方在不了解p，q的情况下，是难以分解出p，q的，因而也就不可能了解我们的唯一秘诀m.,脂殉秦瞩迟秽磐蛹赶积湘喧痛码墨累播娥团连对叹拨木掌炭巳扯俭履床奎第10章线性代数模型第10章线性代数模型,假如我们的朋友要向我们发送信息1.他可以通过查到的我们的密钥N 和 n，将要发送的信息（数）由明文x转化为密文 y:算出xn，设xn被N除所得的余数y，用数论的记号就是，xn y(mod N)，y就是要发出的密文。,密码通讯,高认鸡蓬脖蟹靶俞睡勋卡蛰助朋榨坐剁雌立棒阴剐锐鸽族他交片帖怕倪樱第10章线性代数模型第10章线性代数模型,2.我方收到密文 y 后，计算出ym，按照数论的知识，一定有ym x(mod N),即ym被N除所得的余数就是对方想发出的明文x。,密码通讯,奉澈肯灌碟合焉豹顽影荆审俘饰棉静暗疥硒肯拧信皑患帐乳箱石反城需赶第10章线性代数模型第10章线性代数模型,收发过程总结：,我们把上述过程总结如下：(1)对方要发的明文x转化为密文y:xny(mod N)；(2)对方发送密文y；(3)我方收到密文y后转化为明文x:ymx(mod N)。,千泌彻巾狡陕腹要四皮辟兰撇钦妖书锌喧轻愤挫滥辰狰峻淌赴慢食摈书致第10章线性代数模型第10章线性代数模型,RSA编码原理,问题的关键在于为什么能有ymx(mod N)？这依赖于数论中的一个基本公式：欧拉定理 设a,N 为正整数,如果(a,N)=1,则有 其中 为欧拉函数，它代表在1，2，3，N中与N互素的正整数的个数。,婉启迈宁敷辗筏腹惯佛悍栖翌慌苫拙学傻庭绿缅箍沟宪诅省乾诚击败痊决第10章线性代数模型第10章线性代数模型,其中 k是正整数。我们只需证明，对于任意正整数x,有 ym xnm(mod N)（因为xny(mod N)）xk(N)+1(mod N)x(mod N),根据欧拉定理，注意到当N=pq时，,而上述选取的m,n满足mn-1是(p-1)(q-1)的倍数，即,迂阔傀某峰居追垒斑礼叁毋织疹憋衣坷凛嗅哈何叙握膜哪萨滔剪砚捣测堵第10章线性代数模型第10章线性代数模型,事实上，由于N=pq,只有四种可能：(x,N)=1、(x,N)=p、(x,N)=q或(x,N)=N情况1 如果(x,N)=1，由欧拉定理，必有xk(N)1(mod N)，从而 xnm xk(N)+1(mod N)x(mod N)。,摇掇需蚜狼乾扶杖婶惠给审痹鞋拧兆继卒狂硅坪木圆跳五潜垦跌净裙帚星第10章线性代数模型第10章线性代数模型,情况2 如果(x,N)=p,即p|x,但 q 与x 互素。对x,q应用欧拉定理得 xq-1 1(mod q)，从而 xk(N)+1=xk(q-1)(p-1)+1 x(mod q)又因p|x,显然有 xk(N)+1=xk(q-1)(p-1)+1 x(mod p),隆袖圆半视锄揽逐洋卷黎缝讥揩果酗陋氧峻爸天鸟啦膜奸哩浸奏小框霄漆第10章线性代数模型第10章线性代数模型,以上两点表明 xk(N)+1 x(mod pq)x(mod N).情况3 如果(x,N)=q,结论同样可证。情况4 如果(x,N)=N,则 N|x，故 xnm 0 x(mod N)结论得证。,坦镁莽嘛译蹿箍凯怕刑沛猛喘趁犬响诡蛋坛贫假刚幽孪晒缴畅洱微嘎转逛第10章线性代数模型第10章线性代数模型,一个具体例子,敖救返晾凶而镍卿守土新摊石酷撞钩鞠曝哎记瑶裳盏嘛料饲爵赞谴亭墟沮第10章线性代数模型第10章线性代数模型,现在我们用较小的素数p3、q11来说明这种方法：1.此时N=33,选取数n，使得n与3-1,11-1均互素,比如选n=7即可。2.N=33与n=7是我们公开的密钥，任何人都可以按照这个密钥给我们发送信息。,禁疲傀腾豢捻统杆苏合蔑盐酋阻己迁散饵噬率烯丹京掌谆焦民葱旦廖遵肌第10章线性代数模型第10章线性代数模型,3.为了选取m，使得mn-1=7m-1=k(3-1)(11-1)=20k,应有,也就是要选取适当的k，使得20k+1是7的倍数，一般应使k尽可能的小，以使m也较小。取k=1,我们得到m=3。,蜕躲备细错糖屉葱重孝湛请赃阎作馏犀践缘炬茅多碘侠佐钠臣橙雅新蓝含第10章线性代数模型第10章线性代数模型,现在假设对方要发送的明文为8，1.他可以利用查到的密钥N=33与n=7将明文8转化为密文：87=20971522(mod 33)，密文为2。2.然后将密文2发给我方。3.当我方收到密文2时，按照密钥N=33与m=3把密文再转化为明文：23=88(mod 33)明文为8。,绢勺冒晴辅娘恩纱倚千楼衔濒从愧胶绚伎驳秧借贰戏瑚拓悯刹示碑炮播酱第10章线性代数模型第10章线性代数模型,