多个序列最短线性移位寄存器综合的迭代算法

近十几年来,多个序列最短线性移位寄存器综合问题,在信息论和控制论中为许多学者所关心和重视,但至今没有很好的算法。本文给出了解决这个问题的迭代算法,并证明了所求得的线性移位寄存器确实是产生多个序列的最短线性移位寄存器。此外,本文还给出最短线性移位寄存器唯一性的充要条件,以及在不唯一的情况下产生多个序列的所有最短线性移位寄存器集合.当t为1时,本文的算法就是著名的Berlekamp-Massey迭代算法。     

前馈序列与反馈序列的关系

本文引入移位寄存器序列的向量值表示讨论了线性移位寄存器的前馈序列与反馈序列同时为ｍ序列时的关系,得到了它们在向量值表示下的一个关系式。     

关于m序列的互相关函数

m 序列由于它的伪随机性,其中特别是它的自相关函数“接近”于 Delta 函数,使得它在跟踪、测量、数字通信等无线电技术中受到重视.根据无线电信号的检测理论,信号经过恒参、线性信道中的传播并在加性白色高斯噪声背底下的提取是提取它的自相关函数,以在接收端获取最大的信噪比,常采用匹配滤波技术来实现.为了提高信道的利用率,在同一无线电系统中可以采用一个以上的 m 序列信号,这样     

递归构造多个具有最优代数免疫度的平衡布尔函数

代数免疫度是针对代数攻击而提出来的一个新的密码学概念.要能够有效地抵抗代数攻击,密码系统中使用的布尔函数必须具有平衡性、较高的代数次数、较高的非线性度和较高的代数免疫度等.为了提高布尔函数的密码学性能,通过布尔函数仿射等价的方法,找出了所有具有最优代数免疫度的三变元布尔函数.由这些具有最优代数免疫度的三变元非线性布尔函数,递归构造了一类代数免疫度最优、代数次数较高的平衡布尔函数.给出了这类布尔函数非线性度的一个下界,偶数变元时,其下界严格大于Lobanov给出的下界.     

相关免疫函数阶的判别方法

在密码学中,为了抵抗相关攻击,要求选用的布尔函数具有相关免疫性,高阶的相关免疫函数都是一阶的,一阶的却不一定是高阶的,本文给出了二种判断一阶相关免疫函数是否为二阶或更高阶的新方法.     

产生 M 序列的一个递推算法

§1.引言M 序列又称 de Bruijn 序列,是一类具有最长周期的非线性移位寄存器序列。本文研究产生 M 序列的算法。早在70年代万哲先等对构造 M 序列的方法已有系统的研究。此后有一系列的文章研究 M 序列的构造问题。最近 Fredricksen 对这方面的工作给出了一个很好的综述。产生 M 序列的一个常用方法是先由一个较简单的移位寄存器产生许多短圈,再用并圈法将这些短圈合并起来构成 M 序列。如在[1,6]中就已给出过一些将 n 级纯轮换移位寄存器(简记为 PCK_n)和 n 级补轮换移位寄存器(简记为 CCR_n)产生的圈合并为 M 序列的方法。与[1—7]不同,Fredricksen 给出一个将 PCR_n 产生的圈合并为 M 序列的递推算法。最近 Etzion 和 Lempe 在 Fredricksen 算法的基础     

代数免疫度为1的布尔函数

布尔函数的代数免疫度是在流密码的代数攻击中所产生的重要概念.研究了代数免疫度为1的布尔函数,得到的主要结果有:对代数免疫度为1的布尔函数给出了一个谱刻画,给出了其个数的精确计数公式,最后给出了此类函数的非线性度的紧的上界.     

m序列的移位相减性

ｍ序列是一类最重要的线性移位寄存器序列．文献［１］证明了移位相加是２元ｍ序列的特有性质，本文证明了任意的ｑ元ｍ的序列都具有移位相减性，并说明了移位相加是移位相减的特例。     

多重序列线性移位寄存器综合的Euclidean算法

给定多重序列,求产生它们的最短线性移位寄存器在超过BCH限的循环码译码及控制论中向量输入输出图部分实现中都具有十分重要的应用.本文引进了解决这个问题的Euclidean算法,还导出这个问题的解是唯一的充要条件,如果问题的解不是唯一时,本文还给出产生给定多重序列的所有的最短线性移位寄存器集合.当本文的算法用于单个序列.这就是Sugiyama等人提出的算法.     

相关攻击与相关免疫函数

本文首先介绍了如何采用ＤＣ攻击法对一类流密码体制进行相关攻击，从而说明在密码学中有必要研究相关免疫（ＣＩ）函数。在综述了域Ｆ２上相关免疫（ＣＩ）函数的研究进展的同时，给出了ＣＩ函数在一般有限域上的特性和构造，并进一步研究有限环Ｚ／（ｍ）时的情景，本文详尽描述了ＣＩ函数的五种充要条件。最后提出了几个值得研究的未解决的问题。     

布尔函数的迹Walsh谱

布尔函数线性Walsh谱和高阶Walsh谱的研究对构造能够抵抗线性逼近攻击和二次或较高次逼近攻击的密码函数发挥了重要作用.为了抵抗采样攻击,提出了布尔函数迹Walsh谱和迹Walsh循环谱概念,并给出该Walsh谱的一些简单性质.利用这一谱值的分布特性,可以很好地分析布尔函数的迹函数逼近问题,对序列密码采样攻击研究具有重要意义.     

