1.域（Fields）

在抽象代數(shù)中，“域”是一種可在其上進(jìn)行加、減、乘和除運(yùn)算而結(jié)果不會超自身的集合（代數(shù)結(jié)構(gòu)），其概念是數(shù)域以及四則運(yùn)算的推廣。域是環(huán)的一種，其區(qū)別在于域要求它的元素可以進(jìn)行除法運(yùn)算，這等價(jià)于每個(gè)非零的元素都要有乘法逆元；同時(shí)，域中元素關(guān)于乘法是可交換的。一句話，域是乘法可交換的除環(huán)。即：

1.若數(shù)集P中任意兩數(shù)作某一運(yùn)算的結(jié)果仍在P中，則稱P對這個(gè)運(yùn)算是封閉的。

2.數(shù)域的等價(jià)定義：如果一個(gè)包含0、1在內(nèi)的數(shù)集P，對于加、減、乘、除（除數(shù)不為0）是封閉的，則稱P為一個(gè)數(shù)域。

常見數(shù)域：復(fù)數(shù)域C；實(shí)數(shù)域R；有理數(shù)域Q（注意：自然數(shù)集N及整數(shù)集Z都不是數(shù)域，因?yàn)椴糠殖ㄟ\(yùn)算不是封閉的）。

2.有限域（伽羅華域Galois Fields）：僅含有限個(gè)元素的數(shù)域

①有限域定義

若域F只包含有限個(gè)元素，則稱其為“有限域”，又稱“伽羅華域”（由伽羅瓦(Galois.E)于18世紀(jì)30年代研究代數(shù)方程根式求解問題時(shí)引出的）。有限域在近代編碼、計(jì)算機(jī)理論、組合數(shù)學(xué)等各方面有著廣泛的應(yīng)用。

有限域中元素的個(gè)數(shù)稱為有限域的“階”。階必為素?cái)?shù)的冪（如何證明？），可表示為p^n（p是素?cái)?shù)、n∈Z+），這個(gè)素?cái)?shù)P就是該有限域的“特征數(shù)”，通常用GF(p?)表示p?元的有限域。盡管存在有無限個(gè)元素的無限域，但只有有限域在密碼編碼學(xué)中得到了廣泛的應(yīng)用。元素個(gè)數(shù)相同的有限域是同構(gòu)的。GF(p?)的乘法群是(p?-1)階的循環(huán)群。

在密碼學(xué)中，最常用的域是階為p的素?cái)?shù)域GF（p）或階為2^n的GF(2^n)域。當(dāng)n=1時(shí)，存在有限域GF（p），也稱為“素?cái)?shù)域”。GF(p)就是mod p，因?yàn)橐粋€(gè)數(shù)模p后，結(jié)果在[0，p-1]之間，即該域中有p個(gè)元素；對于元素a和b，則(a+b) mod p和(a*b)mod p，其結(jié)果都是域中的元素；GF(p)里面的加法和乘法都是平時(shí)用的加法和乘法，GF(p)的加法和乘法單位元分別是0和1。

為什么p一定要是一個(gè)素?cái)?shù)呢？這是因?yàn)楫?dāng)p為素?cái)?shù)時(shí)，才能保證集合中的所有元素都有加法和乘法逆元(0除外)。假如p等于10，盡管所有元素都有加法逆元，但乘法不行，如元素2，因?yàn)檎也坏揭粋€(gè)數(shù)a，使得2*a mod 10等于1；若p為素?cái)?shù)，那么它就能保證域中的所有元素都有逆元。利用反證法和余數(shù)的定義即可證明。

②有限域四則運(yùn)算規(guī)則

若任意a、b、c∈GF(q)，則必有：

1．封閉性：a+b∈GF(q)，a·b∈GF(q)；

2．結(jié)合律：(a+b)+c=a+(b+c)，(a·b)c=a(b·c)；

3．交換律：a+b=b+a，a·b=b·a；

4．乘對加分配律：a(b+c)=a·b+a·c；

5．必有加法恒等元0和乘法恒等元e，使：a+0=a，a·e=a，e可理解為1；

6．必有加法負(fù)元-a和乘法逆元a-1，使：a+(-a)=0，a.a-1=e，但0-1無定義。

③有限域定理

定理1? 一個(gè)有限域E有p?個(gè)元素，這里p是E的特征，而n是E在它的素域△上的次數(shù)。

定理2? 令有限域E的特征是素?cái)?shù)p，E所含的素域是△，而E有q=p?個(gè)元素，那么E就是多項(xiàng)式xq-x在△上的分裂域。任何兩個(gè)這樣的域都同構(gòu)。

定理3? 令△是特征為p的素域，而q=p?(n≥1)，那么多項(xiàng)式xq-x在△上的分裂域E就是一個(gè)有q個(gè)元的有限域。

定理4? 一個(gè)有限域E是它的素域△的一個(gè)單擴(kuò)域。

④有限域GF(2^8)多項(xiàng)式運(yùn)算

這是GF(p^n)的特例，p=2，n=8。例如多項(xiàng)式:f(x)=x^6+x^4+x^2+x+1，但是這里不同于中學(xué)的多項(xiàng)式運(yùn)算。下面是它的一些特點(diǎn)：

