公钥密码学的数学基础(第二版)

第1章整除 整除是数论中的基本概念.本章主要介绍与整除相关的一些基本概念及其性=质.这些基本概念如整除、因子、公因子、*小公倍数、分解因子等，早在中学时=期已被大家所熟悉.在这里我们将给出这些概念的严格的数学定义.通过掌握这=些概念的数学定义及相关性质，我们可以进一步解决许多初等数论里与整除相关=的问题.整除理论内容丰富，解决问题方法灵活.它不仅是数论、代数的基础，而=且在密码学中有很广泛的应用，如整数的素分解、Euclid算法求*大公因子等问=题在密码学中都有极其重要的应用. 1.1整除的概念 我们用集合Z表示全体整数组成的集合，N表示自然数的全体.下面给出整除的定义. 定义1.1设a，b∈Z，如果存在q∈Z，使得b=aq，那么，=就说b可被a整除，记作a|b，称b是a的倍数，a是b的因子(也=可称为约数、除数).否则就说b不能被a整除，或a不整除b，记作a.b. 由定义及乘法的运算规律，立即可得出整除的以下性质： 定理1.2设a，b，c∈Z，则 (1)a|b且; (2)a|b且对任意的有; (3)若m∈Z且，则; (4)a|b且; (5)若，则. 证明(1)由于a|b，根据整除的定义知存在q1，使.同样存在q2使得，从而即(2)由知，存在r，s使得.对任意的x，y∈Z有，故.反之显然. 性质(3)—(5)证明类似，读者可以自己补出证明. 显然±1，±b是b的因子，我们称其为b的显然因子，其他因子称为b的非显然因子，或真因子.由此我们可引出素元的定义. 定义1.3设整数.如果p除了显然因子±1，±p外没有其他的因子，那么p就称为素元(常称为素数)，若整数，且a除显然因子外还含有真因子，则称a为合数. 注一般情况下，素数我们只取正的. 下面我们介绍几个关于素数的定理. 定理1.4若a为合数，则a的*小真因子为素数. 证明由a为合数知a>2.设d为a的*小真因子.若d不为素数，则=存在d的真因子d′，使d′|d，由性质(1)知，与d为*小真因子矛盾.定理=得证. 定理1.5素数有无穷多个. 证明假设只有有限个素数，设为p1，p2， ，pk.考虑a=p1p2 pk+1，由=定理1.4知，整除a的*小真因子一定为素数，记为p.由于p为素数，因而p必=等于某个pi，所以p|a，p|p1p2 pk同时成立，从而p|1，这与p是素数矛盾.因此=定理得证. 将素数从小到大排列，假设pn表示第n个素数，π(x)表示不超过x的素数=个数.虽然我们无法知道pn的确切位置，但是，我们可以得到pn的弱上界估计下面定理仅描述了pn的一个弱上界估计与π(x)的一个弱下界估计.而对于π(x)=更为精确的估计，超出本书的讨论范围，有兴趣的读者可参考文献[23]. 定理1.6将全体素数按从小到大的顺序排列，则第n个素数pn与π(x)分别有以下结论： (1); (2). 证明(1)我们用归纳法来证明定理的**部分成立.当n=1时，命题 显然成立.假设对于时，命题成立.当n=k+1时，由定理1.4知，由归纳假设. 于是命题(1)得证. (2)对于任意的x.2，必存在唯一的整数n，使得，从而由**部分结论得定理得证. 初等数论还有一个*基本的结论：带余除法定理，它是整除的一般情形，也是Euclid算法的基础. 定理1.7设a，b是两个给定的整数且.那么一定存在唯一的一对整数q与r，满足，其中，r被称为b被a除后的*小非负余数.此外a|b的充要条件是r=0. 证明唯一性：若还有整数q′与r′满足. 则有及.由整除的性质立即可得，所以唯一性成立. 存在性：当a|b时，可取.当时，考虑集合，容易看出，集合T中必有正整数例如，取中必有一个*小正整数，记为. 我们来证明必有t0|a|，则. 显见，这和t0的*小性矛盾.取就满足要求.显然，a|b的充要条件是r=0.定理得证. 下面利用带余除法对整数进行分类.设a.2是给定的正整数，.对给定的j，被a除后余数等于j的全体整数是这些整数组成的集合记为Sa，j.集合满足以下两个性质： (1)中的任两个Sa，j两两不相交，即. (2)中所有子集的并等于Z，即. 这样按被a除后所得不同的*小非负余数，将全体整数分成了两两不相交的a个类.这种分类对于一些数学问题的处理会带来很大的方便. 例1.8对于任意整数x，x3被9除后所得的*小非负余数是0，1，8. 证明对于任意的整数x，存在使得.因此只需检验0至8之间的数即可. 例题得证. 例1.9设是给定的正整数.那么，任一正整数n必可唯一表示为，其中整数.这就是正整数n的a进制表示. 证明对正整数n必有唯一的，使.由带余除法知，必有唯一的q0，r0满足. 若k=0，则必有，所以结论成立.假设时结论成立. 那么当k=m+1时，上式中的q0必满足.由假设知，其中.因而有. 即结论对m+1也成立.定理得证. 例1.10将十进制整数27182写成十二进制的形式. 解进行下面的算法 得 1.2*大公因子与*小公倍数 *大公因子与*小公倍数是整除理论中两个*基本的概念. 本节主要讨论*大公因子与*小公倍数的概念及其性质. 定义1.11设a1，a2是两个整数.如果d|a1且，那么就=称d是a1和a2的公因子.一般地，设a1，a2， ，ak是k个整=数.如果，那么就称d是a1，a2， ，ak的公因子. 定义1.12设a1，a2是两个不全为零的整数，d是a1和a2的一个正公因=子，若对任意的d′|a1，d′|a2都有d′|d成立，则称d为a1和a2的*大公因子，记=作d=(a1，a2)或d=gcd(a1，a2).一般地，设a1，a2， ，ak是k个不全为零=的整数，d是a1，a2， ，ak的一个正公因子，若对任意的a1，a2， ，ak的公因=子d′，有d′|d，则称d为a1，a2， ，ak的*大公因子，记作(a1，a2， ，ak)或. 从定义1.12知，*大公因子即是公因子中*大的一个，*大公因子存在性的证明可参看文献[20].*大公因子有下面性质. 定理1.13 (1)对任意整数. (2)设m>0，则. (3)设a1，a2是两个不全为零的整数，则更一般地，有. (4). (5). 定理的结论比较显然，证明留给读者补出.定理提供了一种求解*大公因子的很简单、实用的方法. 例1.14对任意的整数m，有. 例1.15设a>2是奇数.证明 (1)一定存在正整数d.a.1，使得a|2d.1. (2)设d0是满足a|2d.1的*小正整数，那么其中h∈N)的充要条件是. (3)必有正整数d使. 证明(1)考虑以下a个数. 由及带余除法知，对每个，存在使得. 所以a个余数r0，r1， ，ra.1仅可能取个值.根据鸽巢原理知其中必有两 个余数相等，不妨设且ri=rk，因而有. 由(a，2)=1，推出.取就满足要求. (2)充分性是显然的，需证必要性.同样由带余除法定理得