关于“停走”生成器概率模型中的符合率问题

本文首先建立了“停走”生成器辅出序列的概率模型,给出了“停走”生成器输出序列与其线性移位寄存器序列之间的符合率的计算公式。     

一种生成k元de Bruijn序列的算法

目前,已有很多生成全长的移位寄存器序列(又称de Bruijn序列)的方法,他们的共同思想是先通过某种简单的移位寄存器生成所有不同的圈,然后再把它们联接为一个全长圈。在这篇文章中,我们先定义一个项链的周期约化,进而提出一种新的生成任意k元de Bruijn序列的方法。这种方法把这类算法从域推广到整数模上,而且在n≥3和k≥4时,这种算法能生成一大批de Bruijn序列。     

环Z2l上广义Bent函数的稳定性

文献「４」为研究密钥流序列的线性复杂度稳定性和使一些流密码能抗ＢＡＡ（最佳仿射逼近）攻击,提出Ｂｅｎｔ函数稳定性概念,文献「７」研究了素域Ｚｐ上广义Ｂｅｎｔ函数的稳定性及其构造,并指出当ｍ是合数时,ｍ值广义Ｂｅｎｔ函数并不都有稳定性,本文进一步在环Ｚ２＾ｌ（ｌ〉１）上提出了广义Ｂｅｎｔ函数稳定性的概念,综合应用谱、概率和代数数论的方法考察了稳定的概率意义,给出了稳定函数的概率判别条件,提供了构造稳     

M序列自相关系数的递推算法

一、前言 伪随机序列是一类有着广泛应用的伪随机码.在数字通讯、测距及跟踪系统中常用其来调制信号,以达到提高可靠性与有效性以及保密等目的.最常用的一类伪随机码则是由移位寄存器产生的序列.对于线性的情形,已有比较完整的结果,而对于非线性情形,则要复杂得多.目前,讨论得最多而用途最广的是所谓最长的序列,即M序列. 在我们的工作中,已经证明了,凡满足下述两条件:     

带时滞观测线性离散系统的递推滤波

本文讨论带时滞观测线性离散系统的滤波问题,提出利用联合分布函数,得到滤波递推格式.这种方法还适用于一般的带有状态时滞的线性离散系统.     

M 序列反馈函数的构造方法Ⅱ

构造 F_2上的 M 序列(即最大长度非线性移位寄存器序列)及其反馈函数在理论上已有比较完整的方法,但在目前有限的计算能力下,人们仍难以获得足够多的 M 序列,我们在[1]中,提出了一种比较简单的方法,用这种方法,可从任一非奇 n 元布尔函数出发直接写出一批 M 序列反馈函数(简称 M 馈):本文沿用[1]的记号和概念,继续讨论 M 馈的构造方法.     

M 序列反馈函数的构造方法Ⅲ

二元域 F_2上周期为2~n 的 n 级 M 序列(即最大长度移位寄存器序列)具有较好的随机性.实际构造这种序列及其反馈函数(简称 M 馈)历来很受重视.近几年来,人们试图从一线性移位寄存器出发来构造 M 馈.利用一个 n 次本原多项式,J.Mykkeltveit 等人构造了2~n-2个 n+1级 M 馈,M.K.siu 与 P.Tong 构造出2~(n+1)个 n+2级 M 馈,F.Hemmati 又构造出2~(5n)个 n+2级 M 馈.B.Arozi 用两个次数分别为 m_1和 m_2的本原多项式构造出一个 m_1+m_2级 M 馈,其中(m_1,m_2)=1.我们在[1]和[2]中提供了几种直接构造 M 馈的方法,从任一非奇异移存器出发,可以直接写出一大批 M 馈.本文是[1]和[2]的继续,通过对几类线性移存器因子关联图的详细分析,构造出几类新的 M 馈.在§2中,用两个互反的 n 次本原多项式构造出2~(?)(2~(n-2)-     

分式线性函数的亚纯迭代根

迭代根问题是嵌入流的一个弱问题.关于单调函数的迭代根已有较多结论.但是对非单调函数迭代根的研究却很困难的.分式线性函数是一类实数域上的非单调函数．本文对复平面上分式线性函数的迭代根进行了研究.将分式线性函数的迭代函数方程与一个商空间上的矩阵方程对应,并运用一个求解矩阵根的方法,得到其所有亚纯迭代根的一般公式.并且确定了不同情形下分式线性函数迭代根的准确数目. 作为应用,分别给出了函数$z$和函数$1/z$全部亚纯迭代根.     

基于函数arccos(px+q)变换的灰色预测模型研究

借助于函数变换理论和灰色系统建模理论,并结合反余弦函数和线性函数的特点,提出了反余弦函数和线性函数相结合的变换方法并建立了一个改进的GM(1,1)模型.证明了这种变换一方面能提高序列的光滑比并压缩序列的级比;另一方面可以使还原误差减小.具体算例结果表明,经过反余弦函数和线性函数相结合建立的改进GM(1,1)模型的拟合精度优于传统GM(1,1)模型和基于反余弦函数变换的GM(1,1)模型的拟合精度.