保障与安全数论ppt课件.ppt

《保障与安全数论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数论导引1素数和数的互素除数(因子)的概念：设z为所有全体整数构成的集合，若b≠0且使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。定义：若a•xmodn=1，则称a与x对于模n互为逆元。用Euclid算法求乘法逆元若a和n互素，则a在模n下有逆元。茨诀仟姑斋蝎祸赴很妨队龙淘乾踌猿堰羊柜放湖贩庶琳厘言男手杖筏默寒7保障与安全数论067保障与安全数论061算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式a＝

2、P1α1P2α2…Ptαt，这里P1>P2>P3>…>Pt是素数，其中αi>0最大公约数：若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有c∣d。注：1*.等价的定义形式是：gcd（a,b）＝max{k∣k∣a，k∣b}2*．若gcd（a,b）=1，称a与b是互素的。港悔沉云岭脖匠荤储搪致丝肮疹石耶苔保祟娄惺翠镣圭此招丽娥怔阮廓秃7保障与安全数论067保障与安全数论062模算术全体整数Z构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合

3、z为整数环。整数环z对除法运算不封闭。带余除法：a∈z>0，可找出两个唯一确定的整数q和r,使a=qm+r,0<=r

4、的一种等价关系。具有等价关系的三点基本性质：对任意整数a有a≡a（modm）如果a≡b(modm)则b≡a（modm）如果a≡b(modm）,b≡c（modm）则a≡c(modm)于是，全体整数集合z可按模m（m>1）分成一些两两不交的等价类。3*.整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。Z模12的标准剩余系为：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[1

5、0],[11]自反性对称性传递性帮雅杜魔丘现馈凉片睡胰集泄悸芹湿千鸵隙朽佩稍屯当脯咖肾必培泅舶命7保障与安全数论067保障与安全数论0644*.对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘（可交换的、可结合的、可分配的）而且，简化运算每个中间结果的模n运算，其作用与先进行全部运算，然后再简化模n运算是一样的。(1)[a(modm)±b(modm)]modm=(a±b)(modm)(2)[a(modm)b(modm)]modm=ab(modm)(3))[(ab)(modm)]+[(ac)(modm)]modm=(a(b+c))(modm)例1152mod

6、12=(3*3)mod12=9例2通过同余式演算证明560－1是56的倍数，223－1是47的倍数。解：注意53=125≡13(mod56)于是有56≡169≡1(mod56)对同余式的两边同时升到10次幂，即有56∣560-1。封卓击铝件痊翔览串邓官锣杯撰甚饶惯兢秒蛹圣诬荐虚焊霄挨拓咕籍绽糖7保障与安全数论067保障与安全数论065注意26=64≡-30(mod47),于是223=(26)3·25=(26·26)26·25≡900·(-30)·(32)mod(47)≡(7)(-30)·(32)(mod47)≡(-30)·(224)(mod47)≡(-30)·(36)(mod

7、47)≡(-1080)(mod47)≡1(mod47)于是有47∣223-1求117(mod13)，112=121≡4(mod13)，114≡42≡3(mod13)，117≡1143≡2(mod13)糠蝇磕芽厚媳佯精嫉遗淬境蚤斜苗纠搅恭贬矿捞拾褐文粘雁驴秽俞港凄研7保障与安全数论067保障与安全数论066定理：(消去率)对于ab≡ac（modm）来说，若(a,m)＝1则b≡c(modm)5*.一次同余方程ax≡b(modm)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有a