计算机系统与网络安全技术（第2版）-课件 1-5-2 公钥密码学基础（欧拉定理）

第一章信息安全概述-欧拉定理计算机系统与网络安全技术欧拉定理a和b的最大公约数是能够同时整除a和b的最大的正整数：gcd（a，b）gcd（4，6）＝2如果gcd（a，b）＝1，则a和b互素如何求gcd（a，b）？最大公约数信息安全概述Fermat小定理:p素数,a是整数且不能被p整除,则:a（p-1）≡1modp.费尔马（

Fermat）小定理证明:考虑集合s1={1,2,…,p-1}对每个数乘以a,得到集合s2=

{a(modp),2a(modp),…,(p-1)a(modp)}s2中的元素两两不同且都在1与p-1之间,因此两个集合相同信息安全概述欧拉定理费尔马（

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)=?费尔马（

Fermat）小定理示例的应用解：210=1024≡1(mod11)253=(210)523≡1523≡8(mod11)信息安全概述欧拉定理（1）欧拉函数

ϕ(n)是整数1a<n中满足gcd(a,n)=1的个数欧拉定理（2）如何求欧拉函数(a)若(m1,m2)=1,则ϕ(m1m2)=ϕ(m1)ϕ(m2)(b)设n∈Z+,有分解式,n=p1e1p2e2...pmem其中p1,p2,…,pm∈Z+是互不相同的素数,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不互素的数的个数，因为p是素数，故ϕ(p

)等于从p

减去在1,2,…p

中被p整除的数的个数。而在1,2,…p,p+1,…,2p,…,p-1p中，p的倍数共有p-1个，所以ϕ(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)欧拉定理信息安全概述欧拉定理求欧拉函数的两个特例欧拉定理如果n=pq（p和q为素数），则ϕ(n)=（p-1）（q-1）如果n为素数，则ϕ(n)=n-1信息安全概述欧拉定理(2)欧拉定理如果gcd(a,n)=1,则:aϕ(n)

≡1modn.证明与费马小定理类似.注意：n=p时欧拉定理和费马小定理相同欧拉定理eg:求7803的后三位数字解：7803（mod1000）的结果

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

≡(7400)273

≡343(mod1000)信息安全概述欧拉定理eg:计算243210

（mod101）解： （1）由费尔马定理2100（mod1001）＝1（mo