电子商务安全与管理

《电子商务安全与管理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.1素数和数的互素初等数论研究的基本对象是整数集合和自然数集合;整数集合Z={0,±1,±2,±3,……}自然数集合N={1,2,3,4,……}自然数集合对于+和*是封闭的,而整数集合对+,*,-是封闭的目的:研究/的封闭性,以便应用于加解/密。2.1素数和数的互素2.1.1除数和整除的概念若b≠0且a,b,m∈Z，使得a=mb，称b整除a,记为b

2、a，又称b为a的除数（因子）。若不存在整数m使得a=mb，则称b不能整除a。例：24的因子是1，2，3，4，6，8，12，24几个性质：如果a

3、1，则a=±1;如果a

4、b且b

5、a，则a=±b;任何b≠0能

6、整除0；如果b

7、g,而且b

8、h，则对任意整数m和n，有b

9、(mg+nh)2.1素数和数的互素2.1.2素数（质数）的概念整数p>1被称为素数，是指p的因子仅有±1，±p算术基本定理任何大于1的整数a，都能被因式分解为：a=p1a1p2a2…ptat，这里p1>p2>…>pt都是素数，且每一个ai>0。例：91=13×7；11011=13×112×7；12=3×222.1素数和数的互素2.1.3最大公约数若a,b,c∈Z，如果c

10、a,c

11、b,称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足：1）d是a和b的公约数；2）对a和b的任何一个公

12、约数c,有c

13、d，记为：d=gcd(a,b)。注意：第2)指出了其它约数都是最大公约数的因子，这一点可以从:a=p1a1p2a2…ptat，,b=q1b1q2b2…qfbf,c=rimin(ai,bi)…rjmin(aj,bj)看出(这里ri=pm=qn)。例如gcd(8,12)=4,其它约数2,1都是4的因子。最大公约数的另外一种等价形式的定义：gcd(a,b)=max{k

14、k

15、a,k

16、b}2.1素数和数的互素2.1.4带余除法命题：设a,b∈Z,b>0，则存在惟一确定的整数q和r，使得a=qb+r（0≤r

17、2证明：定义实数x=[x]+{x}，其中[x]为x的整数部分，{x}为x的小数部分；先证明满足条件的q和r是存在的：令q=[a/b],r=a-qb,则q和r都是整数；并且由于r/b=a/b-q={a/b},而0≤{a/b}<1,因而0≤r/b<1,即0≤r

18、r-r’

19、

20、1+r2)+r1=…=q1(q2(…(qnrn-1+0)+…)+r1,直到rn=0为止，则gcd(a,b)=rn-1计算机编程的方法：(1)X←a;Y←b;(2)ifY=0returnX=gcd(a,b);(3)R=XmodY;(4)X←Y,Y←R;(5)goto(2);2.1素数和数的互素2.1.5欧几里德算法Euclid（辗转相除法，求最大公约数的方法）例：求gcd(1970,1066)1970=1×1066+9041066=1×904+162…6=1×4+24=2×2+0所以：gcd(1970,1066)=gcd(4,2)=22.1素数和数的互素

21、2.1.5欧几里德算法Euclid（辗转相除法，求最大公约数的方法）引理：任意两个整数a,b的最大公约数d可以表示成a,b两数关于整系数的线性组合，即有s,t∈Z,使d=sa+tb。例如gcd(180,252)=36,252=1*180+72（72=1*252-1*180），180=2*72+36(36=1*180-2*72),72=2*36+0gcd(180,252)=1*180-2*72=1*180-2*(1*252-1*180)=3*180-2*252数的互素：若gcd(a,b)=1，则称a与b互素（a,b∈Z）2.2模运算2.2.1整数同余定义

22、：如果(amodn)=(bmodn)，则称整数a和b模n同余，记为a≡bmodn，这里n为正整数。整数同余关系是一种等价关系，满足三个性质：自反性对称性传递性2.2模运算2.2.2模运算的操作与性质[(amodn)±×(bmodn)]modn=(a±×b)modn例：求117mod132.2模运算2.2.3幺元e（单位元）和零元θ若e⊙x≡x⊙e≡x(modn),则称e为⊙模运算的幺元；例如，0是Z集合中+或-模运算的幺元。若θ⊙x≡x⊙θ≡θ(modn),则称θ为⊙模运算的零元；例如，0是Z集合中*模运算的零元。2.2模运算2.2.4可逆元（相反数）

23、若x⊙y≡e(modn),则称x(y)可逆，其逆元为y(x)。例如：1+7≡0(mod8),则