一類三重循環(huán)碼及其重量分布

劉芳蕊，范翠玲

(西南交通大學 數(shù)學學院，成都 610031)

假設(shè)p是一個素數(shù)，有限域GF(p)上的[n,k,d]線性碼是n維向量空間GF(p)n中的一個k維線性子空間，其中非零向量漢明重量的最小值為d。若有限域GF(p)上的[n,k,d]線性碼C，滿足(c0,c1,…,cn-1)∈C?(cn-1,c0,c1,…,cn-2)∈C，則稱C為循環(huán)碼。若將任意向量(c0,c1,…,cn-1)∈GF(p)n等價地表示為多項式的形式，即c0+c1x+c2x2+…+cn-1xn-1∈GF(p)[x]/(xn-1)，則任意有限域GF(p)上長度為n的線性碼C對應(yīng)于商環(huán)GF(p)[x]/(xn-1)中的一個子集，線性碼C是循環(huán)碼當且僅當GF(p)[x]/(xn-1)中對應(yīng)的子集是商環(huán)GF(p)[x]/(xn-1)的一個理想。眾所周知，GF(p)[x]/(xn-1)的每一個理想都是主理想。假設(shè)C=〈g(x)〉是一個循環(huán)碼，其中多項式g(x)是首一的且是C的所有生成元中次數(shù)最小的，則g(x)是唯一的并稱它為生成多項式，稱h(x)=(xn-1)/g(x)為C的校驗多項式。若有限域GF(p)上長度為n的循環(huán)碼C的校驗多項式h(x)為GF(p)上t個不同的不可約多項式的乘積，則稱對偶碼C⊥有t個零因子。

令A(yù)i表示長度為n且漢明重量為i的碼C的碼字個數(shù)，那么碼C的重量計數(shù)器定義為如下表達式：1+A1y+A2y2+…+Anyn。重量分布A0,A1,…,An是編碼理論中一個重要的研究課題，它不僅包含用來估計糾錯能力的重要信息，還可以計算在一些算法下檢錯和糾錯的出錯概率[1]。另外，循環(huán)碼具有豐富的代數(shù)結(jié)構(gòu)，因此重量分布在數(shù)論上是一個有趣且具有挑戰(zhàn)性的問題。循環(huán)碼具有高效的編譯碼算法，因此被廣泛應(yīng)用于消費電子、數(shù)據(jù)傳輸技術(shù)、廣播系統(tǒng)和計算機應(yīng)用等領(lǐng)域。此外，具有較少重量的循環(huán)碼在認證碼里有著重要的應(yīng)用，可以很容易地計算出由這些循環(huán)碼構(gòu)造的認證碼的參數(shù)[2]。同時，具有較少重量的循環(huán)碼在密鑰共享方案也有著重要的應(yīng)用，可以很容易確定由這樣的循環(huán)碼生成的秘密共享方案的訪問結(jié)構(gòu)[3-5]。具有較少重量的循環(huán)碼在跳頻序列的設(shè)計中有著特殊的應(yīng)用[6-7]，三重循環(huán)碼在聯(lián)合方案也有應(yīng)用[8]。因此，研究具有較少重量循環(huán)碼是十分具有價值的工作。

本文提出了一類新型p元(p是一個奇素數(shù))三重循環(huán)碼，它的對偶碼有2個零因子，并利用指數(shù)和理論完全確定了這類循環(huán)碼的重量分布，證明了其中一些循環(huán)碼是最優(yōu)的。

1 符號和定義

2 對偶碼有2個零因子的循環(huán)碼

給定正整數(shù)m，q=pm且n=q-1，令α是乘法群GF(q)*的1個生成元，對于任意的0≤a≤q-2，將α-a在GF(p)上的極小多項式記為ma(x)。

假設(shè)0≤u≤q-2和0≤v≤q-2是任意2個滿足Cu∩Cv=?的整數(shù)。C(u,v,p,m)表示GF(p)上長度為n，碼字為

c(a,b)=(c1,c2,…,cn),?(a,b)∈GF(p)×GF(p)

(1)

3 一些已知的三重循環(huán)碼

Carlet等[3]和Yuan等[21]采用一些特殊的單項式構(gòu)造了一些循環(huán)碼并證明了以下定理。

定理1假設(shè)m≥3為奇數(shù)且p為奇素數(shù)，當v=(ph+1)/2，p=3，gcd(m,h)=1且h是奇數(shù)，或者v=ph+1時，則碼C(1,v,p,m)是一個三重[pm-1,2m]循環(huán)碼，其重量分布如表1所示。當m是偶數(shù)，定理1中由單項式xv定義的循環(huán)碼C(1,v,p,m)有5個非零重量。關(guān)于定理1中三重循環(huán)碼的對偶碼的信息，讀者可以參考文獻[3]。

表1 重量分布1

Luo和Feng[22]擴展了定理1中的第一個構(gòu)造并且證明了以下定理。