特點(diǎn)1：多項(xiàng)式的系數(shù)只能是0或1（即【0，p-1】）。若p=3，那么系數(shù)是可以取0，1，2的；

特點(diǎn)2：合并同類項(xiàng)“加法”即“⊕”，對系數(shù)進(jìn)行異或操作，如x^4+x^4=0；

特點(diǎn)3：減法就等于加法（即無所謂的減法），或者負(fù)系數(shù)。所以，x^4–x^4就等于x^4+x^4，-x^3就是x^3。1

例如，設(shè)f(x)=x^6+x^4+x^2+x+1，g(x)=x^7+x+1，則：

f(x)+g(x)=x^7+x^6+x^4+x^2+(1+1)x+(1+1)1=x^7+x^6+x^4+x^2；

f(x)–g(x)=f(x)+g(x)；

f(x)*g(x)=(x^13+x^11+x^9+x^8+x^7)+(x^7+x^5+x^3+x^2+x)+(x^6+x^4+x^2+x+1)=x^13+x^11+x^9+x^8+x^6+x^5+x^4+x^3+1；

f(x)/g(x)，除法如下圖所示，其余數(shù)也就是mod操作的結(jié)果:

伽羅華域的元素可以通過該域上的本原多項(xiàng)式生成。通過本原多項(xiàng)式得到的域，其加法單位元都是0，乘法單位元是1。本原多項(xiàng)式是一個(gè)素多項(xiàng)式（素多項(xiàng)式不能表示為其他兩個(gè)多項(xiàng)式相乘的乘積，類似于素?cái)?shù)）。以GF(2^3)為例，指數(shù)小于3的多項(xiàng)式共8個(gè)：0，1，x，x+1，x^2，x^2+1，x^2+x，x^2+x+1。其系數(shù)剛好就是000,001,010,011,100,101,110,111，是0到7這8個(gè)數(shù)的二進(jìn)制形式。多項(xiàng)式對應(yīng)一個(gè)值，我們可以稱這個(gè)值為多項(xiàng)式值（有時(shí)看成一個(gè)向量）。GF(2^3)上有不只一個(gè)本原多項(xiàng)式，選一個(gè)本原多項(xiàng)式x^3+x+1，這8個(gè)多項(xiàng)式進(jìn)行四則運(yùn)算后 mod (x^3+x+1)的結(jié)果都是8個(gè)之中的某一個(gè)。

設(shè)P(x)是GF（2^w）上的某一個(gè)本原多項(xiàng)式，GF（2^w）的元素產(chǎn)生步驟是：

1、給定一個(gè)初始集合，包含0,1和元素x，即?{0,1,x}；

2、將這個(gè)集合中的最后一個(gè)元素，即x，乘以x，如果結(jié)果的度大于等于w，則將結(jié)果mod P(x)后加入集合；

3、直到集合有2^w個(gè)元素，此時(shí)最后一個(gè)元素乘以x再mod P(x)的值等于1。

⑥四則運(yùn)算Python程序

輸入：伽羅華域位大小4、8、16、32、64，兩個(gè)數(shù)字。

primitive_polynomial_dict={4:0b10011,#x**4+x+1

8:(1<<8)+0b11101,#x**8+x**4+x**3+x**2+1

16:(1<<16)+(1<<12)+0b1011,#x**16+x**12+x**3+x+1

32:(1<<32)+(1<< 22)+0b111,#x**32+x**22+x**2+x+1

64:(1<<64)+0b11011#x**64+x**4+x**3+x+1

}

class GF:

??? def __init__(self, w):

??????? self.w = w

??????? self.total =(1<< self.w) -1

??????? self.gflog = []

??????? self.gfilog = [1]# g(0) =1

??????? self.make_gf_dict(self.w, self.gflog, self.gfilog)

??? def make_gf_dict(self, w, gflog, gfilog):

??????? gf_element_total_number =1<< w

??????? primitive_polynomial = primitive_polynomial_dict[w]

??????? for i in range(1, gf_element_total_number -1):

??????????? temp = gfilog[i -1]<<1# g(i) = g(i-1) * 2

??????????? if temp & gf_element_total_number:# 判斷溢出

??????????????? temp ^= primitive_polynomial# 異或本原多項(xiàng)式

??????????? gfilog.append(temp)

????? assert(gfilog[gf_element_total_number-2]<<1)^primitive_polynomial

??????? gfilog.append(None)

??????? for i in range(gf_element_total_number):

??????????? gflog.append(None)

??????? for i in range(0, gf_element_total_number -1):

??????????? gflog[gfilog[i]] = i

??????? print(gflog)

??????? print(gfilog)

??? def add(self, a, b):

??????? return(a ^ b) % self.total

??? def sub(self, a, b):

??????? return(a ^ b) % self.total

??? def mul(self, a, b):

??????? return self.gfilog[(self.gflog[a]+ self.gflog[b]) % self.total]

??? def div(self, a, b):

??????? return self.gfilog[(self.gflog[a] - self.gflog[b]) % self.total]

總結(jié)

以上是生活随笔為你收集整理的数域、有限域（伽罗瓦域）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。