密码编码学与网络安全--原理与实现--（第八版）第5章 ------有限域
目錄
5.1群
5.1.1 群的性質(zhì)
5.1.2 交換群
5.1.3 循環(huán)群
5.2 環(huán)
5.3 域
5.4 有限域GF(p)
5.4.1 階為p的有限域
5.4.2 在有限域GF(p)中求乘法逆元
5.4.3 小結(jié)
5.5 多項(xiàng)式運(yùn)算
5.5.1 普通多項(xiàng)式運(yùn)算
5.5.2 系數(shù)在Zp中的多項(xiàng)式運(yùn)算
5.5.3 求最大公因式
5.5.4 小結(jié)
5.6 有限域GF(2^n)
5.6.1 動(dòng)機(jī)
?5.6.2 多項(xiàng)式模運(yùn)算
?5.6.3 求乘法逆元
?5.6.4 計(jì)算上的考慮
?5.6.5 使用生成元
5.6.6 小結(jié)
學(xué)習(xí)目標(biāo)
- 區(qū)分群、環(huán)和域。
- 理解有限域GF(p)的定義。
- 區(qū)分普通多項(xiàng)式運(yùn)算、系數(shù)在中的多項(xiàng)式運(yùn)算和有限域GF()中的多項(xiàng)式運(yùn)算。
- 理解有限域GF()的定義。
- 解釋模運(yùn)算符的兩種不同的用法。
有限域在密碼學(xué)中的地位越來(lái)越重要。許多密碼算法都依賴于有限域的性質(zhì)，特別是高級(jí)加密標(biāo)準(zhǔn)(AES)和橢圓曲線加密算法。其他例子包括消息認(rèn)證碼(CMAC)和認(rèn)證加密方案(GCM)。
本章介紹有關(guān)有限域概念的背景知識(shí)，以便讀者理解AES及其他使用有限域知識(shí)的密碼算法的設(shè)計(jì)。
5.1群
群、環(huán)和域都是數(shù)學(xué)理論中的分支——抽象代數(shù)或近世代數(shù)的基本元素。在抽象代數(shù)中，我們關(guān)心的是其元素能夠進(jìn)行代數(shù)運(yùn)算的集合，也就是說(shuō)，可以通過(guò)多種方法使得集合上的兩個(gè)元素運(yùn)算后得到集合中的第三個(gè)元素。這些運(yùn)算方法都遵守特殊的規(guī)則，而這些規(guī)則又能確定集合的性質(zhì)。根據(jù)約定，集合上元素的兩種主要運(yùn)算符號(hào)與普通數(shù)字的加法和乘法所用的符號(hào)相同。但要指出的是，在抽象代數(shù)中并不只限于普通的算術(shù)運(yùn)算，詳見(jiàn)后面的介紹。
5.1.1 群的性質(zhì)
群G，有時(shí)記為，是定義了一個(gè)二元運(yùn)算的集合，這個(gè)二元運(yùn)算可表示為??? ，G中的每個(gè)序偶(a,b)通過(guò)運(yùn)算生成中的元素，并且滿足以下公理。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A1)?封閉性? 若a和b都屬于G，則也屬于G。(這里a和一個(gè)意思不加區(qū)分，后文也一樣)? ? ? ? ?(A2)?結(jié)合律? 對(duì)于G中的任意元素a,b,c，都有。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A3)?單位元? G中存在一個(gè)元素e，對(duì)于G中的任意元素a，都有。? ? ? ? ? ? ? ? ? ? ? ? ?(A4)?逆元? 對(duì)于G中的任意元素a，G中都存在一個(gè)元素，使得。
---------------------------------------------------------------------------------------------------------------------------------書(shū)本這里舉了一個(gè)置換群的例子，詳細(xì)請(qǐng)看書(shū)
---------------------------------------------------------------------------------------------------------------------------------
若一個(gè)群的元素是有限的，則該群稱為有限群，并且群的階等于群中元素的個(gè)數(shù)。否則，稱該群為無(wú)限群。
5.1.2 交換群
一個(gè)群若滿足以下的條件，則稱為交換群。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A5). 交換律? 對(duì)于G中的任意元素a,b，都有。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ?加法運(yùn)算下的整數(shù)集（包括正整數(shù)、負(fù)整數(shù)和零）是一個(gè)交換群。乘法運(yùn)算下的非零實(shí)數(shù)集是一個(gè)交換群。前列中的集合(置換群)是一個(gè)群，但是對(duì)于，他不是交換群。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?群眾的運(yùn)算是加法時(shí)，其單位元是0；a的逆元是-a；且減法用以下規(guī)則定義：a-b=a+(-b)。
5.1.3 循環(huán)群
我們?cè)谌褐袑⑶髢邕\(yùn)算定義為重復(fù)運(yùn)用群中的運(yùn)算，如。此外，我們定義為單位元，并且，其中是a在群內(nèi)的逆元素。若群G中的每個(gè)元素都是一個(gè)固定元素的冪（k為整數(shù)），則稱群G是循環(huán)群。我們認(rèn)為元素a生成了群G，或者說(shuō)a是群G的生成元。循環(huán)群總是交換群，他可能是有限群或無(wú)限群。
e.g. 整數(shù)的加群是一個(gè)無(wú)限循環(huán)群，它由1生成。在這種情況下，冪被解釋為是用加法合成的，因此n是1的第n次冪。
5.2 環(huán)
環(huán)R，有時(shí)記為，是有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別稱為加法和乘法，且對(duì)于R中的任意元素a,b,c，滿足以下公理。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（A1~A5）R關(guān)于加法是一個(gè)交換群；也就是說(shuō)，R滿足從1到5的所有原則。對(duì)于此種情況下的加法群，我們用0表示其單位元，用-a表示a的逆元。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M1)? 乘法封閉性? 若a和b都屬于R，則ab也屬于R。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M2)? 乘法結(jié)合律? 對(duì)于R中的任意元素a,b,c，有。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M3)? 分配律? 對(duì)于R中的任意元素a,b,c，總有，。
環(huán)本質(zhì)上是一個(gè)集合，可在其上進(jìn)行加法、減法[a-b=a+(-b)]和乘法而不脫離該集合。
環(huán)若還滿足以下條件，則被稱為交換環(huán)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M4)? 乘法交換律? 對(duì)于R中的任意元素a,b，有ab=ba。
下面定義整環(huán)，它是滿足以下公理的交換環(huán)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M5)? 乘法單位元? 在R中存在元素1，使得對(duì)R中的任意元素a，有a1=1a=a。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (M6)? 無(wú)零因子? 若有R中的元素a,b，且ab=0，則必有a=0或b=0.
---------------------------------------------------------------------------------------------------------------------------------后面我會(huì)專門(mén)出一篇文章來(lái)學(xué)習(xí)環(huán)，多項(xiàng)式環(huán)，分圓多項(xiàng)式環(huán)，等。對(duì)于一些密碼學(xué)方案來(lái)說(shuō)是一種基本的結(jié)構(gòu)
---------------------------------------------------------------------------------------------------------------------------------
5.3 域
域F，有時(shí)記為，是有兩個(gè)二元運(yùn)算的集合，這兩個(gè)二元運(yùn)算分別稱為加法和乘法，且對(duì)于F中的任意元素a,b,c，滿足以下公理。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A1~M6)? F是一個(gè)整環(huán)；也就是說(shuō)，F滿足從A1到A5及從M1到M6的所有原則。? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(M7)? 乘法逆元? 對(duì)F中的任意元素a（除0外），F中存在一個(gè)元素使得。
域本質(zhì)上是一個(gè)集合，可以在其上進(jìn)行加法、減法、乘法和除法而不脫離該集合。除法又按規(guī)則來(lái)定義。
深入理解這些內(nèi)容后，下面這些可以替代的描述可能是有用的。域是一個(gè)集合，定義了兩個(gè)二元運(yùn)算——加法和乘法，滿足下面的條件。
5.4 有限域GF(p)
有限域的階（元素的個(gè)數(shù)）必須是一個(gè)素?cái)?shù)的冪，其中n為正整數(shù)。階為的有限域一般記為GF()，GF代表Galois域，它以第一位研究有限域的數(shù)學(xué)家的名字命名。在此要關(guān)注兩種特殊的情形：n=1時(shí)的有限域GF(p)，它和n>1時(shí)的有限域有著不同的結(jié)構(gòu)，本節(jié)將對(duì)它進(jìn)行研究。對(duì)有限域GF()來(lái)說(shuō)，有限域GF()具有特別重要的密碼學(xué)意義，詳見(jiàn)5.6節(jié)。
5.4.1 階為p的有限域
給定一個(gè)素?cái)?shù)p，元素個(gè)數(shù)為p的有限域GF(p)被定義為整數(shù)的集合，其運(yùn)算為模p的算數(shù)運(yùn)算。
整數(shù)的集合，在模n的算術(shù)運(yùn)算下構(gòu)成一個(gè)交換環(huán)。進(jìn)一步發(fā)現(xiàn)：中的任一整數(shù)有乘法逆元當(dāng)且僅當(dāng)該整數(shù)與n互素。若n為素?cái)?shù)，則中的所有非零整數(shù)都與n互素，中所有非零整數(shù)都有乘法逆元。
因?yàn)閣與p互素，若用w乘以的所有元素，則得出的剩余類(lèi)時(shí)中所有元素的另一種排列。因此，恰好只有一個(gè)剩余類(lèi)值為1。于是，中存在這樣的整數(shù)：當(dāng)它乘以w，得余數(shù)1。這個(gè)整數(shù)就是w得乘法逆元，記為，所以其實(shí)是一個(gè)有限域。
5.4.2 在有限域GF(p)中求乘法逆元
當(dāng)p值較小時(shí)，求有限域GF(p)中元素得乘法逆元很容易：只需構(gòu)造一個(gè)乘法表，所要結(jié)果直接從表中讀出。但是，當(dāng)p值較大時(shí)，這種方法時(shí)不切實(shí)際的。
若a和b互素，則b有模a的乘法逆元。也就是說(shuō)，若gcd（a,b）=1，則b有模a的乘法逆元。即對(duì)于正整數(shù)b<a，存在使得。若a時(shí)素?cái)?shù)且，則a和b顯然互素，且其最大公因式為1。運(yùn)用擴(kuò)展歐幾里得算法容易計(jì)算。
再次重復(fù)(2.7)，我們證明過(guò)該式可以用擴(kuò)展歐幾里得算法求解：
現(xiàn)在，若，則有。運(yùn)用2.3節(jié)定義的模算術(shù)的基本公式，有
然而，若，則。因此，若，則通過(guò)對(duì)式（2.7）運(yùn)用擴(kuò)展歐幾里得算法可以獲得b的乘法逆元。
更一般地，對(duì)任意n，擴(kuò)展歐幾里得算法可用于求內(nèi)的乘法逆元。若對(duì)方程應(yīng)用擴(kuò)展歐幾里得算法，并且得到，則在內(nèi)有。
5.4.3 小結(jié)
本節(jié)介紹了如何構(gòu)建階為p的有限域，其中p為素?cái)?shù)。特別地，我們用以下性質(zhì)定義有限域GF(p)。
我們已經(jīng)證明了有限域GF(p)中的元素是集合{0,1,...,p-1}中的元素，其算術(shù)運(yùn)算是模p的加法和乘法。
5.5 多項(xiàng)式運(yùn)算
?在繼續(xù)討論有限域之前，需要介紹一個(gè)有趣的問(wèn)題——多項(xiàng)式算術(shù)。這里只討論單變?cè)囗?xiàng)式，并且將多項(xiàng)式運(yùn)算分為三種。
- 使用代數(shù)基本規(guī)則的普通多項(xiàng)式運(yùn)算。
- 系數(shù)運(yùn)算是模p運(yùn)算的多項(xiàng)式運(yùn)算，即系數(shù)在有限域GF(p)中。
- 系數(shù)在有限域GF(p)中，且多項(xiàng)式被定義為模一個(gè)n次多項(xiàng)式m(x)的多項(xiàng)式運(yùn)算。
本節(jié)討論前兩種多項(xiàng)式運(yùn)算，下一節(jié)討論最后一種多項(xiàng)式運(yùn)算。
5.5.1 普通多項(xiàng)式運(yùn)算
一個(gè)n次多項(xiàng)式()的表達(dá)形式為
式中，是某個(gè)指定數(shù)集S中的元素，稱該數(shù)集為系數(shù)集，且。稱是定義在系數(shù)集S上的多項(xiàng)式。零次多項(xiàng)式被稱為常數(shù)多項(xiàng)式，它只是系數(shù)集中的一個(gè)元素。若，則對(duì)應(yīng)的n次多項(xiàng)式就被稱為首一多項(xiàng)式。
在抽象代數(shù)中，一般不給多項(xiàng)式中的x賦一個(gè)特定值。為了強(qiáng)調(diào)這一點(diǎn)，變?cè)獂有時(shí)被稱為不定元。
多項(xiàng)式運(yùn)算包含加法、減法和乘法，這些運(yùn)算是把變量x當(dāng)成集合S中一個(gè)元素來(lái)定義的。除法也以類(lèi)似的方式定義，但這時(shí)要求S是域。域包括實(shí)數(shù)域、有理數(shù)域、和素?cái)?shù)域。注意整數(shù)并不是域，它也不支持多項(xiàng)式除法運(yùn)算。
加法、減法的運(yùn)算規(guī)則是把相應(yīng)的系數(shù)相加減。因此，若
則加法運(yùn)算定義為
乘法運(yùn)算定義為
式中，。在后一個(gè)公式中，當(dāng)時(shí)令，當(dāng)時(shí)，令。注意結(jié)果的次數(shù)等于兩個(gè)多項(xiàng)式的次數(shù)之和。
5.5.2 系數(shù)在Zp中的多項(xiàng)式運(yùn)算
現(xiàn)在考慮系數(shù)是域F中的元素的多項(xiàng)式，這種多項(xiàng)式被稱為域F上的多項(xiàng)式。在這種情況下，容易看出這樣的多項(xiàng)式結(jié)合是一個(gè)環(huán)，稱為多項(xiàng)式環(huán)。也就是說(shuō)，如果把每個(gè)不同的多項(xiàng)式視為集合中的元素，那么這個(gè)結(jié)合就是一個(gè)環(huán)。
對(duì)有限域中的多項(xiàng)式進(jìn)行多項(xiàng)式運(yùn)算時(shí)，除法運(yùn)算是可能的。注意，這并不是說(shuō)能進(jìn)行整除。下面說(shuō)明兩者的區(qū)別。在一個(gè)域中，給定兩個(gè)元素a和b，a除以b的商也是這個(gè)域中的一個(gè)元素。然而，在非域的環(huán)R中，普通除法將得到一個(gè)商式和一個(gè)余式，這并不是整除。
現(xiàn)在，如果試圖在非域系數(shù)集上進(jìn)行多項(xiàng)式除法，那么除法運(yùn)算并不總是有定義的。
然而，如所見(jiàn)的那樣，即使系數(shù)集是一個(gè)域，多項(xiàng)式除法也不一定是整除。一般來(lái)說(shuō)，除法會(huì)產(chǎn)生一個(gè)商式和一個(gè)余式。對(duì)于有限域中的多項(xiàng)式，式（2.1）的除法可以重述如下：給定n次多項(xiàng)式f(x)和m次多項(xiàng)式g(x)()，若用g(x）除f(x)，則得到一個(gè)商式q(x)和一個(gè)余式r（x），它們滿足? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.2)
各個(gè)多項(xiàng)式的次數(shù)為
? ??
若允許有余數(shù)，則我們說(shuō)有限域中的多項(xiàng)式除法是可能的。與整數(shù)的長(zhǎng)除法相同，長(zhǎng)除法也適用于多項(xiàng)式除法。后面會(huì)給出一些例子。
與整數(shù)運(yùn)算相似，我們可以把余式r(x)寫(xiě)成f(x) mod g(x)，即。若這里沒(méi)有余式，則說(shuō)g(x)整除f(x)，并寫(xiě)為；等價(jià)地，可以說(shuō)g(x)是f(x)的一個(gè)因式或除式。
有限域GF(2)中的多項(xiàng)式對(duì)我們而言式有意義的。在有限域GF(2)中加法等價(jià)于異或（XOR）運(yùn)算，乘法等價(jià)于邏輯與（AND）運(yùn)算。
域F中的多項(xiàng)式f(x)被稱為不可約的（即約的），當(dāng)且僅當(dāng)f(x)不能表示為兩個(gè)多項(xiàng)式的積（兩個(gè)多項(xiàng)式都在F上，次數(shù)都低于f（x）的次數(shù)）。與整數(shù)相似，一個(gè)不可約多項(xiàng)式也被稱為素多項(xiàng)式。
5.5.3 求最大公因式
通過(guò)定義最大公因式，可以擴(kuò)展有限域中多項(xiàng)式運(yùn)算和整數(shù)運(yùn)算之間的相似性。如果：
那么多項(xiàng)式c(x)為a(x)和b(x)的最大公因式。下面是一個(gè)等價(jià)的定義：gcd[a(x),b(x)]是能同時(shí)整除a(x)和b(x)的多項(xiàng)式中次數(shù)最高的一個(gè)。
? ? ? ? ? ? ? ? ? ? ? ? ?(5.3)
上式假設(shè)a(x)的次數(shù)大于b(x)的次數(shù)，可以重復(fù)使用(5.3)來(lái)求最大公因式。將下列方案和用于整數(shù)的歐幾里得算法的定義進(jìn)行比較。
每個(gè)循環(huán)中都有，直至最后?。因此，通過(guò)重復(fù)應(yīng)用除法，我們得到了兩個(gè)多項(xiàng)式的最大公因式。這就是用于多項(xiàng)式的歐幾里得算法。
5.5.4 小結(jié)
本節(jié)首先討論了一般多項(xiàng)式的算術(shù)運(yùn)算。在一般多項(xiàng)式算術(shù)運(yùn)算中，變量不被計(jì)算，即不給多項(xiàng)式的變量賦值。相反，運(yùn)用代數(shù)的一般規(guī)則對(duì)多項(xiàng)式進(jìn)行算術(shù)運(yùn)算（加、減、乘、除）。除非系數(shù)是域的元素，否則多項(xiàng)式的除法是不允許的。
接著討論了有限域GF(p)中的多項(xiàng)式算術(shù)運(yùn)算：加、減、乘、除。然而，除法不是整除，即除法的結(jié)果通常是商和余數(shù)。
最后，本節(jié)說(shuō)明了使用歐幾里得算法可以求有限域中的兩個(gè)多項(xiàng)式的最大公因式。
本節(jié)論述的知識(shí)為下一節(jié)的學(xué)習(xí)奠定了基礎(chǔ)。下一節(jié)中將用多項(xiàng)式來(lái)構(gòu)建階為的有限域。
5.6 有限域GF(2^n)
前幾節(jié)中提到過(guò)有限域的元素個(gè)數(shù)必須為，其中p為素?cái)?shù)，n為正整數(shù)。5.4節(jié)中討論了元素個(gè)數(shù)為p的有限域這一特殊情況。我們發(fā)現(xiàn)在使用上的模運(yùn)算時(shí)，它滿足域的所有條件。當(dāng)n>1時(shí)，上的多項(xiàng)式在模運(yùn)算時(shí)并不能產(chǎn)生一個(gè)域。本節(jié)介紹在一個(gè)具有個(gè)元素的集合中，什么樣的結(jié)構(gòu)滿足域的所有條件，并集中討論有限域GF()。
5.6.1 動(dòng)機(jī)
實(shí)際上所有的加密算法(包括對(duì)稱密鑰和公開(kāi)密鑰算法)都涉及整數(shù)集上的算術(shù)運(yùn)算。如果某種算法使用的運(yùn)算之一是除法，那么就使用定義在有限域中的運(yùn)算。為了方便使用和提高效率，我們希望這個(gè)整數(shù)集中的數(shù)與給定的二進(jìn)制位數(shù)所能表達(dá)的信息一一對(duì)應(yīng)而不應(yīng)出現(xiàn)浪費(fèi)。也就是說(shuō)，我們希望這個(gè)整數(shù)集的范圍是從0到，以便正好對(duì)應(yīng)一個(gè)n位的字。?
?
?5.6.2 多項(xiàng)式模運(yùn)算
設(shè)集合S由域上次數(shù)小于等于n-1的所有多項(xiàng)式組成。每個(gè)多項(xiàng)式的形式如下：
?式中，在集合{0,1,....,p-1}上取值。S中共有個(gè)不同的多項(xiàng)式。
如果定義了合適的運(yùn)算，那么每個(gè)這樣的集合S就是一個(gè)有限域。定義由如下幾條組成。
?5.6.3 求乘法逆元
如歐幾里得算法可以用來(lái)求兩個(gè)多項(xiàng)式的最大公因式那樣，擴(kuò)展歐幾里得算法可以用來(lái)求一個(gè)多項(xiàng)式的乘法逆元。若多項(xiàng)式b(x)的次數(shù)小于a(x)的次數(shù)且，則該算法能求出b(x)以a(x)為模的乘法逆元。若a(x)為即約多項(xiàng)式，即除了本身與1外沒(méi)有其他因式，則始終有g(shù)cd[a(x),b(x)]=1。算法的描述方式和整數(shù)情形的擴(kuò)展歐幾里得算法一樣。給定兩個(gè)多項(xiàng)式a(x)和b(x)，其中a(x)的次數(shù)大于b(x)的次數(shù)。我們希望解如下方程得到v(x)、w(x)和d(x)，其中d(x) = gcd[a(x),b(x)]:
如果d(x)=1，那么w(x)是b(x)模a(x)的乘法逆元。計(jì)算過(guò)程如下：
?5.6.4 計(jì)算上的考慮
有限域GF()中的多項(xiàng)式
可以由它的n個(gè)二進(jìn)制系數(shù)唯一地表示。因此，有限域GF()中的每個(gè)多項(xiàng)式都可以表示一個(gè)n位的二進(jìn)制數(shù)。
加法? ? ?我們發(fā)現(xiàn)這里的多項(xiàng)式加法是對(duì)應(yīng)系數(shù)分別相加，而對(duì)于上的多項(xiàng)式，加法其實(shí)就是異或(XOR)運(yùn)算。所以，有限域?GF()中的兩個(gè)多項(xiàng)式的加法等同于按位異或運(yùn)算。
乘法? ? ?簡(jiǎn)單的異或運(yùn)算不能完成有限域?GF()中的乘法，但是可以使用一種相當(dāng)直觀且容易實(shí)現(xiàn)的技巧。以為多項(xiàng)式的有限域?GF()是AES中使用到的有限域，我們將參照該域來(lái)討論這個(gè)技巧。這個(gè)技巧容易推廣到有限域?GF()。
這個(gè)技巧基于下面的等式：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(5.4)
稍作思考就不難證明式(5.4)是正確的。如果不確定，可以除一下。一般來(lái)說(shuō)，在有限域?GF()中對(duì)n次多項(xiàng)式p(x)，有。
?5.6.5 使用生成元
定義有限域GF()的另一種等價(jià)方式有時(shí)更方便，它使用相同的不可約多項(xiàng)式。首先，需要兩個(gè)定義：階位q的有限域F的生成元是一個(gè)元素，記為g，該元素的前q-1個(gè)冪構(gòu)成了F的所有非零元素，即域F的元素是0,。
回顧第2章的討論可知，若a是n的一個(gè)本原根，則其冪是不同的(mod p)。且他們與n是互素的。特別地，對(duì)于素?cái)?shù)p，若a是p的一個(gè)本原根，則其冪是不同的(mod p)。考慮由多項(xiàng)式f(x)定義的域F，若F內(nèi)的一個(gè)元素b滿足，則稱b為多項(xiàng)式f(x)的根。包含于F的元素b稱為多項(xiàng)式的一個(gè)根，前提是。
首一多項(xiàng)式f(x)是有限域GF(p)上的n次本原多項(xiàng)式，當(dāng)且僅當(dāng)其根是有限域GF()的非零元素的生成元。特別地，可以證明，f(x)滿足
此外，上述方程為真時(shí)的最小正整數(shù)是。也就是說(shuō)，不存在整數(shù)使得f(x)整除。
所有本原多項(xiàng)式都是不可約的，反之則不成立。對(duì)于不是本原多項(xiàng)式的不可約多項(xiàng)式i，我們可以找到一個(gè)正整數(shù)。
最后，可以證明一個(gè)不可約多項(xiàng)式的根g是這個(gè)不可約多項(xiàng)式定義的有限域的生成元。
?通常，對(duì)于由不可約多項(xiàng)式f(x)生成的有限域GF()，有。計(jì)算到的值。域的元素對(duì)應(yīng)g的冪：到，另外再加上零元素。域元素的乘法用公式實(shí)現(xiàn)，其中k為任意整數(shù)。
5.6.6 小結(jié)
本節(jié)說(shuō)明了如何構(gòu)建階為的有限域。特別地，定義了具有如下性質(zhì)的有限域GF()。
有限域?GF()的元素可由二元有限域中所有次數(shù)不大于n-1的多項(xiàng)式集合定義。每個(gè)多項(xiàng)式可由唯一的n位數(shù)來(lái)表示。有限域中的算術(shù)是模某個(gè)次數(shù)為n的不可約多項(xiàng)式算術(shù)。還介紹了有限域?GF()的一種等價(jià)定義，該定義利用了生成元，其運(yùn)算用生成元的冪進(jìn)行。
總結(jié)
以上是生活随笔為你收集整理的密码编码学与网络安全--原理与实现--（第八版）第5章 ------有限域的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： partial 分部类-庞大类的瘦身计划
- 下一篇： Linux之Ubuntu安装搜狗输入法