求k=minerror(a)时的k错线性复杂度的新算法

摘要:本文在学习了 和 的一个计算k错线性复杂度的算法之后,给出了一个求错误重量为 时的 错线性复杂度,即线性复杂度首次降低时所降到的值的新的算法。该算法可以节约存储空间和运算步骤。

关键词:二元 周期序列 线性复杂度 错线性复杂度

中图分类号:文献标识码:A文章编号:1007-9416(2010)05-0000-00

定理2.1:上述算法是正确的。

证明:如果 大于等于序列的重量,显然 错复杂度为0.反之,原始序列加上对应的严格错误序列的线性复杂度就是所求的 错线性复杂度,且非0,这时根据 算法的分析,最后一步需要对 加1.

算法中的量 的意义在于:当我们使得序列的左右两部分 和 相同时,就只考虑其中的一部分,如 .但实际中的严格错误序列也应左右两部分相同,总共的重量应是这两部分所需改变的和,也就是其中一部分的2倍,所以算法中需要 ,而所需改变的位置的总个数应是tT.

上述算法最大的特点就是不必使用已有算法中的 向量,而采用了一个新的运算符号*,*表示对应位置可以取0,也可以取1,这意味着我们需要改变 或 的值,但不能确定要改变哪一个,需要根据后面的要求来判断,即使得最终的线性复杂度尽量的小。当

时,可以使得 为零序列(这意味着线性复杂度可以降低)时, 中的*应取 中对应位置的值,反之亦然。而当 和 对应位置同时为*时,*可以同时取0,也可以同时取1,需要后面条件来判断,新的序列 对应位置仍取*.

根据上面分析的结果,参考文献[5]中定理5.1的证明过程,我们就可以证明上述算法是正确的。证毕。

上面给出的算法也是经过 次循环,计算复杂度的方式与文献[5]中是一样的。那么这个算法与已有算法的最大区别是:不需要其它算法中不可或缺的 向量。文献[5][6][7]中的算法都需要 个变量 来存储对应位置上的改变量,而这些算法的主要运算和存储主要就是 向量,所以我们的算法相比已有算法来说可以节省一半以上的存储空间和运算。因为我们比较关心的就是序列的线性复杂度首次降低的大小,所以上面给出的算法有很强的应用价值。

参考文献

[1] 丁存生,肖国镇.流密码学及其应用.国防工业出版社.1994.

[2] 孙淑玲.应用密码学.北京:清华大学出版社.2004.

[3] 胡予濮,张玉清,肖国镇.对称密码学.北京:机械工业出版社.2002.

[4] K.Kurosawa,F.Sato,and W.Kishimoto, ”A relationship between linear complexity and k-error linear complexity”. IEEE Transactions on Information Theory, vol.46,NO.2, 2000,pp.694-698.

[5] M.Stamp,C.F.Martin, ”An algorithm for the k-error linear complexity of binary sequences with period 2n”. IEEE Transactions on Information Theory,vol.39,NO.4,1993,pp.1398-1401.

[6] A.Lauder and K.paterson, “Computing the error linear complexity spectrum of a binary sequence with period 2n”. IEEE Transactions on Information Theory, vol.19,NO.1,1973,pp.101-110.

[7] A.Sǎlǎgean, “On the computation ofthe linear complexity and the k-error linear complexity of a binary sequence with period a power of two ”. IEEE Transactions on Information Theory, vol.51,NO.3,2005,pp.1145-1150.

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文