剩余类与剩余系课件.ppt

1、对任意一个整数a，令:kkmaCa，则有如下定理：定理 1 设m是一个正整数，则（1）baCC 的充分必要条件是)(modmba；（2）对任意的整数ba,，要么baCC，要么baCC；（3）存在m个数两两对模m互不同余，且在任意1m个整数中，必有两个数对模m同余。证 （1）若baCC，因为abCCb，所以存在整数k，使得kmab，即)(modmba，必要性得证。下证充分性。设整数ba,满足关系)(modmba，则对集合aC中的元素任意c，存 在 整 数1k，使 得mkac1，由 已 知 条 件)(modmba，存在整数2k，使得mkba2，于是得 mkkbc)(21，所以有bCc，由c的任意性

2、知baCC；反方向的包含关系同理可证，故baCC。（2）任意的两个整数ba,，要么)(modmba，要么)(modmba 。如果)(modmba，由（1）知baCC；如果)(mod mba ，用反证法。假设 baCC，即存在整数c，使得aCc且bCc，于是存在整数21,kk，使得mkac1及mkbc2，由这两个等式很容易得 mkkba)(12，即)(modmba，与条件)(mod mba 矛盾。因此baCC。（3）对于模m而言，集合1,2,1,0m中任意两个元素互不同余，所以由集合1210,mCCCC是m个两两互不相交的集合，且任意一个整数，必属于其中一个集合，即它们构成整数集合的一个划分。任

3、意1m个整数，必有两个数属于1210,mCCCC中的同一个集合，由（1）知它们对模m同余。定义 2 每一个这样的集合aC称为模m的同余类或剩余类，一个剩余类中的任意一个元素叫做该类中的代表元或剩余。一组数saaa,21称为是模m的完全剩余系，如果对于任意的整数a有且仅有一个整数)1(siai与a在同一个剩余类中。由定理 1（3）知，模m的完全剩余系是存在的，且ms 以及给定的m个整数是模m的完全剩余系的充分必要条件是它们两两对模m不同余。事实上，一组模m的完全剩余系就是在模m的每个同余类中取定一个数作为代表所构成的一组 数。而 对 于 模m的 一 个 完 全 剩 余 系saaa,21，maaa

4、CCC,21就是模m的m个两两不同的剩余类，且有 miaiC1 完全剩余系的形式是多种多样的，学会在不同的问题中选取合适的完全剩余系对于解决问题很有帮助。一般地，称1,2,1,0m为模m的最小非负完全剩余系；m,2,1为模m的最小正完全剩余系；0,1,),2(),1(mm为模m的最大非正完全剩余系；1,2,),1(,mm为模m的最大负完全剩余系；当m为奇数时，2/)1(,1,0,1,2/)1(mm为模m的绝对值最小完全剩余系，当m为 偶 数 时，2/)2(,1,0,1,2/mm或2/,1,0,1,2/)2(mm 为模m的绝对值最小完全剩余系。例1 设 正 整 数9m，对 任 意 整 数a，集

5、合:9kkaCa为模m的剩余类，16,14,12,10,8,6,4,2,0是模9的一个完全剩余系，8,7,6,5,4,3,2,1,0为模9的最小非负完全剩余系；9,8,7,6,5,4,3,2,1为模9的最小正完全剩余系；0,1,2,3,4,5,6,7,8为模9的最大非正完全剩余系；1,2,3,4,5,6,7,8,9为模9的最大负完全剩余系；4,3,2,1,0,1,2,3,4为模9的绝对值最小完全剩余系。例 2 设21,aa是模m的同一个剩余类中的任意两个整数，则有),(),(21mama。证 设rCa 1，rCa 2。则 存 在 整 数21,kk，使 得mkra11，mkra22，于 是 有)

