gfpm上周期为pn序列的m紧错线性复杂度new

《gfpm上周期为pn序列的m紧错线性复杂度new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第27卷第9期2010年9月计算机应用研究ApplicationResearchofComputemV01．27No．9Sep．2010GF(Pm)上周期为P仃序列的m紧错线性复杂度周建钦k2，熊微2(1．上海市信息安全综合管理技术研究重点实验室，上海200240；2．杭州电子科技大学通信工程学院，杭州310018)摘要：综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror(S)的概念，提出紧错线性复杂度的概念。在GF(p4)上周期为P8序列的k错线性复杂度快速算法的基础上，给出m紧错线性

2、复杂度的快速算法。其中P是素数。编程实现了该算法，并给出实验结果。关键词：流密码：周期序列；线性复杂度；k错线性复杂度；紧错线性复杂度中图分类号：TN911；TN918．1文献标志码：A文章编号：1001-3695(2010)09-3542-03doi：10．3969／j．issn．1001-3695．2010．09．093m。tighterrorlinearcomplexityofsequencesoverGF(pm)withperiodP“ZHOUJian．qinl'-．XIONGWei2(1．ShanghaiKey

3、LaboratoryofIntegrateAdministrationTechnologiesforInformationSecurity，Shanghai200240，China；2．SchoolofTeleeor,vmunication；Hangz．houDianziUniversity，Hangzhou310018，China)Abstract：Usingthetheoriesoflinearcomplexity，k-errorlinearcomplexity，thek-errorlinearcomplexityp

4、rofileandthemi-nimumerror，thispaperpresentedthenotionofm-tighterrorlinearcomplexity．Moreover，gaveallefficientalgorithmforcom-putingm—tighterrorlinearcomplexitybasedonthealgorithmforcomputingk-errorlinearcomplexityofsequencesoverGF(p“)withperiodP“，wherePwasaprime．

5、ItrealizedtheproposedalgorithmwithClanguage，andalsogavetheexperimentresultshere．Keywords：sh'eamcipher；periodicsequence；linearcomplexity；k-errorlinearcomplexity；tighterl"orlinearcomplexity密钥序列的线性复杂度是流密码强度的一个重要度量指标，但是高线性复杂度并不一定能保证序列是安全的。例如一n个周期为凡的二元序列S=瓦贰?≯，1，其线性复杂

6、度为n，但只要将最后一位1变为0，该序列的线性复杂度就降为O。这样序列的线性复杂度是极其不稳定的，用来作为密钥序列也不安全。因此，序列的线性复杂度的稳定性与序列的不可预测性密切相关，密钥序列的线性复杂度不仅要足够大，而且必须有很好的稳定性。Ding等人【11最早注意到这个问题，因而率先创立了流密码的稳定性理论，并提出了重量复杂度、球体复杂度等流密码稳定性度量指标。随后，Stamp等人旧1也引入了类似球体复杂度的线性复杂度稳定性度鼍指标，即克错线性复杂度，同时给出了k错线性复杂度曲线的概念。改变序列的一个周期中至多k位后得

7、到的最小线性复杂度，称为k错线性复杂度。任何一个序列的后错线性复杂度也可以反复运用B·M算法计算出来，但为了计算周期为Ⅳ的二元序列的k错线性复‘，^，，杂度，要把这个算法运用乏f：’1次。对于周期为N的二元序J2”、，／列，虽然已有了一些特殊周期序列线性复杂度的快速算法，但如果没有一个有效的算法来计算k错线性复杂度，也得将这■，^，、些快速算法运用乏fi’1次。即使N和．i}不是太大，计算量也’。”、J／是相当大的。在Games．Chan¨]算法的基础上，Stamp等人晗1提出一个确定周期为2“的二元序列的k错线性复杂度

8、的快速算法，使得人们对线性复杂度的研究有了新的重要进展，很快就得到了大量的推广。Kaida等人H1提出了一个确定GF(p“)上周期为P“的序列的k错线性复杂度的算法。Kurosawa等人呤1引入了最小错误minerror(S)(S为二元序列)的概念来描述周期为2“的二元序列的线性复杂度的稳定性，将其定义为使得序列线性