数论基础 网络安全 NETWORK SECURITY a与b的最大公因数：gcd(a,b),简记为(a,b) ·gcd(20,24)=4,gcd(15,16)=1 如果gcd(a,b)=1,称a与b互素 模运算mod a=qn+r 0sr<n;q=[a/n]i [x]表示小于或等于x的最大整数 a=[a/n]n (a mod n)r=a mod n 如果(a mod n)=(b mod n),则称a与b模n同余， 记为a=bm0dn 例如，23=8mod5,8=1mod7 13
13 数论基础 • a与b的最大公因数：gcd（a, b），简记为（a, b） ▪ gcd（20, 24）=4 , gcd（15, 16）=1 • 如果gcd（a, b）=1 ，称a与b 互素 • 模运算 mod a= q n +r 0≤r<n ; q=[a/n] ; [x] 表示小于或等于x的最大整数 a=[a/n]n + （a mod n） , r = a mod n 如果 （a mod n ）= （b mod n） ，则称a 与b 模n同余， 记为 a = b mod n 例如， 23 =8 mod 5 , 8 =1 mod 7
数论基础（续） 网络安全 NETWORK SECURITY 模运算对加法和乘法是可交换的、可结合的、可分配的 (a+b)mod n=(a mod n)+(b mod n))mod n (a-b)mod n=((a mod n)-(b mod n))mod n (axb)mod n=((a mod n (bmod n))mod n (a x (b+c))mod n=(a xb)mod n+(a xc)mod n)mod n ·幂模运算ma mod n m2 mod n= (mxm) mod n=(m mod n 2 mod n m4 mod n=(m2 mod n 2 mod n m8 mod n=((m2 mod n)2 mod n)2 mod n m25modn=(m×m8×m1 mod n
14 数论基础（续） • 模运算对加法和乘法是可交换的、可结合的、可分配的 （a+b） mod n = （（a mod n ） + （b mod n） ） mod n （a-b） mod n = （（a mod n） – （b mod n） ） mod n （a×b） mod n = （（a mod n ）× （b mod n） ） mod n （a × （b+c） ） mod n = （（ a ×b） mod n + （a ×c） mod n） mod n • 幂,模运算 ma mod n m2 mod n = （m×m） mod n = （m mod n ） 2 mod n m4 mod n = （m2 mod n ） 2 mod n m8 mod n = （（m2 mod n ）2 mod n ）2 mod n m25 mod n = （m × m8 × m16） mod n
数论基础（续） 网络安全 NETWORK SECURITY 欧拉函数中n) n是正整数，中()是比n小且与n互素的正整数的个数 ==== 1K1)1=1 {1,2}1=2 中 1K1,3}=2 1K1,2,3,4}1=4 中(6 |K1,5}1=2 中(7) 是2,3,4,56三 中(10)=1K1,3,7,9}1=4 中(11) =,2,34,5,5,78,910l=10 如果p是素数，则中p)=(p-)比如中(2)，(5) 中11) 如果p,9是素数，则中(pg)=中(p中(g)=(p-1(g-) 比如中(10) 15
15 数论基础（续） • 欧拉函数ф(n) ▪ n是正整数， ф(n)是比n小且与n 互素的正整数的个数 ф(2) = |{1}| =1 ф(3) = |{1, 2}| =2 ф(4) = |{1, 3}| =2 ф(5) = |{1, 2, 3, 4 }| =4 ф(6) = |{1, 5}| =2 ф(7) = |{1, 2, 3, 4, 5, 6}| =6 ф(10) = |{1, 3, 7, 9}| =4 ф(11) = |{1, 2,3,4,5,6, 7,8, 9,10}| =10 ▪ 如果p是素数，则ф(p)=(p-1), 比如ф(2), ф(5)， ф(11) ▪ 如果p,q 是素数，则ф(pq)=ф(p)ф(q)＝ (p-1)(q-1), 比如, ф(10)
数论基础（续） 网络安全 NETWORK SECURITY 定理1若ac=bd mod n且c=d mod n及(c,n)=1,则a=b mod n 证明由(a-b)c+b(c-d)=ac-bd=0modn可得n(a-b)c。因为及 (c,n)=1,故n|(a-b)。因此a=bmod n 定理2若(a,n)=1,则存在唯一整数b,0<b<n,且(b,n)=1,使得 ab=1 mod n 证明由定理1知，若(a,n)=1,且jmod n,则ai≠aj mod n。因此， 集合{ai mod n)1=0,1,,n1为集合0,1，，n-1的一个排列。因 此b为ab=1modn的唯一解。此外，因ab-1=kn,k为正数，若(b, n)=g则g|(ab-1)。因g|ab,所以gl1。因此，g=1。故b也与n互 素。 16
16 数论基础（续） • 定理1 若ac=bd mod n 且c=d mod n 及 (c，n)=1，则 a=b mod n • 证明 由(a-b)c+b(c-d)=ac-bd=0 mod n 可得 n | (a-b)c。因为及 (c，n)=1，故n | (a-b)。因此a=b mod n • 定理2 若(a，n)=1，则存在唯一整数b，0<b<n，且(b，n)=1，使得 ab=1 mod n • 证明 由定理1知，若(a，n)=1，且ij mod n，则aiaj mod n。因此， 集合{ai mod n}i=0，1，…，n-1为集合{0，1，…，n-1}的一个排列。因 此b为ab=1 mod n的唯一解。此外，因ab-1=kn，k为正数，若(b， n)=g则g | (ab-1)。因g | ab，所以g|1。因此，g=1。故b也与n互 素
数论基础（续) 网络安全 NETWORK SECURI 定理3令{r1,r2,, r(n为模n的一既约剩余系，且(a,n=1,则 ari,ar2,..., ar(m}也为模n的一既约剩余系 证明设(arj,n)=g,则ga或gr。因此我们得以下两种情况。 1)gla且gln,或2)glr且g1n。 首先1)不可能，因为(a,n)=1；其次2)也不可能，因为r为模n既 约剩余系的一元素。因此(arj,n)=1。此外，ar≠ar,否则r=r。因 此{ar1,ar2,,arm}也为模n的一既约剩余系。 ● 定理4欧拉定理：若(a,n)=1,则a(o)=1modn 证明令{r1,r2,,r(m}为模n的一既约剩余系，由定理3知，若(a, n)=1,则{ar1,ar2,,ar中m)}也为模n的一既约剩余系。因此 Π1<=i<=m)(ar)modn=卫1<=i<=中n(r)modn,由消去法，可得 a(n)=1 mod n 17
17 数论基础（续） • 定理3 令{r1，r2，…，rф(n)}为模n的一既约剩余系，且(a，n)=1，则 {ar1，ar2，…，arф(n)}也为模n的一既约剩余系 • 证明 设(arj，n)=g，则g|a或g|rj。因此我们得以下两种情况。 1) g|a且g|n，或 2) g|rj且g|n。 首先 1）不可能，因为(a，n)=1；其次 2）也不可能，因为rj为模n既 约剩余系的一元素。因此(arj，n)=1。此外， ariarj，否则ri=rj。因 此{ar1，ar2，…，arф(n)}也为模n的一既约剩余系。 • 定理4 欧拉定理：若(a，n)=1，则aф(n)=1 mod n • 证明 令{r1，r2，…，rф(n)}为模n的一既约剩余系，由定理3知，若(a， n)=1，则{ar1，ar2，…，arф(n)}也为模n的一既约剩余系。因此 1<=i<=ф(n) ( ari) mod n = 1<=i<=ф(n) (ri) mod n，由消去法，可得 aф(n)=1 mod n