密码学数学基础第一讲 整数的因子分解

《密码学数学基础第一讲 整数的因子分解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密码学数学基础初等数论近似代数因子分解群同余式求解环、域二次剩余有限域参考书《信息安全数学基础》，李继国等著，武汉大学出版社。课后答疑时间：周二下午16：00－18：00地点：主楼1111总成绩＝课堂表现(30%)＋考试成绩(70%)考勤15%+作业15%第一讲整数的因子分解教师：李艳俊本讲内容一、带余除法和整除法二、整数的表示三、最大公因子与辗转相除法四、整数的唯一分解定理五、素数六、多项式的整除一、带余除法和整除法整数集合Z{0,1,2,}整数与整数通过相加、相减、相乘仍然是整数，但是通过相除的结果

2、则不一定是整数。定理1.1设a、b是两个整数，其中b>0，则存在唯一的整数q和r使得aqbr,0rb。其中的除法称为带余除法，或欧几里德除法。q称为a被b除得的不完全商，r称为余数。aq记为[x]为x的整数部分，并且xx[]1xb若式子aqbr中，r=0，则称b整除a，记为b

3、a。b称为a的真因子，a是b的倍数。整除的性质b0,c0(1)c

4、b，b

5、ac

6、a；(2)b

7、abc

8、ac；(3)对任意整数x，y有:ca

9、,c

10、bc

11、(axby)二、整数的表示十进制表示32

12、41084101100108t2n的a进制表示nratra2rar10其中，a是大于1的整数，n是任一整数。nqar,0ra,nqar00000qqar,0ra,(qarar)0111110qqar,0ra,1222t1t2qqar,0ra,(qar)arararii1i1i1t1t1t210t2i2,3,ratra2rar10存在0qa,记作rqt1tt1例用二进制表示618。例用十六进

13、制表示618。十六进制二进制十六进制二进制0000081000100019100120010A101030011B101140100C110050101D110160110E111070111F1111十六进制和二进制之间的换算表三、最大公因子与辗转相除法定理1.2设a，b，c为三个正整数，且a=bq+c,其中q为整数，则(a,b)=(b,c)。求(a,b)的方法：辗转相除法。a=bqr，0

14、b

15、，111b=rqr，0

16、1k+1k+1kr=rqr，0

17、b

18、>r>r>，所以只包含有限12个等式。例:求（524，134）。定理1.3对任意两个正整数a,b，存在整数x和y，使得（a,b）=xa+yb。推论1.1设d是a和b的任一公因子，则d

19、(a,b)。例:求解(793,2769)，和x,y，使得(793,2769)=793x+2769y。27693793390390(3)7932769793239013137793(2

20、)27693903013(793,2769)13x7,y2定义1.2设设a1,a2,an是n个整数。如果整数d是它们中每一个数的因数，那么就称d为公因数。所有公因数中最大的一个正整数为最大公因数。a,a,a定理1.4设12n是n个整数，令(,aa)d,(,da)d,,(d,a)d121132n2nn1则(,aa,a)d，因而存在整数uu,,u，使得12nn112nauauau(,aa,a)1122nn12n例:计算4389，5313，399的最大公因子。四、整数

21、的唯一分解定理定理1.5设p为素数，a，b为整数，若p

22、ab，则p

23、a或p

24、b。定理1.6（唯一分解定理）任一不为1的正整数n均可以唯一地表示为np1p2ps标准分解式12s其中p1p2ps，i为自然数，i1,2,,s。例1写出51480的标准分解式。51480=225740=2212870=236435=2351287=2353429=23532143=233251113。最小公倍数定义1.3设a1,a2,an是n个整数。如果整数m是它们中每一个数的倍数

25、，那么就称m为公倍数。所有公倍数中最小的一个正整数为最小公倍数。a,a,a定理1.7设12n是n个非零整数，令[,aa]mma,[,]m,,[m,a]m121132n2nn1则[,aa,a]m。12nn1ab定理1.8设a，b为两个正整数，则[,]ab。(,)ab例:计算[195,72,90]。五、素数定理1.9素数有无穷多个。x()x表示不超过x的个数，则有