定理2假設(shè)m≥3是奇數(shù)且p是奇素數(shù)，如果v=(ph+1)/2，其中h是一個滿足gcd(2m,h)=1的整數(shù)，那么碼C(1,v,p,m)是一個三重[pm-1,2m]循環(huán)碼，其重量分布如表2所示。

表2 重量分布2

文獻[23-24]中介紹了幾類三重非二元循環(huán)碼，本文不需要這些碼的重量分布公式，因此不再贅述。同樣地，本文僅考慮三重非二元循環(huán)碼，不會涉及引用三重二元循環(huán)碼。

4 一類三重循環(huán)碼及其重量分布

本節(jié)將提出一類定義在有限域GF(p)上的三重循環(huán)碼C(u,v,p,m)，其中u=1，v是使得Cv∩C1=?且lv=m的整數(shù)。容易驗證，循環(huán)碼C(1,v,p,m)的長度為q-1，維數(shù)為2n。

4.1 引理

首先介紹2個有限域上指數(shù)和的引理。

表3 指數(shù)和的值分布

證明根據(jù)S(a,b)的定義，可得

=-q+p+(q-1-Wa,b)p

=(p-1)q+pWa,b

(2)

表4 指數(shù)和的值分布

證明當h是偶數(shù)時，結(jié)論在文獻[20]中的定理3.4中已證?，F(xiàn)假設(shè)h是奇數(shù)，則在GF(p)中存在一個非平方元λ滿足λ(ph-1)/2=-1，根據(jù)R(a,b)的定義，可得

(3)

(4)

根據(jù)式(3)和(4)可得：

=2(p-1)q+2pWa,b，

(5)

根據(jù)指數(shù)和的理論，循環(huán)碼C(1,v,p,m)中的一個碼字c(a,b)的漢明重量wt(c(a,b))可表示為：

(6)

其中，對每一組(a,b)∈GF(p)2，

(7)

對于給定的v，在本節(jié)中出現(xiàn)的函數(shù)Tv(a,b)均為(7)所定義的指數(shù)和。

下面的引理將用于下文中確定本文提出的一類循環(huán)碼的重量分布。

引理3設(shè)s為滿足gcd(q-1,s)=2的任意整數(shù)，則

其中λ為GF(p)*中任意給定的非平方元。

(8)

顯然，gcd(q-1,s)=2。當x遍歷GF(q)時，xs將遍歷GF(q)中的非零平方元2次，且僅0出現(xiàn)1次。類似地，λx將遍歷GF(q)中的非平方元2次，且0僅出現(xiàn)1次。引理3的結(jié)論由(8)得。

4.2 一類三重循環(huán)碼

下面的定理為本文主要結(jié)果。

定理3假設(shè)m為奇數(shù)，p=5且v=(5m-1)/4+(5(m+1)/2-1)/2。碼C(1,v,p,m)是一個GF(5)上參數(shù)為[5m-1,2m]的循環(huán)碼且其重量分布如表2所示。

證明假設(shè)h=(m+1)/2且s=5h-1。因為m為奇數(shù)，所以gcd(s,pm-1)=2。容易驗證，v為奇數(shù)且sv≡2(mod 5m-1)。令λ=2為GF(pm)上的一個非平方元，則2v≡-2(modp)。根據(jù)引理3，有：

(9)

由(6)式和(9)式可得：

(10)

碼C(1,v,5,m)的重量分布可由式(10)和引理2直接得到。

例1 假設(shè)p=5,m=3且v=43，則C(1,v,p,m)是GF(5)上的一個參數(shù)為[124,6,90]的循環(huán)碼，重量計數(shù)器為1+3720y90+9424y100+2480y110。

例2 令p=5,m=3且v=483，則C(1,v,p,m)是GF(5)上的一個參數(shù)為[3124,10,2450]的循環(huán)碼，重量計數(shù)器為1+2030600y2450+5860624y2500+1874400y2550。

5 三重循環(huán)碼在密鑰共享中的應(yīng)用

密鑰共享是密碼學中一個有趣的課題。在一個密鑰共享方案中，管理者將創(chuàng)建一個密鑰，以便在一組參與者之間共享。管理者將計算每個參與者共享的密鑰，并分發(fā)給所有參與者。一些參與者能夠在合并他們的密鑰后恢復整個密鑰，而一些參與者將無法恢復。本節(jié)將研究基于本文中提出的三重碼的密鑰共享方案。

5.1 一種基于線性碼的密鑰共享方案

設(shè)G=[g0,g1,…,gn-1]是GF(p)上的一個[n,k,d]線性碼C的生成矩陣。本節(jié)中提到的所有線性碼，假設(shè)沒有任何生成矩陣的列向量是零向量。利用線性碼構(gòu)造密鑰共享方案如下：

1)密鑰和參與者：在由線性碼C構(gòu)建的密鑰共享方案中，密鑰是GF(p)的一個元素，有n-1個參與者P1,P2,…,Pn-1和一個管理者。

