第一章信息安全概述-歐拉定理計(jì)算機(jī)系統(tǒng)與網(wǎng)絡(luò)安全技術(shù)歐拉定理a和b的最大公約數(shù)是能夠同時(shí)整除a和b的最大的正整數(shù)：gcd（a，b）gcd（4，6）＝2如果gcd（a，b）＝1，則a和b互素如何求gcd（a，b）？最大公約數(shù)信息安全概述Fermat小定理:p素?cái)?shù),a是整數(shù)且不能被p整除,則:a（p-1）≡1modp.費(fèi)爾馬（

Fermat）小定理證明:考慮集合s1={1,2,…,p-1}對(duì)每個(gè)數(shù)乘以a,得到集合s2=

{a(modp),2a(modp),…,(p-1)a(modp)}s2中的元素兩兩不同且都在1與p-1之間,因此兩個(gè)集合相同信息安全概述歐拉定理費(fèi)爾馬（

Fermat）小定理證明:于是:(p-1)!=1

2

…

(p-1)≡[a(modp)

2a(modp)

…

(p-1)a(modp)]modp≡[a

2a…(p-1)a]modp≡[ap-1

(p-1)!]modp注意到(p-1)!與p互素,兩邊消去(p-1)!，得

ap-1≡1modp信息安全概述歐拉定理例：求253(mod11)=?費(fèi)爾馬（

Fermat）小定理示例的應(yīng)用解：210=1024≡1(mod11)253=(210)523≡1523≡8(mod11)信息安全概述歐拉定理（1）歐拉函數(shù)

?(n)是整數(shù)1a<n中滿足gcd(a,n)=1的個(gè)數(shù)歐拉定理（2）如何求歐拉函數(shù)(a)若(m1,m2)=1,則?(m1m2)=?(m1)?(m2)(b)設(shè)n∈Z+,有分解式,n=p1e1p2e2...pmem其中p1,p2,…,pm∈Z+是互不相同的素?cái)?shù),e1,e2,…,em∈Z+,?(n)=n(1-1/p1)(1-1/p2)…(1-1/pm)信息安全概述歐拉定理證明：?(n)=?(p1e1)?(p2e2)…?(pmem)

下證：?(p

)=p

-p-1?(p

)等于從p

減去在1,2,…p

中與p不互素的數(shù)的個(gè)數(shù)，因?yàn)閜是素?cái)?shù)，故?(p

)等于從p

減去在1,2,…p

中被p整除的數(shù)的個(gè)數(shù)。而在1,2,…p,p+1,…,2p,…,p-1p中，p的倍數(shù)共有p-1個(gè)，所以?(p

)=p

-p-1歐拉定理信息安全概述歐拉定理?(n)=?(p1e1)?(p2e2)…?(pmem)=(p1e1–p1e1-1)(p2e2-p2e2-1)…(pmem-pmem-1)=p1e1p2e2…pmem(1-1/p1)(1-1/p2)…(1-1/pm)

=n

(1-1/p1)(1-1/p2)…(1-1/pm)歐拉定理信息安全概述歐拉定理求歐拉函數(shù)的兩個(gè)特例歐拉定理如果n=pq（p和q為素?cái)?shù)），則?(n)=（p-1）（q-1）如果n為素?cái)?shù)，則?(n)=n-1信息安全概述歐拉定理(2)歐拉定理如果gcd(a,n)=1,則:a?(n)

≡1modn.證明與費(fèi)馬小定理類(lèi)似.注意：n=p時(shí)歐拉定理和費(fèi)馬小定理相同歐拉定理eg:求7803的后三位數(shù)字解：7803（mod1000）的結(jié)果

?(1000)=1000(1-1/2)(1-1/5)=400，有7803

≡(7400)273

≡343(mod1000)信息安全概述歐拉定理eg:計(jì)算243210

（mod101）解： （1）由費(fèi)爾馬定理2100（mod1001）＝1（mo