同余关系及其在计算机领域的应用 SBN978-988-99559-15 左图是2007实行的新的sBN标准,从10 位升到13位,为了讲课方便,我们仍然 用2007年以前的10位标准来讲述: 9789889955915> 假设ISBN号已经选择前9位x1x2,…x9,则这最后一位校验位 为:1x1+2x2+…+9X=X10(mod1) 比如:有一本书的前9位为0-619-06213,则其校验位由以下确定: (1.0+2.6+3.1+49+5.0+66+7.2+8.1+9.3)(mod11)=136(mod11) 4(mod11),故该书的校验码为4
同余关系及其在计算机领域的应用 左图是2007实行的新的ISBN标准，从10 位升到13位，为了讲课方便，我们仍然 用2007年以前的10位标准来讲述： 1 2 9 1 2 9 10 ISBN x ,x , x , x +2x 9x x (mod11) 4 , + + = 假设 号已经选择前9位 则这最后一位校验位 为：1 比如：有一本书的前9位为0-619-06213,则其校验位由以下确定： (1 0+2 6+3 1+4 9+5 0+6 6+7 2+8 1+9 3)(mod11)=136(mod11) (mod11)故该书的校验码为4
同余关系及其在计算机领域的应用 定理:通过校验位可以发现ISBN的单一错误 证明:假设xx2…x10变成y1y2…y10,其中yk=x(k≠i),y1≠x1 不妨设x1>y,必存在整数使得x1=y1+a。其中0<a≤10 因此 ly1+2y2+3y3+4y4+5ys+6y6+7y7+8yg+9y9+10y10 =1x1+2x2…(1-1)X1+iy1+(1+1)x1…+9x。+10x10 lx1+2x2…(1-1)x1+ix1+i(-=a)+(1+1)x:1…+9xg+10x10 ∑ⅸx1+i(a)=i(a)mod(1) 注意到此时∑ⅸ=0mod(1),这是因为 1x1+2x2+3x3+4x4+5x5+6X6+7x7+8x8+9X= Xo mod(11) 必有 1x1+2x2+3x3+4x4+5x5+6X6+7x7+8x8+9X。+10x10=11 X. mod(11)≡omod(11) 如果yy2…y1是正确的SBN号,则∑iy,=0mod(1),由此i(a)=0mod(1 则11ia,但是l≤is100<a≤10.不可能,故yy2y不是正确的SBN号
同余关系及其在计算机领域的应用 1 2 10 1 2 10 k k i i i i i i 1 2 3 4 5 6 7 8 9 10 1 2 i-1 i i 1 9 10 1 2 i ISBN x x x y y y y x k i y x x >y x y a 0 a 10 1y 2y 3y 4y 5y 6y 7y 8y 9y 10y 1x 2x (i 1)x iy (i 1)x 9x 10x 1x 2x (i 1)x + = = + + + + + + + + + + = + − + + + + + = + − 定理：通过校验位可以发现 的单一错误。 证明：假设 变成 ，其中 （ ）, 。 不妨设 ，必存在整数使得 。其中 。 因此 -1 i i 1 9 10 10 i i 1 10 i i 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 10 ix i(-a) (i 1)x 9x 10x ix i(-a) i(-a) mod(11) ix 0 mod(11) 1x 2x 3x 4x 5x 6x 7x 8x 9x x mod(11) 1x 2x 3x 4x 5x 6x 7x 8x 9x 10x 11x mod(11) 0 mod(1 + = = + + + + + + = + + + + + + + + + + + + + + + + + + 注意到此时 ，这是因为 则必有 10 1 2 10 i i 1 1 2 10 1) y y y ISBN iy 0 mod(11) i(-a) 0 mod(11) 11 ia 1 i 10 0 a 10, y y y ISBN = 如果 是正确的 号，则 ，由此 。 则 ，但是 ， 不可能，故 不是正确的 号
同余关系及其在计算机领域的应用 类似的可以证明如下的定理: 定理:通过校验位可以发现不等位互换的错误。 即是形如x…x…x1…x变成x1…x…x…X的错误
同余关系及其在计算机领域的应用 1 i j 10 1 j i 10 x x x x x x x x 类似的可以证明如下的定理： 定理：通过校验位可以发现不等位互换的错误。 即是形如 变成 的错误
同余关系及其在计算机领域的应用 同余的应用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
同余关系及其在计算机领域的应用 同余的应用2：验证信用卡的有效性 首先注意到不同的信用卡的标识码的长度和前缀都不一样，本节只介 绍国际上比较流行的Master卡，该卡标识码为16位，以51，52，53， 54或者55开头. 比如：5548 3742 7983 0696 在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
同余关系及其在计算机领域的应用 Master卡的标识码aa2…a,确定 Master卡的校验位,使用以下算法: 1.从右边第2位往左,将每隔一位乘以2 2.将第1步中的积各位相加 3.将第1步没有乘以2的各位相加 4.将第2步和第3步的结果相加 5.如果第4步得到的结果为S,则如果S=0(mod10 则该卡有效,否则无效
同余关系及其在计算机领域的应用 M a a a M 1 2 16 S aster aster 卡的标识码 ，确定 卡的校验位，使用以下算法： 1.从右边第2位往左，将每隔一位乘以2 2.将第1步中的积各位相加。 3.将第1步没有乘以2的各位相加 4.将第2步和第3步的结果相加 5.如果第4步得到的结果为S，则如果 0（mod10）， 则该卡有效，否则无效