不相交线性码的一种新构造

New Construction of Disjoint Linear Codes

不相交线性码在具有高非线性度的多输出弹性密码函数的构造中扮演着重要角色,如何快速高效地生成大量不相交线性码是一个重要的研究课题.本文提出一种构造不相交线性码的新方法,得到目前已知最多的不相交[n, k]线性码.该构造的计算量,特别是当n?k时,比现有的其他构造的计算量小很多.当k整除n时,借助一个k次本原多项式得到v个k×k的矩阵Mi,其中v=2k-1, i=0, 1,···, v-1.用这样的Mi和k阶单位阵及k阶零方阵组合便可生成全部的不相交[n, k]线性码.当k不整除n时,借助一个k次本原多项式得到v1个k×k的矩阵Mi,借助一个m次本原多项式得到v2个k×m的矩阵Mj′,其中m=n-uk, v1=2k-1, v2=2m-1, i=0, 1,···, v1-1,j=0, 1,···, v2-1, u=■n/k■-1.用这样的Mi, Mj′, k阶单位阵, k阶零方阵以及k×m的零矩阵组合便可生成大量的不相交n[n, k]线性码.此时,生成不相交[n, k]线性码的个数比■(2n-1)/(2k-1)■少2m-k-1.

Disjoint linear codes play an important role in the construction of multiple output resilient cryptographic functions with high nonlinearity.How to generate a large number of disjoint linear codes quickly and effectively is an important research topic.In this paper,a new construction of disjoint linear codes is presented.It can generate a set of disjoint[n,k]linear codes with currently best known cardinality.The computational cost of this construction is much smaller than that of other known constructions,especially when n?k.When n is a multiple of k,it gets v matrices Mi of order k×k by means of only one primitive polynomial of k,where v=2k-1,i=0,1,···,v-1.Combining such Mi with identity matrix of order k×k and null matrix of order k×k,all the disjoint[n,k]linear codes can be generated.When n is not a multiple of k,it gets v1 matrices Mi of order k×k by means of one primitive polynomial of k and v2 matrices Mj′of order k×m by means of one primitive polynomial of m,where m=n-uk,v1=2k-1,v2=2m-1,i=0,1,···,v1-1,j=0,1,···,v2-1,u=■n/k■-1.Combining with such Mi,Mj′,identity matrix of order k×k,null matrix of k×k and null matrix of order k×m,a large number of[n,k]disjoint linear codes can be generated,and the number of the ngenerated disjoint[n,k]linear codes is 2m-k-1 less than■(2n-1)/(2k-1)■.