数论与组合数学第五章 数论的应用

《数论与组合数学第五章 数论的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数论的应用在一个很长的时期里，数论被认为是很难有应用价值的。但是，二十世纪中后期，数论的应用，特别是在密码学等学科中的应用，改变了人们的看法，数论的研究也增加了新的内容。本章以下几节将要介绍数论在信息保密技术中的几个应用。第一节仿射加密现实社会中，充满了各种各样的信息，例如，军事情报，商业秘密，金融消息，计算机文件，私人通信等等。在很多情况下，人们希望在秘密的情况下保存或传送信息，这就导致了对信息加密的研究。对于那些一目了然的信息，我们称为“明文”。当我们要把某个信息传送给某些人（称之为“合法接收人”）时，是先把明文进行“加密”处理，这种经过加密处理的明文，我们称为“

2、密文”。密文不是随便甚麽人都可以看懂的。只有合法接收人，他们掌握了一定的方法，才能把它“翻译”成加密处理之前的明文。总的来说，关于信息加密的研究主要是两个方面：第一，研究把明文翻译成密文的方法，这个方法要尽可能的简单易行；第二，研究这种加密方法的保密性（安全性），即，除合法接收人外，其他人从密文了解到明文内容（全部或部分）的可能性。把明文翻译成密文的过程，称为加密过程，或加密；所用的方法（或公式），称为加密方法（或加密公式）。把密文翻译成明文的过程，称为解密过程，或解密；所用的方法（或公式），称为解密方法（或解密公式）。194为了能将数论用于明文的加密，首先需要建立明文与正

3、整数的对应关系。一个文件总是由文字和其他符号（标点符号，数字，特殊记号，等等）组成的。如果用汉语拼音书写汉字，那么，文件就可以用26个拉丁字母和一些符号来表达。假设所使用的字母和符号共有N个，如果把这些符号和N个正整数0，1，2，L，N-1建立一一对应的关系，那么，文字、符号、句子和文件就都和正整数建立了一一对应的关系。例如，假设使26个拉丁字母a，b，c，L，y，z与数字00，01，02，L，24，25建立了下表所示的一一对应关系：表1abcdefghijklm00010203040506070809101112nopqrstuvwxyz13141516171819202

4、122232425那么，与“woyaolai”（我要来）对应的数字就是2214240014110008。在实际应用中，一个文件所对应的整数是一个很大的数字，所以，人们往往要对大的正整数进行处理，使它们可以与较小的正整数列对应，从而容易进行加密运算。我们知道，对于给定的正整数k，任何正整数P都可以唯一地表示成P=pnkn+pn-1kn-1+L+p1k+p0，0£pi£k-1，0£i£n。这样，任何整数P就与整数列{pn,pn-1,L,p0}建立了一一对应的关系，对大整数P的加密就转化为对不超过k的整数pi（0£i£n）的加密。以下几节中，我们总用P表示明文，用E(P)或E表示

5、与P相应的密文。在这一节，我们主要介绍历史较长久的一类加密方法，即仿射加密方法。用W表示需要加密的所有明文P的集合，并且假定集合W的上界是A。用仿射加密方法对明文P加密的过程是这样的：(ⅰ)取大正整数M>A，以及正整数a，b，a¢，使得(a,M)=1，aa¢º1(modM)。(1)（注意：因此，明文P满足0£P

6、，由式(3)，式(2)和式(1)，我们得到P0ºa¢(E-b)ºa¢((aP+b)-b)ºaa¢PºP(modM)，由于0£P

7、tuvwxyzabc例如，使用例1中的加密方法，明文“jiudianzhong”（九点钟）被加密成“mlxgldqckrqj”。以下，为了叙述方便，我们用“®”表示数字与符号的对应关系，例如，“a®00”，“d®03”，等等。又用“Þ”表示明文和密文的对应关系，例如，“sÞa”“menÞphq”，等等。例2已知明文所使用的符号只是26个英文字母a，b，L，y，z，它们分别与整数00，01，L，24，25对应，又知道使用公式EºP+b(mod26)，0£E<26(4)对每个符号加密。已经知道明文字母e与密文字母u对应