信息安全数学基础第1章 整数的可除性.ppt
信息安全数学基础,信息安全工程大学,第1章 整数的可除性,1.1 整除,整除的一些基本性质,整除的一些基本性质,素数,素数,埃拉托色尼斯筛法,【人物传记】 埃拉托色尼斯,埃拉托色尼斯（公元前276-194）, 出生于希腊属地埃及西部的Cyrene, 他在雅典的柏拉图学习了一段时间. 托勒密二世（Ptolemy II）邀请他到亚历山大教他的儿子. 后来成为著名的亚历山大图书馆馆长. 他著有数学、地理、天文、历史、哲学和文学方面的书. 除了数学方面的工作, 他还以古代编年史和地理测量闻名.,素数的性质,素数个数定理,【人物传记】 克里斯汀·歌德巴赫,克里斯汀·歌德巴赫（1690-1764）生于普鲁士哥尼斯堡（这个城市因七桥问题而在数学界很有名）. 1725年成为圣彼得堡皇家学院的数学教授. 1728年到莫斯科成为沙皇彼得二世的老师. 1742年任职于俄国外交部. 除了“每个大于2的偶数都能写为两个素数的和以及每个大于5的奇数能写为3个素数的和”的猜想外, 在数学分析方面也做出了令人瞩目的贡献.,【人物传记】 陈景润,陈景润（1933-1996）取得了关于孪生素数和歌德巴赫猜想的重要结果. 1966年发表On the representation of a large even integer as the sum of a prime and the product of at most two primes（大偶数表为一个素数及一个不超过二个素数的乘积之和,简称“1+2”）, 成为哥德巴赫猜想研究上的里程碑. 而他所发表的成果也被称之为陈氏定理.,【人物传记】 张益唐,美籍华裔数学家张益唐（1955-）于1978年进入北京大学数学科学学院攻读本科, 1982年读硕士, 师从潘承彪, 1985年入读普渡大学, 导师为莫宗坚. 2013年由于在研究孪生素数猜想上取得了重大突破, 于第六届世界华人数学家大会中荣获晨兴数学卓越成就奖, 后来他也获颁Ostrowski奖和Rolf Schock奖. 2014年, 美国数学学会更将崇高的柯尔数论奖授予张益唐. 同年7月4日, 张益唐当选为中央研究院第30届数理科学组院士. 同年9月, 张益唐获得了该年度的麦克阿瑟奖（俗称“天才”奖）.,1.2.1带余除法,带余除法一般形式,带余除法-举例,1.2 .2 最大公因数,最大公因数-举例,故168和99的最大公因数为(168, 90)=2×3=6.,最大公因数的基本性质,最大公因数的基本性质,【例1.2.3】 计算最大公因数（120, 150, 210, 35）. 解: （120, 150）=30, （30, 210）=30, （30, 35）=5, 故（120, 150, 210, 35）=5 或（120, 150, 210, 35）=(120, 150), (210, 35)=(30,35) =5,最大公因数的基本性质,【人物传记】 欧几里德,【人物传记】 欧几里德（Euclid, 前325年前265年）, 古希腊数学家, 他最著名的著作几何原本被广泛的认为是历史上最成功的教科书,从古至今已经有了上千种版本, 这本书介绍了从平面到刚体几何以及数论的知识. 人们关于欧几里德的生平所知很少, 现存的欧几里德画像都是出于画家的想像.,当两个数很大且共同的素因数也很大时, 短除法用起来就不方便了. 例如, 求46480和39423的最大公因数. 这里介绍另外一种求最大公因数的方法欧几里德算法, 该方法有较高的效率, 而且易于程序实现. 欧几里德算法, 中文通常称为辗转相除法, 主要用于求两个整数的最大公因数, 从而为求解一次同余方程及一次同余方程组做铺垫.,1.2.3 欧几里德算法,欧几里德算法,欧几里德算法,欧几里德算法-举例,【例1.2.6】 利用欧几里德算法求（172, 46）.,欧几里德算法-举例,也可以这样求解：,C语言的一种程序实现方法,下面给出C语言的一种程序实现方法. int gcd(int a, int b) while(b != 0) int r = b; b = a % b; a = r; return a; ,裴蜀等式,裴蜀等式-举例,裴蜀等式-举例,故: 2=46×15+172×(-4),裴蜀等式-特例,裴蜀等式-举例,void Euclid(unsigned int num1,unsigned int num2) int a32,b32; int inv_a,inv_b,tmp; int i=0,j=0; a0=num1; b0=num2; while(ai%bj!=0) printf(“%d=%d×%d+%dn“,ai,ai/bj,bj,ai%bj); i+; j+; ai=bj-1; bj=ai-1%bj-1; printf(“%d=%d*%d+%dnn“,ai,ai/bj,bj,ai%bj);,/回代过程/ i-;j-; inv_a=1; inv_b=-ai/bj; printf(“%dn“,ai%bj); for(;i=0,j=0;i-,j-) printf(“ =%d×(%d)+%d×(%d)n“,ai,inv_a,bj,inv_b); tmp=inv_a; inv_a=inv_b; inv_b=tmp-ai-1/bj-1*inv_b; ,下面给出程序的一个运行结果： 209=3×59+32 59=1×32+27 32=1×27+5 27=5×5+2 5=2×2+1 2=2*1+0 1 =5×(1)+2×(-2) =27×(-2)+5×(11) =32×(11)+27×(-13) =59×(-13)+32×(24) =209×(24)+59×(-85),作业1,1、设a为自己的学号，b=210，求整数s,t，使得 as+tb=(a,b),1.3 最小公倍数,【例1.3.1】 求最小公倍数168, 90. 解: 前面用短除法得到了(168, 90). 求解过程如下.,故168和99的最小公倍数168, 90=2×3×28×15=2520.,最小公倍数的性质,最小公倍数的性质,最小公倍数的性质,最小公倍数的性质,1.4算术基本定理,标准分解式,最大公因数和最小公倍数,最大公因数和最小公倍数,【例1.4.3】 计算120, 150, 210, 35的最大公因数和最小公倍数. 解: 12023·3·5, 1502·3·52, 2102·3·5·7, 355·7. （120, 150, 210, 35）5, 120, 150, 210, 3523·3·52·74200.,
