同余关系在计算机领域的应用

同余关系及其在计算机领域的应用同余的应用1：国际图书标准(ISBN编码)ISBN是internationalstandardofbooknumber的缩写，即国际标准图书编号。ISBN是国际通用的图书或独立的出版物(除定期出版的期刊)代码。出版社可以通过ISBN清晰地辨认所有非期刊书籍。一个ISBN只有一个或一份相应的出版物与之对应。新版本如果在原来旧版的基础上没有内容上太大的变动，在出版时也不会得到新的ISBN号码。当平装本改为精装本出版时，原来相应的ISBN号码也应当收回。国际标准图书编号问世后，很快得到推广，主要是因为它对出版商、书商的工作有很大的益处，体现在:国际标准书号是机读的编码，从图书的生产到发行、销售始终如一，对图书的发行系统起了很大的作用;它的引入使图书的定购、库存控制、账目和输出过程等任何图书业的分支程序都简化了;国际标准书号也对图书馆和文献中心的订购、采选、编目和流通程序都有促进作用;ISBN系统的引入也服务于书目信息的流动和使用，而且为一个国家的图书生产提供经济的书目控制;ISBN对图书市场更有效率，它能确定国际上出版的任何图书及其出版社。在书业中习惯称ISBN为库藏码(StockNumber)，就是因为其被普遍应用于书库管理。同余关系及其在计算机领域的应用10位数ISBN的结构现行的ISBN由10位数字组成，这10位数字由4组数字组成，中间用“-”相连，每组数字都有不同的含义。第一组号码是地区号，又叫组号，最短的只有一位数字，最长的达五位数字，大体上兼顾文种、国别和地区。0、1代表英语，使用这两个代码的国家有:澳大利亚、加拿大、爱尔兰、新西兰、波多黎各、南非、英国、美国、津巴布韦等;2代表法语，法国、卢森堡以及比利时、加拿大和瑞士的法语区使用该代码;3代表德语，德国、奥地利和瑞士德语区使用该代码;4是日本出版物的代码;5是俄罗斯出版物的代码;7是中国出版物使用的代码。第二组:出版社代码。由国家或地区的ISBN中心设置并分给各个出版社。第三组:书序码。该出版物代码，是出版者分配给每一个出版物的编号。第四组:计算机校验码。校验码是ISBN号的最后一位数值，它能够校验出ISBN号是否正确。校验码只能是1位数，当为10时，记为罗马数字X。同余关系及其在计算机领域的应用左图是2007实行的新的ISBN标准，从10位升到13位，为了讲课方便，我们仍然用2007年以前的10位标准来讲述：12912910ISBNx,x,x,x+2x9xx(mod11)4,假设号已经选择前9位则这最后一位校验位为：1比如：有一本书的前9位为0-619-06213,则其校验位由以下确定：(10+26+31+49+50+66+72+81+93)(mod11)=136(mod11)(mod11)故该书的校验码为4同余关系及其在计算机领域的应用12101210kkiiiiii1234567891012i-1ii191012iISBNxxxyyyyxkiyxxyxya0a101y2y3y4y5y6y7y8y9y10y1x2x(i1)xiy(i1)x9x10x1x2x(i1)x定理：通过校验位可以发现的单一错误。证明：假设变成，其中（）,。不妨设，必存在整数使得。其中。因此-1ii191010ii110ii1123456789101234567891010ixi(-a)(i1)x9x10xixi(-a)i(-a)mod(11)ix0mod(11)1x2x3x4x5x6x7x8x9xxmod(11)1x2x3x4x5x6x7x8x9x10x11xmod(11)0mod(1注意到此时，这是因为则必有101210ii112101)yyyISBNiy0mod(11)i(-a)0mod(11)11ia1i100a10,yyyISBN如果是正确的号，则，由此。则，但是，不可能，故不是正确的号同余关系及其在计算机领域的应用1ij101ji10xxxxxxxx类似的可以证明如下的定理：定理：通过校验位可以发现不等位互换的错误。即是形如变成的错误。同余关系及其在计算机领域的应用同余的应用2：验证信用卡的有效性首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介绍国际上比较流行的Master卡，该卡标识码为16位，以51，52，53，54或者55开头.比如：5548374279830696在Master卡中，具备如下性质：1.如果第2位为1，则第2到3位表示银行号。2.如果第2位为2，则第2到4位表示银行号。3.如果第2位为3，则第2到5位表示银行号。4.如果第2位为其他值，则第2到6位表示银行号。银行号后面直到第15位为持卡人账号，最后一位为校验位。比如刚才的例子中，第2位为5，则银行号为54837，持卡人账号为427983069同余关系及其在计算机领域的应用1216MaaaMSasteraster卡的标识码，确定卡的校验位，使用以下算法：1.从右边第2位往左，将每隔一位乘以22.将第1步中的积各位相加。3.将第1步没有乘以2的各位相加4.将第2步和第3步的结果相加5.如果第4步得到的结果为S，则如果0（mod10），则该卡有效，否则无效同余关系及其在计算机领域的应用:5546199723355004mod例假设信用卡的标志码为，检查该卡的有效性。解：1.02=052=1032=622=492=1812=242=852=102.0+1+6+4+9+2+8+1=313.5+6+9+7+3+5+0+4=394.31+39=705.700（10）所以这张卡的标志码有效。