数学欣赏2006D

nullnull主讲：张文俊nullIn this ChapterIn this Chapter名人语录 名人语录 数学的生命力的源泉在于它的概念和结论尽管极为抽象，但却像我们所坚信的那样，它们是从现实中来的，并且在其他科学中，在技术中，在全部生活实践中都有广泛的应用；这一点对于了解数学是最重要的。 ——A.D.ALEKSANDROV 《数学，它的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 、方法和意义》名人语录 名人语录 从十分清楚明白、根本无法怀疑的东西、最简单最容易认识的对象开始，一点一点逐步上升到对复杂对象的认识。 ——R. DESCARTES名人语录 名人语录 “数学是什么？大致说来，数学和其它科学一样，它的发展基于两个原因：（一）奇怪的现象；（二）数学结果的应用。” “结果把奥妙变为常识，复杂变为简单，数学便成为科学的有力而不可缺少的工具。 ” ——陈省身 第一节 数学归纳法原理 第一节 数学归纳法原理 zwj@szu.edu.cn数学归纳法原理 数学归纳法原理 万丈高楼平地起万丈高楼平地起 南北朝时，一位印度法师将一部名为《百喻经》的寓言式图书带到中国并翻译成汉语。其中有一篇题为《三重楼寓》的寓言……数学归纳法及其理论基础数学归纳法及其理论基础null 理论基础 自然数公理：设S是自然数集合N的子集，即SN，如果S 满足 （1）       1∈S； （2）       若n∈S，则n+1∈S； 那么，必有S=N. null 【数学归纳法原理】 设Pn是与自然数相关的一种命题，如果 （1）当n=1时命题P1是成立的； （2）假设当n=k时命题Pk是成立的，可以证明当n=k+1时命题Pk+1也是成立的。 那么命题Pn对所有自然数n都是成立的。null【数学归纳法原理变形1】 设Pn是与自然数相关的一种命题，如果 当n = k0时命题Pk0是成立的； 假设当n = k (k ≥ k0) 时命题Pk是成立的，可以证明当n=k+1时命题Pk+1也是成立的。 那么命题Pn对所有自然数n ≥ k0都是成立的。 例如：n 边形内角和问题。 null【数学归纳法原理变形2】 设Pn是与自然数相关的一种命题，如果 当n =1时命题P1是成立的； 假设当1 ≤ n ≤ k时命题Pn是成立的，可以证明当n=k+1时命题Pk+1也是成立的。 那么命题Pn对所有自然数n都是成立的 null例如：有两堆棋子，数目相等。两人玩耍，每人每次可以从其中一堆中取任意多颗棋子，但不能同时从两堆中提取，规定取得最后一颗棋子者为胜。求证：后取者可以必胜。null【数学归纳法原理变形3】 设Pn是与自然数相关的一种命题，如果 当n = 1，2，…, k0时命题Pn是成立的； 假设当n = k时命题Pk是成立的，可以证明当n=k+k0时命题Pk+k0也是成立的。 那么命题Pn对所有自然数n都是成立的。null例如:求证：方程x+2y=n的非负整数解的组数为 ； 一般地，方程x+my=n的非负整数解的组数为 其中 表示商 的整数部分。 null【数学归纳法原理变形4——跷跷板归纳法 】 设An ，Bn是与自然数相关的两种命题，如果 当n = 1时命题A1是成立的； 假设当n = k时命题Ak是成立的，可以证明命题Bk也是成立的； 假设当n = k时命题Bk是成立的，可以证明当n=k+1时命题Ak+1也是成立的。 那么命题An ，Bn对所有自然数n都是成立的。 null例如: 假设数列{an}满足： a2n = 3n2, a2n-1=3n(n-1)+1, n=1,2,3, …。Sm=a1+a2+…+am. 求证：null【数学归纳法原理变形5——逆向归纳法 】 设Pn是与自然数相关的一种命题，如果 存在一个递增的无限自然数序列{nk},使命题 Pnk成立； 假设当n = m时命题Pm是成立的，可以证明当n=m-1>0时命题Pm-1也是成立的。 那么命题Pn对所有自然数n都是成立的. 例如: 算术平均与几何平均不等式 归纳法在几何上的一个应用 ——两色定理的证明归纳法在几何上的一个应用 ——两色定理的证明null两色定理：在一张纸上随意画一些直线，这些直线把这张纸分割成若干个区域。把这假想成一个世界地图，要对其进行图色以便区分各个不同的国家，只需要两种颜色（比如红色与黄色）就够了。 null两色定理的证明： 我们考虑画出这幅地图所用直线的条数： （1）如果只用一条直线，那么只能分出两个国家，两种颜色足够了； （2）现在假设对所有用n条直线画出的地图，都只需要两种颜色，我们考虑一个由n+1条直线画出的地图M。 null对于这个地图，从中抹去一条直线，此时剩下的地图是由n条直线画出的，自然可以由两种颜色着色。再把刚刚抹去的直线添上去，这条直线把整张纸分成两部分，刚才图好颜色的国家中，有些也给分开了，有些则没有被分开。null在这条直线分成的两部分中，一半保留原来的着色，另一半中各个国家的颜色全部换掉：红换黄，黄换红。于是，这个由n+1条直线画出的地图M也只需要两种颜色就能区分各个国家了。根据数学归纳法原理，任何由若干条直线画出的地图都只需要两种颜色就够了。 归纳法的妙用 ——数不尽的骆驼归纳法的妙用 ——数不尽的骆驼null下面的故事是巧妙运用归纳法的一个例子。 一位画家招收三个弟子，为了测试徒弟们对绘画奥妙掌握的程度，画家出了一道题目：要求三个弟子各自用最经济的笔墨，在给定大小的纸上画出最多的骆驼。null 第一个弟子为了多画一些，他把骆驼画得很小、很密，纸上显示出密密麻麻的一群骆驼； 第二个弟子为了节省笔墨，他只画骆驼头，从纸上可以看到许多骆驼； 第三个弟子在纸上用笔勾画出两座山峰，再从山谷中走出一只骆驼，后面还有一只骆驼只露出半截身子。null 三张画稿交上去，第三个弟子的画因构思巧妙、笔墨经济、以少含多而被认定为最佳作品。原因 何在？ 归纳法的不当使用 ——秃子世界归纳法的不当使用 ——秃子世界null 只长1根头发的人是秃子。 如果长n根头发的人是秃子，那么长n+1根头发的人也是秃子。 于是根据数学归纳法原理，不论长多少根头发的人都是秃子，这个世界是个秃子世界。 第二节 抽屉原理与聚会认友 第二节 抽屉原理与聚会认友 zwj@szu.edu.cn抽屉原理与聚会认友抽屉原理与聚会认友二桃杀三士 二桃杀三士 晏婴（？~前500年）是古代历史上齐国富有经验的政治家，他足智多谋，在有些事情的处理上用到了一些数学原理。在《晏子春秋》里记载了一个叫“二桃杀三士”的故事：null齐景公有三名勇士，田开疆、公孙接和古治子。这三名勇士都力大无比，英勇善战，为齐景公立下过许多功劳。但是他们也因此而目空一切，甚至连齐国宰相晏婴都不放在眼里。晏婴对此极为恼火，便劝齐景公杀掉他们。齐景公对晏婴言听计从，但却心存疑虑，担心万一武力制服不了他们反被他们联合反抗。晏婴于是献计于齐景公：以齐景公的名义奖赏三名勇士两个桃子，请他们自己评功，按功劳大小分吃桃子。 null三名勇士都认为自己功劳很大，应该单独吃一个桃子。于是，公孙接讲了自己的打虎功，拿了一只桃子；田开疆讲了自己的杀敌功，也拿了一只桃子。两人正要吃桃时，古治子讲了自己更大的功劳。田开疆、公孙接觉得古治子功劳确实大过自己而羞愧不已，拔剑自刎。古治子见了，后悔不迭。心想：“如果放弃桃子隐瞒功劳，则有失勇士威严；但若争功请赏羞辱同伴，又有损哥们义气。如今两位兄弟都为此绝命，我独自活着还有何意义？”于是，古治子一声长叹，拔剑结束了自己的生命。null晏婴采用借“桃”杀人的办法轻易地除去了心腹之患。这里，他利用了数学中的一个简单而有用的原理：抽屉原理。 抽屉原理的简单形式抽屉原理的简单形式null所谓抽屉原理，又叫鸽笼原理，它是组合数学中一个最基本的原理，可以用来解决许多涉及存在性的组合问题。其基本内容为： 把m个物体放到n个抽屉中，如果物体数比抽屉数多（即m>n），那么，必然有至少一个抽屉里放入两个或两个以上的物体。null这个原理有两个简单变形： 把多于m×n个的物体放到n个抽屉中，那么，必然有至少一个抽屉里放入m+1个或m+1个以上的物体。 把无穷多个的物体放到n个抽屉中，那么，必然有至少一个抽屉里放入无穷多个物体。null抽屉原理I 把m个物体放到n个抽屉中，那么，必然有（至少）一个抽屉里放入至少k个物体。这里null例如： 在任意给定的3个整数中，必定有2个整数，其和是2 的倍数（其算术平均值还是整数）。 在任意给定的5个整数中，必定有3个整数，其和是3 的倍数（其算术平均值还是整数）。 在坐标平面上任意取5个整点（纵横坐标都是整数），则必定存在其中两个整点，其连线的中点仍是整点。 null 在n维空间中，任意取2n+1个整点（纵横坐标都是整数），则必定存在其中两个整点，其连线的中点仍是整点。 在3×4的长方形中，任意放置6个点，必有两个点的距离不超过 。 6) 边长为1的正方形中任意放入9个点，在以这些点为顶点的各个三角形中，必有一个三角形，它的面积不大于1/8。聚会认友聚会认友null我们可能经常会遇到这样的情况：在一桌酒席上，十来个本来不相识的人坐在一起，经过不太久的交流，马上会有人找到自己的“知音”，他们可能是校友、同行、同乡、同姓、同年龄、同属相或者是朋友的朋友、朋友的同乡、同乡的朋友等。这种情况几乎在每次酒席中都会发生，以致让人感觉到这世界真是太小。难道这都是巧合吗？ 聚会的朋友聚会的朋友null我们经常会参加各种聚会。如果我说：在任何一种聚会中，一定有两个人，他们在场的朋友数是一样多的。你一定会很吃惊。但是，我们可以用抽屉原理来说明，这是千真万确的。 六个人的聚会六个人的聚会null在任何6个人中，一定可以找到3个人，他们或者互相都认识，或者互相都不认识。 抽屉原理的推广形式抽屉原理的推广形式null抽屉原理II 把m个物体放到n个抽屉中，那么，必然有（至少）一个抽屉里放入至多 个物体。 null例如 设 为区间(0,1)内的任意n+1个实数，那么，其中必有两个数，其差的绝对值小于1/n. 第三节 七桥问题与图论 第三节 七桥问题与图论 背景背景七桥问题 七桥问题 18世纪，位于现立陶宛内的哥尼斯堡镇，有一条河流叫普雷格尔河。河中有两个相邻的小岛，岛与岛、岛与陆地之间建有七座桥 null 问题：一个人能否一次无重复地走遍所有的七座桥，最后回到出发点？这就是著名的“七桥问题”。 1736年，一位小学教师写信给当时的著名数学家欧拉（Euler），请教对七桥问题的解答。欧拉用数学方法对七桥问题进行了深入的研究。欧拉的解答 ——七桥问题的数学模型欧拉的解答 ——七桥问题的数学模型nullnull 欧拉研究后发现： (1) 这不是一个代数问题（代数问题研究量的大小、关系）; (2) 这也不是一个平面几何问题（平面几何问题研究角度的大小、线段的曲直、长短等）。null在这里，陆地、岛屿的大小、形状均是无关紧要的，桥梁的曲直、长短也对问题的解答没有影响；该问题的解仅依赖于陆地、岛屿、桥梁等的具体个数及其相互位置关系。 因此，可以将一块陆地或一个岛屿看作一个“点”，将一座桥梁看作一条连接两点的“线”。（如下页图）nullnull按照欧拉的思想，七桥问题转化为：一笔画问题 在右图中，能否从图上某一点开始，笔不离纸、不重复地画出整个图形？null这一重要思想，成为近代数学之一——图论的基础，同时也是近代数学——拓扑学（位置几何学）的奠基。 图的基本概念 与基本结论图的基本概念 与基本结论null1. 图 — 点（称为顶点）和将它们之间的某些点两两连接起来的线（称为边）的集合，叫做图。 一个图记为G（Graph）; 一条边记为e （edge） ，边的集合记为E（Edge）； 一个顶点记为v （vertex） ，顶点的集合记为V（Vertex）。nullnull2. 顶点的次数：顶点v处引出的边的条数叫做顶点v的次数，记为 d（v）。 结论 次数总和等于边数总和的2倍(偶数)。nullnull3. 奇点、偶点——顶点次数为奇（偶）数的顶点叫奇（偶）点。 结论：奇点数必为偶数。 偶点：边线有进有出，进出对应； 奇点：有一条只进不出或只出不进的边线。null4. 连通图——任意两点之间都有链相连的图叫做连通图。 null图的基本概念(3)一笔画定理 —— 七桥问题的解决 一笔画定理 —— 七桥问题的解决 null1. 一笔画定理 定理（一笔画） 一个图G可以一笔画的充要条件是：G是连通的，并且奇点的个数为0或2。 当奇点数为2时，一个奇点为起点，另一个奇点为终点；当奇点个数为0时，任取一个顶点，它是起点，也是终点。null证明思想： (1) 必要性 若G能一笔画，则G必是连通的，而且只有在起点处的边才可能只出不进（奇点），也只有在终点处的边才有可能只进不出（奇点）。故G是连通的，且没有奇点或只有两个奇点。null(2) 充分性 若G是连通的，并且奇点的个数为0或2。我们通过对顶点的总次数 n=2k(偶数)用数学归纳法来证明G可以一笔画。null n=2时，G是一条有两个顶点（端点）的线段，或是一条有一个顶点的圆圈。因此可以一笔画。 null 假设n=2k时结论成立，考虑n=2(k+1)=2k+2的情况。 null如果该图没有奇点，则从中任意去掉一条边. 设此边的两端点分别为v0, v1, 此时，该图仍然是连通的（因为其任一顶点处至少有两条边通过，去掉一条后，还至少有一条边与其它顶点相连），而且，其顶点的次数总和为2k,其中奇点数最多为2。此时剩余图可以从v0出发到 v1结束一笔画，再从v1到 v0, 即可将原图一笔画。 null 如果该图有两个奇点v0, v1, 去掉v0出发的一条边。 null若d(v0)>1, 则剩余图是一个奇点个数为0或2、顶点次数总和为2k的连通图,因而可以一笔画，从而原图也可以一笔画。 若d(v0)=1，则剩余图是一个奇点个数为0或2、顶点次数总和为2k的非连通图，除去v0点后，该图是连通图，可以一笔画，因此原图也可以一笔画。null 2. 应用于七桥问题 七桥问题是一个具有4个奇点的图，因此，不可以一笔画。  思考：如果再增加一座桥，不论修在什么地方，八桥问题总是可以一笔画的。后来那里又增加一桥，而现在只剩下三座桥了。 图的简单应用图的简单应用null  图的简单应用 现实生活中很多问题可以通过图论的原理来解决。把具体问题转化为图论问题的基本思路是：把各种事物抽象为点（顶点），把事物之间具有某种关系抽象为有一条边相连。 null例 9名数学家相遇，其中任意3人中至少有2人有共同语言，每位数学家最多会讲3种语言。证明，至少有3位数学家可以用同一种语言对话。 null证明 把每一位数学家看成一个顶点vi，i =1，2，3,…, 9. 如果某两位数学家能用某种语言对话，则认为其相应的顶点之间有一条边（相邻），并涂相应颜色。 问题是：证明至少存在3个顶点vi, vj, vk, 使边 同色。null  考虑v1，分两种情况： （1）v1与v2, v3 ,…,v9均相邻 由于每位数学家最多会讲3种语言，故8条边 至多有三种不同的颜色，因此由抽屉原则，至少有三条边是同色的，与此三边相关的四位数学家是有共同语言的。null （2）存在 j >1, 使v1与 vj不相邻 此时，不妨设 j =2，由于任意3人中至少有2人有共同语言（相邻），故另外七位数学家v3, v4 ,…,v9中的每一位必与v1, v2 之一相邻，从而其中至少有四位与v1或v2 相邻，不妨设v3, v4 ,v5,v6与v1相邻。null  于是四个边 至多有三种不同的颜色，因此由抽屉原则，至少有两条边是同色的，与此二边相关的三位数学家是有共同语言的。  注：若将9位数学家改为8位数学家，结论不真。 null例 20名网球运动员进行14场单打比赛，每人至少上场一次。求证：必有6场比赛，其参赛的12名运动员各不相同。 null证明 把每一位运动员看成一个顶点vi，i =1，2，3,…, 20. 如果某两位运动员进行一场比赛，则认为其相应的顶点之间有一条边，如此构成一个图G。根据条件知，边数为14，且 问题是：证明至少有六条边的12个顶点是互不相同的。 null 事实上，如果某个球员参加比赛超过一场，我们只保留其一场记录，而将其它场次去掉。用图的语言就是：在每个顶点vi处抹去d(vi)-1条边（一条边可以同时在其两端点抹去），则抹去的边数不超过 条，故剩下的图G1至少有14-8=6条边。G1中每个顶点的次数不超过1，因此6场比赛参赛者各不相同。 第四节 数学与密码 第四节 数学与密码 一个数学家儿子 的两部作品一个数学家儿子 的两部作品null丹·布朗(Dan Brown)是《数字城堡》、 《达·芬奇密码》 的作者。他堪称今日美国最著名畅销书作家。他的小说《达·芬奇密码》自问世以来，一直高居《纽约时报》畅销书排行榜榜首。 丹·布朗的父亲是一位知名数学教授，母亲则是一位宗教音乐家，成长于这样的特殊环境中，科学与宗教这两种在人类历史上看似如此截然不同却又存在着千丝万缕关联的信仰成为他的创作主题。nullnull《数字城堡》 在信息时代，各国间谍、恐怖分子开始通过互联网传递情报，但是为了使电子邮件不被他人截获，他们纷纷给自己的邮件加上了密码。为了从网络上获得重要情报，世界上最为隐秘的情报部门——美国国家安全局(NSA)斥巨资建造了一台可以破解密码的机器——万能解密机……null《数字城堡》探讨的主题是一个在美国社会被广泛关注的问题——国家安全与个人隐私的矛盾问题。整部小说跌宕起伏、玄机重重，秘密直到最后才被解开。 该书的创作灵感来源于一起真实的事件。null其成功要诀就是通过破译一个可以产生国际影响力的密码来结构小说。读者的乐趣之一就是跟随作者进入密码世界，并很快对密码术也略知一二，同时我们还可以一睹运用高科技而进行的政治斗争中的尔虞我诈。《数字城堡》是近年来最精彩同时也是最真实的高科技惊悚小说。丹·布朗以生动的笔触描写了个人自由与国家安全之间的灰色区域，其手法之高超着实令人敬畏，会使读者感到极度震撼，战栗不止。这是一部扣人心弦的最前沿...null《达芬奇密码》 凌晨时分，哈佛大学的符号学家罗伯特-兰登突然接到紧急求助电话———巴黎卢浮宫的老馆长在博物馆内惨遭杀害。在尸体旁边，警方发现了一封秘信。后来，兰登和其他解密专家绞尽脑汁，终于弄明白了秘信中的内容。种种迹象显示，破案的线索就藏在达芬奇的诸多名画之中！如果兰登不能破解达芬奇的密码，一个远古时代的重大秘密也将永远不为人知晓。……null丹·布朗说，达芬奇是加密术的开路先锋，其艺术作品和手稿中包含着大量令人费解的符号和诡异的代码。他说，《达芬奇密码》中最精彩的内容就是对加密术的探讨，尤其是由达芬奇亲自研究出来的种种加密设计令人忍不住拍案叫绝。null在加密术诞生之前，如何把私人信件委托给邮差传递而又不使隐私外泄一直都是个让人头痛的问题。达芬奇发明了第一代“公匙加密术”的雏形———一个可以保证信件安全的便携式“密码箱”。而且一旦有人试图用暴力手段将“密码箱”砸开，里面的信息将立即自行销毁。密码的由来密码的由来null密码，并不是什么奇怪的东西。它只是按照“你知，我知”的原则组成的信号。 密码的历史源远流长。据史料记载，在中国，密码的使用可以追溯到三国时期。 null公元前2000年古埃及墓碑上刻的一些铭文就是用一些奇怪的符号代替当时使用的文字。 公元前130年左右，美索不达尼亚的一些碑文上将一些人名改用数字密写。 null公元4世纪，希腊出现了隐蔽书信内容的初级密码。 1200年，罗马教皇政府和意大利世俗政府开始系统地使用密码术。 在文艺复兴时期的欧洲，密码被广泛用于政治、军事和外交上。 到16世纪末期，多数国家设置了专职的密码秘书，重要文件都采用密码书写。 莫尔斯电码与密码通讯 莫尔斯电码与密码通讯 null 1832年10月，美国画家塞缪尔·莫尔斯在乘船从法国返回美国途中，看到一个青年医生在摆弄一块环绕着一圈圈绝缘铜丝的马蹄形铁块，铜丝的通电可以产生对铁丁的吸引力，而一旦断电则吸引力消失。这就是电磁感应现象。null受此启发，莫尔斯在1844年5月24日发明了一种被后人称为“莫尔斯电码”的电报码和电报机，开始了无线电通讯。 这种编码后来逐步应用到军事、政治、经济等各领域，形成了早期的密码通讯。null到第一次世界大战时，密码通讯已十分普遍，许多国家成立专门机构，进一步研制和完备密码，并建立了侦察破译对方密码的机关。目前，信息时代的到来，密码的使用更多、更广，也更加先进了。 null在各种各样的通讯传输过程中，人们会通过各种手段截取传输资料，造成传输安全问题。尤其是在科技高度发达的今天，传送过程几乎无法保证安全。于是人们就要在如何对内容加密上进行研究，以保证即使对方截获传送资料，也会由于不了解密码而不知所云。 密码联络原理 密码联络原理 “置换” 思想“置换” 思想“置换” 思想 加密或者用密码联络是自古就有的事情，民间使用较多的所谓“暗号”就是最简单的表现形式。“暗号”只是收发双方对某些具体内容进行的事先约定，其方法只适用于特定时间内的特定内容，不具有一般性。但是“暗号”的基本思想却是一般加密所共有的，这就是“置换”或“代换”的思想——用一种形式取代另外一种形式。 null语言→数字，比如英文的莫尔斯电码，中文汉字的电报码等。 重要性 1. 把各种复杂的文字用10个数字符号来代替，符号的简化便于通讯传递； 2. 各种文字转化为数字以后，要进行加密研究，只需要对数字加密进行研究，大大地降低了加密难度。 加密传送基本模式加密传送基本模式加密传送基本模式 无论何种加密传送，其基本模式都是一样的： 把要传递的内容——“明文”，按照“密钥”加密变成“密文”； 将密文按照正常方式发送出去； 对方接收到密文后，按照密钥解密再还原成原来的明文。 加密方法之一 ——代换法加密方法之一 ——代换法null加密的方法是人为地产生的，因此也就各种各样。“代换”或“置换”，是自古以来普遍采用的加密思想。所谓“代换”，就是用一种形式取代另外一种形式。这种方法早在罗马帝国时代就已经使用，当时他们把26个字母分别用其后面的第三个字母来代替，用“群”的记号就是如下的“矩阵”： nullhello khoor null一种变形：把字母或数字用其它字母或数字代换时没有明显的代换规律。比如把0，1，2，…，9等10个数字分别换成3， 5，6，2等等，即有下表： null缺欠： 在日常书面语言中，每个字母所使用的频率是不相同的，人们可以通过截取大量信息进行统计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，推测出大体的代换法则，然后再经过检验调整，即可确定正确的代换法则，从而破解出所有信息。 密钥可以公开了密钥可以公开了null早期的各种加密方法有一个共同的弱点：他们都是封闭式的制解法，即收发双方都必须同时知道这种密码的构造。 这些方法有许多不便之处，而且如果在通讯系统中有一个联络站被间谍渗入，则密码的机密就全盘暴露。 20世纪70年代后期，美国几个电机工程师用数论知识创造了一种编码方法，用这种方法制造了密码，可以公开密钥，但他人却无法破解。 null密码通讯中的加密与解密方法实际上是两个互逆的运算。 数学中许多运算是本身容易而逆向困难。 比如，乘法容易，除法困难；乘方容易，开方困难等。null用两个百位数字相乘得到一个200位数字，利用计算机是轻而易举的。 但要把一个200位数分解为两个数的乘积，却极其困难。 按照通行的做法：用一个一个较小的数去试除，其工作量是极其巨大的。 人们做过估算，要分解一个200位数字，用每秒10亿次的电子计算机，大约需要40亿年，即使分解一个100位数字，所花时间也要以万年计。null这就给数学家一种启示： 能否利用这种矛盾编制密码，使我方编码、译码轻而易举，而敌方破译却难上加难? null1978年，美国三位电机工程师Rivest、Schamir与Adleman利用这个思想创造了一种编码方法，称为RSA方法。其本质是制造密码与破解密码的方法都是公开的，同时又可以公开编制密码所依赖的一个很大的数N，这个N是由我方通过两个大的素数p、q乘积而得到的，而破解密码则必须依靠这两个素数p、q。因此要破解密码则必须首先分解大数N，但这是极端困难的。 RSA编码方法与原理RSA编码方法与原理RSA编码方法 RSA编码方法 RSA方法可以公开用以制造密码与破解密码的方法，它依赖于两个大素数p、q，当然，不同的机构应当使用不同的p、q。下面是其基本方法： null制造密码与密钥： 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。nullm是我们破解密码的唯一秘诀，绝不可以外传。 敌方在不了解p，q的情况下，是难以分解出p，q的，因而也就不可能了解我们的唯一秘诀m. 密码通讯 密码通讯 假如我们的朋友要向我们发送信息 1. 他可以通过查到的我们的密钥N 和 n，将要发送的信息（数）由明文x转化为密文 y : 算出xn，设xn被N除所得的余数y，用数论的记号就是，xn ≡ y(mod N)，y就是要发出的密文。密码通讯 密码通讯 2. 我方收到密文 y 后，计算出ym， 按照数论的知识，一定有 ym ≡ x(mod N), 即ym被N除所得的余数就是对方想发出的明文x。 收发过程总结：收发过程总结：我们把上述过程总结如下： (1)对方要发的明文x转化为密文y: xn≡y(mod N)； (2) 对方发送密文y； (3) 我方收到密文y后转化为明文x: ym≡x(mod N)。 RSA编码原理 RSA编码原理 问题的关键在于为什么能有ym≡x(mod N)？这依赖于数论中的一个基本公式： 欧拉定理 设a, N 为正整数, 如果 (a, N) =1, 则有 其中 为欧拉函数，它代表在1，2，3，……，N中与N互素的正整数的个数。 null其中 k是正整数。我们只需证明，对于任意正整数x , 有 ym ≡ xnm(mod N) （因为xn≡y(mod N) ） ≡ xk(N)+1(mod N) ≡ x (mod N) 根据欧拉定理，注意到当N = pq时，而上述选取的m, n满足mn -1是(p-1)(q-1)的倍数，即null事实上，由于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)。 null情况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)null 以上两点表明 xk(N)+1 ≡ x (mod pq) ≡ x (mod N). 情况3 如果(x, N)=q, 结论同样可证。 情况4 如果(x, N) = N, 则 N|x， 故 xnm ≡0 ≡x (mod N) 结论得证。 一个具体例子一个具体例子null 现在我们用较小的素数p＝3、q＝11来说明这种方法： 1. 此时N=33, 选取数n，使得n与3-1, 11-1均互素, 比如选n=7即可。 2. N=33与n=7是我们公开的密钥，任何人都可以按照这个密钥给我们发送信息。 null3. 为了选取m，使得 mn-1=7m-1=k(3-1)(11-1)=20k, 应有 也就是要选取适当的k，使得20k+1是7的倍数，一般应使k尽可能的小，以使m也较小。取k=1, 我们得到m=3。 null现在假设对方要发送的明文为8， 1. 他可以利用查到的密钥N=33与n=7将明文8转化为密文： 87=2097152≡2(mod 33)， 密文为2。 2. 然后将密文2发给我方。 3. 当我方收到密文2时，按照密钥N=33与m=3把密文再转化为明文： 23=8≡8(mod 33) 明文为8。null