陳志江,董 文,賈中云
(杭州師范大學(xué)信息科學(xué)與工程學(xué)院,浙江 杭州 310036)
伽羅瓦域運(yùn)算的軟件實(shí)現(xiàn)
陳志江,董 文*,賈中云
(杭州師范大學(xué)信息科學(xué)與工程學(xué)院,浙江 杭州 310036)
有限域是編碼理論中相當(dāng)重要的代數(shù)基礎(chǔ)知識(shí),有限域上的運(yùn)算也顯得非常重要.文章通過研究有限域的特點(diǎn)之后,給出了典型有限域GF(2n或3n)(n∈N)上加法與乘法的計(jì)算機(jī)實(shí)現(xiàn).仿真結(jié)果表明,典型有限域上的加法和乘法都得到了很好的實(shí)現(xiàn),具有潛在的實(shí)用價(jià)值.
有限域;加法;乘法
有限域運(yùn)算主要有加法、乘法、冪運(yùn)算、二次方和模逆等,文章主要討論兩種最基本的域運(yùn)算——加法和乘法,并且在軟件上實(shí)現(xiàn)它.目前存在許多這兩種運(yùn)算的算法,從方便實(shí)現(xiàn)上來看,二進(jìn)制域是GF(2n)最具有吸引力的,運(yùn)算只涉及到移位和按位的模2加,這個(gè)在用軟件實(shí)現(xiàn)上很有誘惑力.像Montgomery算法[1]、固定窗口算法[2]等都可以很好的實(shí)現(xiàn)域運(yùn)算.
1.1 域的概念
表1 常用本原多項(xiàng)式Tab.1 Common primitive polynomial
定義1 若S是一個(gè)非空集合,并且在S內(nèi)的一種代數(shù)運(yùn)算(用▽表示)滿足以下要求:
a) 封閉性,?α,β∈S,?α▽?duì)隆蔛;
b) 結(jié)合律,?α,β∈S,?(α▽?duì)?▽?duì)?α▽(β▽?duì)?;
c) ?恒等元ε∈S,?α∈S,使得α▽?duì)?ε▽?duì)?α;
d) ?α∈S,?α-1∈S,使α▽?duì)?1=α-1▽?duì)?ε.
這樣就稱這個(gè)集合S為一個(gè)群.如果?α,β∈S,都有α▽?duì)?β▽?duì)?,就稱群S為阿貝爾群.
定義2 存在非空集合R,如果在R中定義了加和乘兩種運(yùn)算并且滿足以下公理:
a)R關(guān)于加法構(gòu)成阿貝爾群,加法恒等元記為0;
b)R中非零元素全體對(duì)乘法構(gòu)成阿貝爾群,乘法恒等元記為1;
c) 加法和乘法滿足分配律:α(β+γ) =αβ+αγ.
這樣稱R為域[3],域中元素的個(gè)數(shù)就為域的階.
1.2 本原多項(xiàng)式
如果一個(gè)n次的不可約多項(xiàng)式f(x)能整除1 +zt而不能整除其它1 +zs,其中t= 2n- 1,s 伽羅瓦域[5](或稱有限域)的元素個(gè)數(shù)有限,GF(p)來表示p階伽羅瓦域,每個(gè)伽羅瓦域GF(p)都至少包含了一個(gè)本原元素,它用來生成該域中的其它每個(gè)元素.把GF(p)延伸為一個(gè)含有pn個(gè)元素的域,稱為GF(p)的擴(kuò)展域,表示為GF(pn),其中n是一個(gè)非零正整數(shù). 舉個(gè)例子,二進(jìn)制域GF(2)就是GF(2n)其中的一個(gè)子域,除了0和1以外,在擴(kuò)展域中還存在特殊元素,用新元素a來表示.在GF(2n)中任何非零元素都可以通過a的冪次來表示.因此,元素的無限集G就可以根據(jù)元素{0,1,a}形成,無限集G中后一個(gè)元素依次通過前面一個(gè)元素乘以a來得到: G= {0,1,a,…,aj,…} = {0,a0,a1,…,aj,…} . (1) 為了從G中得到有限元素的集合GF(2n),所以G必須只能含有2n個(gè)元素,并且要對(duì)乘法封閉,故可以用以下不可約多項(xiàng)式來表示域元素對(duì)乘法的封閉: a(2n-1)+1=0, 也就是: a(2n-1)=1=a0. (2) 有了這個(gè)限制條件,任何冪次等于或超過2n-1的域元素都可以降階為冪次小于2n-1的元素: a(2n+m)=a(2n-1)a(1+m)=a(1+m), (3) 所以可以得到以下等價(jià)序列: {0,1,a,a2,…,a(2n-2),a(2n-1),a2n,…}?{0,1,a,a2,…,a(2n-2),a0,a1,…}, (4) 從而就可以得到伽羅瓦域GF(2n)的元素由下面序列所構(gòu)成: GF(2n) = {0,1,a,a2,…,a(2n-2)}. (5) 如果有相同的生成元,素?cái)?shù)域的加法是很簡(jiǎn)單的: (x1a1+x2a2+ …+xrar) + (y1a1+y2a2+ … +yrar) = (x1+y1)a1+ … + (xr+yr)ar, 表2 GF(9)對(duì)數(shù)表Tab.2 The logarithms of GF(9) 換句話說就是把對(duì)應(yīng)項(xiàng)的系數(shù)相加. 如果有相同的底,那么乘法也是簡(jiǎn)單的,可以看到gi·gj=gi+j,冪的次數(shù)都是經(jīng)過模運(yùn)算簡(jiǎn)化的. 為了更好進(jìn)行這兩種運(yùn)算,需要建立一張對(duì)數(shù)表.因?yàn)間i=x的話,就稱i為以g為底x的對(duì)數(shù). 假設(shè)在GF(9)中,選擇一個(gè)元素a,可以使a2= 2(超過這個(gè)整數(shù)對(duì)3取模),從而得到g=1 +a是本原元,這樣就可以得到如下對(duì)數(shù)表2. 這樣就可以對(duì)照如上對(duì)數(shù)表簡(jiǎn)單計(jì)算乘法:(a+2)(2a+2)=g5*g7=g12=g4= 2. 在GF(2n)中,2n個(gè)元素的任意一個(gè)都可以由階數(shù)小于或等于n- 1的不同多項(xiàng)式來表示,最高冪指數(shù)就是多項(xiàng)式的階數(shù).GF(2n)中的每個(gè)非零元素都可以用多項(xiàng)式ai(x)來表示,系數(shù)至少有一個(gè)不為零.對(duì)于i= 0,1,2,…,2n- 2,有 ai(x) =ai,0+ai,1x+ai,2x2+ … +ai,m - 1xm - 1, (6) 這樣兩個(gè)元素的加法就為兩個(gè)多項(xiàng)式中同冪次項(xiàng)系數(shù)進(jìn)行模運(yùn)算相加,即 ai+aj= (ai ,0+aj ,0) + (ai ,1+aj ,1)x+ … + (ai ,m-1+aj ,m-1)xm-1. (7) 乘法就是把兩個(gè)元素表示成指數(shù)形式,可以將指數(shù)直接相加取模,即 ai*aj=a(i + j)mod(2n-1). (8) 文章使用Matlab實(shí)現(xiàn)伽羅瓦域內(nèi)的算法實(shí)現(xiàn). GF(2)內(nèi)加法,仿真結(jié)果如表3. 表3 GF(2)內(nèi)加法 Tab.3 Addition in GF(2) GF(3)內(nèi)加法,仿真結(jié)果如表4. 表4GF(3)內(nèi)加法 a+b1+1=21+2=01+3=11+4=21+5=02+1=02+2=12+3=22+4=02+5=13+1=13+2=23+3=03+4=13+5=24+1=24+2=04+3=14+4=24+5=0 GF(4)內(nèi)加法,仿真結(jié)果如表5. 表5 GF(4)內(nèi)加法Tab.5 Addition in GF(4) GF(3)內(nèi)乘法,仿真結(jié)果如表6. 表6 GF(3)內(nèi)乘法Tab.6 Multiplication in GF(3) 文章在充分分析伽羅瓦域特點(diǎn)的基礎(chǔ)上,實(shí)現(xiàn)了伽羅瓦域上簡(jiǎn)單加法與乘法,算法簡(jiǎn)單明了.仿真結(jié)果表明,加法與乘法能夠在伽羅瓦域上得到很好的實(shí)現(xiàn). [1] Fournaris A P,Koufopavlou O.Versatile multiplier architectures in GF(2k) fields using the Montgomery multiplication algorithm[J].Integration,2008,41(3):371-384. [2] Lopez J,Dahab R.High-speed software multiplication in F2m[C]//Progress in Cryptology—indocrypt 2000.India Calcutta:Lecture Notes in Computer Science,2000:93-102. [3] Lidl R,Niederreiter H.Introduction to Finite Fields and Their Applications[M].2th ed.Cambridge:Cambridge University Press,1994:1-332. [4] 郭鑫,陳克非.求解本原多項(xiàng)式的快速算法[J].計(jì)算機(jī)工程,2008,34(15):146-147. [5] Lidl R,Niederreiter H.Finite Fields[M].2th ed.Cambridge:Cambridge University Press,1997:1-124. [6] 葉清貴.RS編譯碼的FPGA實(shí)現(xiàn)研究[D].上海:華東師范大學(xué)信息學(xué)院電子系,2006. SoftwareImplementationinGaloisFieldOperation CHEN Zhi-jiang,DONG Wen,JIA Zhong-yun (College of Information Science and Engineering,Hangzhou Normal University,Hangzhou 310036,China) Finite field is the considerable important basic knowledge of algebra in coding theory,so that the operation of finite field is obviously crucial.Through the researches on the characteristics of the finite field,this paper discussed the computer implementation of the addition and multiplication in a typical finite field GF (2nand 3n) (n∈N).The simulation results indicate that the addition and multiplication in typical finite field have been well implemented and have potential practical value. finite field; addition; multiplication 2010-03-06 浙江省教育廳科研基金項(xiàng)目(Y200908330). 陳志江(1986—),男,浙江紹興人,計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)碩士研究生,主要從事無線多煤體傳感器網(wǎng)絡(luò)研究. *通信作者:董 文(1969—),男,內(nèi)蒙古赤峰人,副教授,博士,主要從事無線傳感網(wǎng)絡(luò)研究.E-mail:dongwen69@163.com 10.3969/j.issn.1674-232X.2011.05.015 TP301.6 A 1674-232X(2011)05-0466-042 伽羅瓦域
3 GF(p)的運(yùn)算
4 GF(2n或3n)的運(yùn)算[6]
5 實(shí)驗(yàn)結(jié)果
Tab.4AdditioninGF(3)6 結(jié) 論
杭州師范大學(xué)學(xué)報(bào)(自然科學(xué)版)2011年5期