6、,(),(1rmma，),(),(2rmma，所以),(),(21mama。例 3（染色问题）设ma,是正整数，mama0,1),(，记集合1,3,2,1mM。现对集合M中的每个数i涂上黑色或白色，要满足以下条件：（1）imi和要涂上同一种颜色；（2）当ai 时，|iai和要涂上同一种颜色。证明：所有的数一定都涂上同一种颜色。证 我们的想法是把要涂色的集合M扩充到全体整数，除已知两条外另外满足：（3）属于模m的同一个剩余类中的数涂上相同的颜色；（4）a和0要涂上同一种颜色。这样就可以对全体整数涂色，这样的涂色应该满足如下性质：1 对任意的整数j，jj和一定涂相同的颜色。因为对于任意的整数j，必

7、存在整数i，使得)(mod,0mijmi，由（3）知ij和同色；而)(modmimij，所以由（3）知imj 和同色，从而由（1）和（4）知jj和同色。2 对任意的整数j，ajj和同色，从而属于模a的同一个剩余类中的数涂上相同的颜色。因为对于任意的整数j，必存在整数i，使得)(mod,0mijmi，由（3）知ij和同色，而由（2）知|iai和同色，进而由1|iaai 和同色推出aij和同色；由条件（3）知，属于模m的同一个剩余 类 中 的 数 同 色，因 为)(modmij，所 以)(mod()(majai，因此aiaj 和，从而ajj和同色。由1和2知，对于任意的整数j，tasmjj和同色，

8、其中ts和为任意的整数。由条件1),(ma知存在整数11,ts，使得111 atms，所以1jj和同色，即所有整数同色。例 4 设maaa,21，mbbb,21分别是模m的两组完全剩余系。证明：当m是偶数时，mmbababa,2211一定不是模m的完全剩余系。证 根据完全剩余系的定义可以看出，对于模m的任意两组完全剩余系，它们各元素之和对模m是同余的，且这和同余于 mmmmmmmm|2)(mod2/|2)(mod02/)1(110，而)(mod0)1(2211mmmbababamm，因 为 当m是 偶 数 时，)(mod02/mm，所 以mmbababa,2211一定不是模m的完全剩余系。简化

9、剩余、欧拉定理及其应用内容回顾：1 同余的定义及基本性质2 完全剩余简化剩余系定义 1 设m是正整数，一个模m的剩余类叫做简化剩余类，如果该类中存在一个与m互素的剩余。在模m的所有不同简化剩余类中，从每个类中任取一个数组成的整数的集合叫做是模m的简化剩余系。同上一样可以得到最小正简化剩余系、最大负简化剩余系、绝对值最小简化剩余系等概念。如果令)(m为集合1,2,1,0m中与m互素的所有整数的个数，则)(m为模m简化剩余系中元素的个数，称之为欧拉函数。当m为素数p时，很容易看出此时有 1)(pp。从定义可以看出，模m的一组完全剩余系中所有和m互素的整数组成模m的一组简化剩余系。此外，任意给定)(

10、m个和m互素的整数，只要两两对模m不同余，它们就组成模m的一组简化剩余系。例 1 设3m，证明：（1）模m的任意一组简化剩余系的所有元素之和对模m必同余于零；（2）模m的最小正简化剩余系的各数之和等于2/)(mm。证 首先证明（2）成立。设saaa,21是所有小于2/m且和m互素的正整数，则有 simammammii,2,1,1,2/）且（，并且对于任意一个正整数a，如果它满足 1,2/）且（mamam，则有1,2/0）且（mammam，因此一定存在一个正整数siai1,，使得iaam，即iama，所以 1121,amamamaaasss 构成模m的最小正简化剩余系，所以得sm2)(，且 2/

11、)(121mmmsamamaaass。而（1）由（2）很容易得到。定理 1 设m是正整数，a是满足1),(ma的整数，b是任意整数。若x遍历模m的一个完全剩余系，则bax 也遍历模m的一个完全剩余系；若x遍历模m的一个简化剩余系，则ax也遍历模m的一个简化剩余系。定理 1 表明：只要1),(ma，我们就可以找到这样的模m的完全剩余系和简化剩余系，它们的元素都是a的倍数；而当1),(ma时，这是一定不可能的。如：75,15,05是模8 的完全剩余系，75,55,35,15是模 8 的简化剩余系。但是72,12,02不 是 模8的 完 全 剩 余 系，72,52,32,12也不是模 8 的简化剩余

12、系。对于不同模之间的剩余系，我们有如下结论：定理 2 设nm,是两个互素的正整数，如果yx,分别遍历模nm,的完全（简化）剩余系，则mynx 遍历模mn的完全（简化）剩余系。例2 分别用模4和模5的完全剩余系和简化剩余系来表示模20的完全剩余系和简化剩余系。解 取模 4 的一组完全剩余系为 0,1,2,3，取模 5 的一组完全剩余系为 0,1,2,3,4，则由定理 3 得模 20 的一组完全剩余系为0,4,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31。取模 4 的一组简化剩余系为 1,3，取模 5 的一组简化剩余系为 1,2,3,4，则由

13、定理 3 得模 20 的一组简化剩余系为9,13,17,21,19,23,27,31。由定理2，我们很容易得到如下关于欧拉函数的一个性质定理。定理 3 若正整数nm,满足1),(nm，则有)()()(nmmn。有了定理3，下面我们来研究欧拉函数的计算 定理 4 设p为素数，a为正整数，则有)11()(1pppppaaaa，进一步，若正整数n有标准因数分解式 kakanpaappppn212|1 则有)11()11)(11()(21kpppnn。证 模ap的最小非负完全剩余系为.1,1)1(,)1(,12,1,1,1,011aaappppppppp 共有ap个整数，其中与模ap不互素的整数为)1

14、(,1,01apppp 共1ap个整数，因此模ap的简化剩余系的元素个数为1aapp，即)11()(1pppppaaaa。结合定理 3，我们就可以得到任何一个具有标准因数分解式的正整数n的欧拉函数的计算公式)11()11)(11()(21kpppnn。由定理 3 和定理 4 还可以推出 定理 5 对于任意正整数m有 mddmd0,|)(。证 方法一：若apm，p为素数，则有)(11(1)()()()(2100,|aadmdpppppppd mppaa11 若1),(,npnpma，且对于正整数n，有 nddnd0,|)(为了简单，下面求和符号的因数指的都是正因数，且dpk|指的是dpdpkk|

15、,|1且，则有)()(|,|,|,|,|,|0,|2dddpmddpmddpmddpmddmda ndndandnddpdppdd|2|)()()()(ndadppp|2)()()()(1 mnpa 因此由归纳法容易得到结论成立。方法二：对正整数集合,2,1m按其和m的最大公因数分类，1,),(|mndmnnSd，则有 mddSm|,2,1 由整除的性质1),(),(dmdndmn/1,1),(,|dmkdmkdknnSd 即集合dS的元素个数为)/(|dmSd 由 集 合dS的 定 义 可 知，对 于 任 意 两 个 整 数mdmddd|,|,2121且，21ddSS，所以 mdmdmddd

16、dmSmm|)(|)/(|,2,1|。例 3 设正整数84n，试计算)(n且按照定理 5 对集合n,2,1进行分类。解 因为732842n，所以由定理 4 得 24622)7/11)(3/11)(2/11(84)84(84 的正因数有 1，2，3，4，6，7，12，14，21，28，42，84，按照定理 6，集合n,2,1的分类为 83,79,73,71,67,65,61,59,55,53,47,43,41,37,31,29,25,23,19,17,13,11,5,11S 82,74,62,58,50,46,38,34,26,22,10,22S 81,75,69,57,51,45,39,33,

17、27,15,9,33S 80,76,68,64,52,44,40,32,20,16,8,44S 78,66,54,30,18,66S 77,49,35,77S 72,60,48,36,24,1212S 70,1414S 63,2121S 56,2828S 4242S 8484S 例 4 设1m，nm|。证明：)()(mmnn，等号当且nm 时成立。证 因为nm|，所以对于任意整数a，若1),(ma，必有1),(na。在m个相邻整数中，与m不互素的数有)(mm个，这些数同样与n不互素。所以把集合,2,1n分成mn个集合，每个集合由m个连续的整数构成，则每个集合中与n不互素的元素个数大于等于)(m

18、m，所以有)()()(mmmmmnnn，等号成立当且仅当nm。欧拉定理在上一节中，我们已经了解到简化剩余系满足如下的一些性质：当3m时，模m的任意一组简化剩余系的所有元素之和对模m必同余于零；模m的最小正简化剩余系的各数之和等于2/)(mm。同时，我们很关心任意一组简化剩余系的乘积情况。定理 1（欧拉定理）设m为大于 1 的正整数，若整数a满足1,ma，则有)(mod1)(mam。对于欧拉定理，特别地，当m是素数p时，有如下形式的费马小定理 定理 2（费马小定理）对任意的整数a和任意的素数p，有)(mod paap，进一步，若1,pa，则)(mod11pap。称上述定理为费马小定理是为了和 1

19、995 年由英国的数学家安德鲁怀尔斯攻克的著名的费马大定理区别开来。例 1 设m是一个正整数，a是满足1),(ma的整数，则存在整数 a，ma 1，使得)(mod1maa 证 方法一（存在性证明）因为1),(ma，根据上一节定理1，若)(21,maaa是模m的最小非负简化剩余系，则)(21,maaaaaa也是模m的一组简化剩余系，而 1 是模m的最小非负简化剩余系中的一个元素，因此，由简化剩余系的定义知，则存在正整数 a，)(1,1mkmaak，使得)(mod1maa。方法二（构造性证明）因为1),(ma，所以由欧拉定理可知，)(mod1)(1)(maaamm 运用上一节定理 4，我们可以计算

20、出欧拉函数)(m的值，从而可以计算出maammod1)(。方法三（构造性证明）因为1),(ma，运用广义的欧几里得算法，我们可以找到整数ts和，使得 1),(matmsa 因此，由同余的定义可以得到：整数msamod满足)(mod1maa，ma 1。由例 1，我们可以给出一个在同余理论中非常重要的概念：乘法逆元素。定义 1 设1m是一个正整数，a是满足1),(ma的整数，则称使得)(mod1maa，ma 1成立的正整数 a为a关于模m的乘法逆元素，记为ma mod1。由乘法逆元素的定义可以看出来，对于那些满足条件1),(ma的整数a的乘法逆元素是不存在的。对于任何大于1 的正整数m，1mod1

21、1m。通过例1，我们可以得到关于乘法逆元素的两种计算方法：算法 1：（1）根据算术基本定理求出m的标准因数分解式；（2）计算)(m；（3）计算ma mod1mammod1)(；算法 2：（1）利用 1.2 广义欧几里德算法计算整数s和t，使得1),(matmsa；（2）msmamodmod1 Knuth 已经证明，对于算法 1，首先要对模m进行因数分解，对 于 大 整 数，这 是 一 件 很 费 时 的 事，平 均 约 需 要2log5.12m次乘法；利用算法 2 求模m的乘法逆元素，平均约需47.1)(log843.02m次除法。因此对于大整数，求乘法逆元素以算法 2 为最佳。有了乘法逆元素

22、的概念，我们对求模一个整数的负整数幂，即若0n，则 mmamannmod)mod(mod1。对于素数模，我们还有下面一个很有趣的结论。定理 3 设p是素数，121,paaa是模p的任意一组简化剩余系，则我们有)(mod1121paaap 特别地，当121,paaa是模p的最小非负简化剩余系时有)(mod1)!1(pp 例 2 设p是奇素数，证明)(mod)1()2(312/)1(222ppp。例 3 设110,paaa和 110,pbbb是模p的两组完全剩余系，p是奇素数。证明：111100,ppbababa一定不是模p的完全剩余系。例 4 证明：如果p是素数，并且)4(mod3p，那么)(m

23、od1!21pp。RSA公开密钥密码系统 RSA公开密钥密码系统是由R.Rivest、A.Shamir和L.Adleman于1977年提出的。RSA的 取名就是来自于这三位发明者的姓的第一个字母。后来，他们在1982年创办了以RSA命名的公司RSA Data Security Inc.和RSA实验室，该公司和实验室在公开密钥密码系统的研究和商业应用推广方面具有举足轻重的地位。1 密钥的产生（1）每位使用者 A，任意选择两个大素数Ap和Aq，并求出其乘积AAAqpn；（2）任意选择一个整数Ae，使得与)1)(1()(AAAqpn互素，并求出Ae关于模)(An的乘法逆元素Ad，即)(mod1AAA

24、ned；（3）将),(AAne公布为其公开密钥，并将Ad秘密保存为其秘密密钥，作为解密使用，为了增强安全性，将Ap和Aq毁去不用。2 RSA系统 设 B 欲秘密传送明文)0(nmm给 A，则 B 首先在公开档案库中找到 A 的公开密钥),(AAne（或者直接由 A 提供），然后执行加密运算得到密文 AeAnmmEcAmod)(B 将密文c传送给 A。A 收到密文c后，利用其秘密密钥执行解密运算得到明文 AdAnccDmAmod)(在下面证明中，在不至于引起混淆的情况下，我们省去qpne,的角标A。事实上，因为)(mod1ned，所以，存在整数k，使得)(1nked 若1),(nm，则由欧拉定理

25、知 mnnmmnmnmknnkedmod)mod(modmod)()(1 于是 mnmnmnccDnkdedAmodmodmod)()(1 若m和n不互素，则必有pnm),(或qnm),(，假设pnm),(，则有1),/(npmi。由上面的证明知iedipmnpmmod。另一方面，)(mod)mod()1(1)1)(1(1qpqpppppkqqpked 即)(|ppqed，且)(|ppped 于是得)(|pppqned，即pnpedmod。所以 mnppmnnpnpmnmiiiedediedmodmod)modmod)/(mod 当m和n不互素时，使用广义欧几里得算法能够很快计算出p和q的值，

26、因而容易求出)(n，进而可以算出解密密钥d，因此此时系统很不安全。但是当p和q均为很大的素数时，在 0 到n之 间 的 任 选 一 数 而 与n不 互 素 的 概 率 为pqqpnqp，当p和q相近时，其概率约等于n2。若n为512 位，则其概率约为2552，因此一般均假设m和n互素。例 1 取两个素数11p，13q，p和q的乘积为143 pqn，120)1)(1()(qpn，再选取一个与120)(n互素的数7e，对于这个e值，计算出它关于模)(n的 乘 法 逆 元 素103d，即 整 数d满 足)(1),(mod1ndned。),(en 和d分别为“公开密钥”和“秘密密钥。”设想甲需要发送明

27、文85m给乙，他已经得到了乙的公开密钥)7,143(),(en，于是算出加密值123143mod85mod7nmce发送给乙，乙收到加密的信息123c后，利用自己的解密密钥进行解密运算得到明文85143mod123mod103ncmd 于是乙得到甲发给他的真实信息85m。3 模n的选择1p和q必须为强素数 定义 1 一个素数p称为是强素数，如果满足如下条件（1）存 在 两 个 大 素 数1p及2p，使 得)1(|1pp且)1(|2pp；（2）存 在 四 个 大 素 数211,rsr及2s，使 得)1(|),1(|),1(|221111prpspr及)1(|22ps。只有两个强素数的乘积所构成的

28、n，其因数分解才是较难的数学问题。若pqn，且1p的所有素因数均很小，即 tiaiipp11 其中，ip为第i个素数，1ia为整数，且所有Api，A为已知的小正整数。（事实上，对于一个素数而言，1ia的情况是很少出现的。）则存在一种1p因子分解法，使得我们可以轻易地分解因子n。1p因子分解法 设pqn，且p满足上式，则我们可令,21kppp为所有小于A的素数，任意选取估计值1a，令 kiaipr1 则 有rp|1，由 费 马 小 定 理 知)(mod12pr，即)12(|rp。令 nxrmod2 当1x时，则选取 3 代替 2，直到1x为止。当1x时，有pnx),1(，于是可以将n因子分解得到

29、p和q。例 2 118829n，首先令A为 14，1a，则 30030131175321kiaipr 103935mod2nxr 331)118829,103934(),1(nx 所以359331n。若1p含有一大的素因子，利用此方法，r就会大到使得计算nrmod2的值无法在有效时间内不可能办到。对于1p有类似的结论。2 p和q的差必须很大因为有恒等式 nqpqp2222 所以，当p和q的差很小时，2qpt近似为n，从1nt开始计算nt 2的值，直到它为一个完全平方数为止。则由方程组 ntqptqp222 可以计算得到nttp2，nttq2 例 3 118829n。估计从3451nt开始，nt

30、 2的值为214196，所以 1423452qpqp 可以计算得到359p，331q。3 p-1和q-1的最大公因子应该很小在进行这种分析之前，我们首先给出一个关于欧拉函数的性质的讨论。性质 设ba,为正整数，1),(bad，ban，则有)()()()(dbadn 且在n不变的情况下，d越小，)(n越大。在 RSA 系统中，如果1p和1q的最大公因子很大，攻击者可能在不需要因数分解n的情况下获得明文。设攻击者知道了密 文1c，则可 以对 该密 文进 行迭 代攻 击，即有nmnccieeiimodmod11，如果存在某个整数i，使得 1)(modnei，则必有1mci，即经过i次迭代后获得明文，攻击成功。由欧拉函数的性质和欧拉定理可知，当)1,1()1()1()1,1()1)(1(qpqpqpqpi 时，等式1)(modnei成立。如果)1,1(qp的值越小，则i的值就越大，当i的值足够大 时，能 够 抵 挡 迭 代 攻 击。因 此 最 理 想 的 情 况 是2)1,1(qp。思考题 （1）如何计算ab mod n（2）如何判定一个给定的整数是素数？（3）如何找到足够大的素数p和q?