摘要
由于de Bruijn序列具有周期最大、元素分布均衡、线性复杂度较高等良好的伪随机性质,因此在序列密码的研究领域中占有重要位置,其中de Bruijn序列的构造问题一直是研究的热点问题之一.目前已有多种构造de Bruijn序列的方法,而对于构造所得de Bruijn序列的差异性则相对研究较少,本文主要讨论基于编织法得到的de Bruijn序列的差异性.基于编织法,高杨等人给出了一种由一条n级de Bruijn序列来构造四条2n级de Bruijn序列的方法.由于这四条2n级de Bruijn序列由两条编织序列I1和I2唯一决定,因此de Bruijn序列的差异性可由这两条编织序列的差异性来刻画,而这两条编织序列的差异性又可以转化为两个指定映射的差异性.映射的差异性问题进一步可归结为对n长状态(e0e2…e2n-2)来源序列的研究,最终本文得到两个映射出现差异的充要条件,进而得到这两个映射的差异数和差异率2(2^n-1+1)^-1.据此可知,由编织法构造的编织序列的差异率随着级数的增大而减少.
De Bruijn sequences have good pseudo-random properties,such as the maximum period,uniform element distribution and the higher linear complexity,hence they play a very important role in stream cipher,and their construction has always been one of hot research topics.Many methods of constructing de Bruijn sequences have been presented,however,few discussions are about the differences of the constructed de Bruijn sequences.This paper studies the differences of de Bruijn sequences generated by interleaving construction.Based on interleaving construction,four de Bruijn sequences of 2n-stage can be constructed from one de Bruijn sequence of n-stage by Gao et al.Since these de Bruijn sequences are uniquely determined by two interleaved sequences I1and I2,the difference of the former can be described by the difference of these two interleaved sequences,which can be transformed into the difference between two given mappings f(x)and g(x).Furthermore,the difference between these two mappings turns into the discussions of the source of the n-tuple state(e0e2···e2n-2).Finally,this paper gives a necessary and sufficient condition for x so that f(x)≠g(x)holds,the number of such x has been enumerated,and the difference rate 2(2^n-1+1)^-1can be drawn.It can be seen that the difference rate of interleaved sequences decreases with the increase of n.
作者
王向宇
王中孝
WANG Xiang-Yu;WANG Zhong-Xiao(Strategic Support Force Information Engineering University,Zhengzhou 450001,China)
出处
《密码学报》
CSCD
2020年第2期169-178,共10页
Journal of Cryptologic Research
基金
国家自然科学基金(61502524)。
关键词
de
Bruijn序列
编织法
编织序列
差异性
de Bruijn sequence
interleaving construction method
interleaved sequences
difference