數(shù)論相關(guān)基礎(chǔ)知識(shí)

1、數(shù)論相關(guān)基礎(chǔ)知識(shí)提綱群環(huán)域模運(yùn)算歐幾里德算法有限域GF(p)多項(xiàng)式運(yùn)算有限域GF(2n)Abstract AlgebraAlgebraic structure Semigroupclosure封閉性, associative 結(jié)合律Groupclosure, associativity, identity單位元, inverse逆元Ring+: associativity, commutativity交換律, identity, inverse 0*: associativity, distributivity分配律Fielda ringmultiplicative inverse 乘法逆元L

2、attice, Boolean4.1 群環(huán)域群 Group集合，元素二元運(yùn)算 封閉性、結(jié)合律單位元、逆元有限群、無(wú)限群交換群（Abel）循環(huán)群生成元環(huán) Ring環(huán)R二元運(yùn)算: 加法+、乘法(R, +)是交換群乘法封閉性、乘法結(jié)合律分配律 a(b+c) = ab+ac交換環(huán)乘法交換律整環(huán)（交換環(huán)且）乘法單位元1無(wú)零因子: ab=0 a=0或b=0域 Field域FF是整環(huán)存在乘法逆元(0除外)除法定義: a/b = a(b-1)有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)域有限域Group Ring Field域相關(guān)概念及定理域的特征 - 任意元素a的n次累計(jì)和為0的最小的n；域的特征要么是素?cái)?shù)，要么是0(沒(méi)有)；素

3、域：沒(méi)有非0真子域的域；有限域的階是pn（其中p是素?cái)?shù)）；有限域的乘法群是循環(huán)群；可逆在加/解密中的重要性加密的操作對(duì)象是比特分組，通常被看作整數(shù)加密是對(duì)整數(shù)的變換。這種變換必須能恢復(fù)(解密時(shí))，即可逆。如果加密是乘法，則解密就是除法，而域上正好有除法-乘法逆元。對(duì)于8bits字節(jié)，希望Z256是域，但它不是；于是轉(zhuǎn)而尋求GF(28)，它是域。AES的S盒是基于模2系數(shù)的模某8次不可約多項(xiàng)式的剩余類(lèi)。4.2 模運(yùn)算模運(yùn)算即求余數(shù)（C語(yǔ)言中的運(yùn)算符）x mod na其中0ab)gcd(a, b) = gcd(b, a mod b)求最大公因子輾轉(zhuǎn)相除法（歐幾里德算法）gcd(a, b) = gc

4、d(b%a, a%b)GCD(1970,1066)1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 +

5、 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0)函數(shù)gcd(a, b)int gcd(int a, int b)if (a=0) | (b=0)return a+b;elsereturn gcd(a%b, b%a);4.4 有限域GF(p)域，無(wú)限域有限域，又叫Galoris域有限域的階都有pn的形式階為p的有限域記為GF(p)唯一性 (Isomorphism)在同構(gòu)意義下，某階有限域只有一個(gè)GF(p)：(Zp, +, x)GF(pm)：系數(shù)在Zp上的模某不可約多項(xiàng)式的多項(xiàng)式域GF(2n)：p=2GF(p)：(Zp, +, x)逆元由于p是素?cái)?shù)，所以除了0外都有逆元GF(

6、p=2)：(Z2, +, x)GF(p=7)：(Z7, +, x)*GF(p=8)：(Z8, +, x)不是域求逆元：擴(kuò)展Euclid算法擴(kuò)展Euclid算法做歐幾里德算法的計(jì)算序列r0q1r1r2 (令r0n，r1a)r1q2r2r3r2q3r3r4rm-2qm-1rm-1rm (1)rm-1qmrm rm+1 (0)記t0 rm+1，t1rm，依tjtj-2 qi-1 tj-1 mod r0，得tm逆r1的逆擴(kuò)展Euclid算法舉例22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022) 4 即 322 4 mod 31 92413022

7、-2(322) 1即2422 1 mod 3128 1 mod 757522819-22819 即 732819 mod 7528119928-1(7328)9 即 328 9 mod 7519291 (7328)-2(338)1 即6728 1 mod75269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 8022922 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301函

8、數(shù)reverse()int reverse(int a, int m)int b, b1=1, b2=0; / 逆元int r, r1=a, r2=m; /do r = r2 % r1; / y-kx = rb = (b2-(r2/r1)*b1)%m;r2 = r1;b2 = b1;r1 = r;b1 = b; while (r1);if (r=0) return 0;if (b0) b += m;return b;4.5 多項(xiàng)式運(yùn)算多項(xiàng)式 一元n次整數(shù)域多項(xiàng)式運(yùn)算加，減乘例子：f(x) = x3 + x2 + 2，g(x) = x2 - x + 1f(x) + g(x) = x3 + 2x2

9、 - x + 3f(x) g(x) = x3 + x + 1f(x) x g(x) = x5 + 3x2 - 2x + 2-除法: f(x)/g(x)=q(x) r(x)整除，若r(x)=0模g(x)同余f(x) = q(x) g(x) + r(x) f(x) r(x) mod g(x)不可約多項(xiàng)式(素多項(xiàng)式,既約多項(xiàng)式)g(x)不能表示為另兩個(gè)多項(xiàng)式的乘積關(guān)于系數(shù)Zn的多項(xiàng)式多項(xiàng)式環(huán)系數(shù)是域F的多項(xiàng)式，構(gòu)成環(huán)系數(shù)是Zn的多項(xiàng)式環(huán)系數(shù)是Zp的多項(xiàng)式環(huán)在Z2上的多項(xiàng)式環(huán)，在計(jì)算機(jī)上操作時(shí)有優(yōu)勢(shì)加法，即XOR乘法，即AND構(gòu)造GF(pn)從環(huán)到域構(gòu)造GF(pn)系數(shù)在Zp上的n-1次多項(xiàng)式f(x)

10、集合S共有pn個(gè)(S,)構(gòu)成有限域GF(pn) 需要某n次不可約多項(xiàng)式m(x)使用模m(x)的多項(xiàng)式加法和乘法從GF(pn)到GF(2n)到GF(28) in AESExample GF(23)- 4.6 有限域GF(2n)系數(shù)模2，即只可0或1若次數(shù)最高7次，共28=256個(gè)多項(xiàng)式(剩余類(lèi))加法XOR乘法移位，加法/XOR乘法逆元(除法)擴(kuò)展Euclid算法GF(23)上的運(yùn)算（in AES）m(x) = x8 + x4 + x3 + x + 1運(yùn)算表：8x8 AES Termsabelian groupassociativecoefficient setcommutativecommutative ringcyclic groupdivisorEuclidean algorithmfieldfinite groupfinite ringfinite fieldgeneratorgreatest common divisorgroupidentity elementinfinite groupinfinite ringinfinite fieldintegral domaininverse elementirreducible polynomialmodular arithmeticmodular polynomial arithmeticmodulo operato