2)共享密鑰的計算和分配：為了計算關(guān)于密鑰s的共享密鑰，管理者隨機選擇一個向量u=(u0,…,uk-1)∈GF(p)k，使得s=ug0，GF(p)k中一共有pk-1個向量u∈GF(p)k。然后管理者將u視為一個信息向量，并計算相應(yīng)的碼字t=(t0,t1,…,tn-1)=uG。最后，對于每個i≥1，把ti交給參與者Pi作為共享密鑰。

3)恢復密鑰：注意到t0=ug0=s，一組共享密鑰{ti1,ti2,…,tim}確定這個密鑰當且僅當g0是gi1,…,gim的線性組合。

下面的引理表明了哪些參與者可以恢復密鑰[5]。

引理4設(shè)G是GF(p)上[n,k]碼C的生成矩陣。在基于C的密鑰共享方案中，一組共享密鑰{ti1,ti2,…,tim}可以確定這個密鑰當且僅當對偶碼C⊥中有一個碼字

(1,0,…,0,ci1,0,…,0,cim,0,…,0),

(11)

其中至少存在一個j使得cij≠0，1≤i2<…

若一組參與者可以通過組合他們的共享密鑰來恢復該密鑰，則包含該組的任何一組參與者也可以恢復該密鑰。若一組參與者可以用他們的共享密鑰來恢復該密鑰，但其任何真子集的共享密鑰的組合都不能恢復該密鑰，則他們被稱為最小訪問集。此處的一組參與者的一個真子集的包含的成員更少。因此，僅需研究最小訪問集，要確定這個集合，需要定義最小碼字。

一個向量c∈GF(p)n的支撐集定義為{0≤i≤n-1:ci≠0}。如果c2的支撐集包含c1支撐集，則碼字c2包含碼字c1。若一個非零碼字c只覆蓋它的倍數(shù)，但不覆蓋其他的非零碼字，則稱它為最小碼字。若最小碼字的第一個坐標為1，則稱為最小AS碼字。

根據(jù)引理4和上面的討論，最小訪問集和對偶碼C⊥的最小AS碼字集之間存在一一對應(yīng)關(guān)系。為了確定密鑰共享方案的訪問結(jié)構(gòu)，只需要確定最小AS碼字集，即所有最小碼字集的一個子集。然而幾乎在每一種情況下，只要能夠確定最小AS碼字的集合，就應(yīng)該能夠確定所有最小碼字的集合。

參與者的共享密鑰取決于碼C的生成矩陣G的選擇。根據(jù)引理4，G的選擇并不影響密鑰共享方案的訪問結(jié)構(gòu)。因此，下文將稱之為基于C的密鑰共享方案，而不提及用于計算共享密鑰的生成矩陣。

5.2 基于特殊線性碼的密鑰共享方案的訪問結(jié)構(gòu)

定理4[5]設(shè)C是GF(p)上的一個[n，k]碼，并設(shè)G=[g0,g1,…,gn-1]是它的生成矩陣。若C的每個非零碼字都是一個最小向量，則在基于C⊥的密鑰共享方案中，一共有pk-1個最小訪問集。此外，有以下結(jié)論：1)若gi是g0的倍數(shù)，其中1≤i≤n-1，則參與者Pi必定在每一個最小訪問集中。這樣的參與者稱為獨裁者；2)若gi不是g0的倍數(shù)，其中1≤i≤n-1，則參與者Pi必定在pk-1個最小訪問集的(p-1)pk-2個中。

根據(jù)定理4，若對于一類碼的每一個非零碼字都是一個最小向量，則研究這一類碼的構(gòu)造是一個有意義的工作。由這類線性碼給出了一個密鑰共享方案，并且這一密鑰共享方案具有定理4中描述的較好的訪問結(jié)構(gòu)。

若一個線性碼的任意兩個非零碼字的重量足夠接近，則這一個碼的每一個非零碼字都是極小的。下面的引理說明了這一性質(zhì)。

5.3 本文中的線性碼構(gòu)造的密鑰共享方案的訪問結(jié)構(gòu)

引理6在本文構(gòu)造的循環(huán)碼C(1,v,p,m)中，每一個非零碼字都是極小的。

證明本文中提出的循環(huán)碼C(1,v,p,m)具有參數(shù)[pm-1,2m]，且其重量分布如表2所示，其中p≥3。

若碼的重量分布如表2所示且m≥3，則類似地可以驗證如下的不等式成立：

由引理5，引理結(jié)論得證。

證明根據(jù)引理4和引理5，本定理的結(jié)論得證。

對于本文中提出的許多循環(huán)碼，其素數(shù)p為5，導致空間p太小。在實際應(yīng)用中，一個密鑰空間應(yīng)盡可能大。使用本文提出的碼所構(gòu)造的密鑰共享方案，利用編碼的規(guī)則將密鑰空間中的每個元素編碼為GF(p)上元素構(gòu)成的一個序列，然后參與者依次共享序列中的每一個元素。