2pn周期二元序列稳定性的进一步分析

序列的线性复杂度与k错线性复杂度是度量密钥序列伪随机性的两个重要指标。在p(p>3)为奇素数且2是模p2本原根的情况下, 对于周期为2pn的二元序列,文章进一步分析了满足k错线性复杂度严格小于序列复杂度的k的最小值的上界,并指出当周期为2p(p>3)时,在大多数情况下可以达到该上界。     

多重周期序列联合线性复杂度及其快速算法

周期序列的线性复杂度是衡量流密码系统安全性能的一个重要指标。近几年人们注重对多重周期序列的联合线性复杂度的研究。该文给出了Fp上周期为Pn的多重周期序列联合线性复杂度的一个新的表达式，介绍了周期为Pn的随机多重周期序列联合线性复杂度分布的计算方法，提出了一种周期为Pn的多重周期序列联合线性复杂度的快速算法。     

周期为p≡7(mod 8)的一类新六次剩余序列的迹表示

构造了一类新的周期为素数 的六次剩余序列,利用有限域和差集理论给出了该序列在周期为素数 情形下的迹函数表示.新序列的线性复杂度为 ,优于Hall六次剩余序列在相同条件下的线性复杂度.     

周期为p 7(mod 8)的一类新六次剩余序列的迹表示

构造了一类新的周期为素数 的六次剩余序列,利用有限域和差集理论给出了该序列在周期为素数 情形下的迹函数表示。新序列的线性复杂度为 ,优于Hall六次剩余序列在相同条件下的线性复杂度。     

一类新的六次剩余序列的线性复杂度

本文构造了一类新的六次剩余序列,给出了该类序列的特征多项式和线性复杂度。结果表明该类序列具有较好的线性复杂度性质。     

Trace representation of some generalized cyclotomic sequences of length pq

This paper contributes to trace representation of some generalized cyclotomic sequences of length which are defined by Ding and Helleseth. From the relations between these sequences and the Legendre sequence, we firstly confirm the defining pairs of these sequences of arbitrary order. Then, we obtain their trace representation, from which we give their linear complexity using Key’s method. It can be seen that Bai et al.’s conclusion is a special case of our result when the order is two. Finally, an example is given to illustrate the validity of our result.     

Strategic attack on the shrinking generator

The shrinking generator is a simple keystream generator with applications in stream ciphers, which is still considered as a secure generator. This work shows that, in order to cryptanalyze it, fewer intercepted bits than indicated by the linear complexity are necessary. Indeed, whereas the linear complexity of shrunken sequences is between A⋅2^(S−2)$A\cdot 2^{(S-2)}$ and A⋅2^(S−1)$A\cdot 2^{(S-1)}$, we claim that the initial states of both component registers are easily computed with fewer than A⋅S$A\cdot S$ shrunken bits located at particular positions. Such a result is proven thanks to the definition of shrunken sequences as interleaved sequences. Consequently, it is conjectured that this statement can be extended to all interleaved sequences. Furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which must be considered as a proof of weakness of interleaved generators.     

On probabilistic n-ary hypergroups

The T-fuzzy n-ary subhypergroups of an n-ary hypergroup are defined by using triangular norms and some related properties are hence obtained. In particular, we consider the probabilistic version of n-ary hypergroups by using random sets and show that the fuzzy n-ary hypergroups defined by triangular norms are consequences of some probabilistic n-ary hypergroups under certain conditions. Some results on n-ary hypergroups recently given by Davvaz and Corsini are extended.     

Extended Games–Chan algorithm for the 2-adic complexity of FCSR-sequences

Binary sequences generated by feedback shift registers with carry operation (FCSR) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. We present an FCSR analog of the (extended) Games–Chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length T = 2ⁿ or pⁿ, where p is an odd prime and 2 is a primitive element modulo p². The algorithm to be presented yields an upper bound for the 2-adic complexity, an FCSR analog of the linear complexity, of a pⁿ-periodic binary sequence.     

计算p^n-周期二元序列的最小错线性复杂度新算法

传统的计算序列k-错线性复杂度的算法,每一步都要计算和存储序列改变的代价,基于节省计算量和存储空间的考虑,提出了一种计算周期为pn的二元序列的最小错线性复杂度的新算法,其中p为素数,2为模p2的一个本原根。新算法省去了序列代价的存储和计算,主要研究在k为最小错,即使得序列线性复杂度第一次下降的k值时,序列线性复杂度的计算方法,给出了理论证明,并用穷举法与传统算法对序列的计算结果进行了比对。结果完全一致且比传统算法节省了一半以上的存储空间和计算时间,是一种有效的研究特殊周期序列稳定性的计算方法。     

Fuzzy -ary polygroups related to fuzzy points

Recently, fuzzy n-ary sub-polygroups were introduced and studied by Davvaz, Corsini and Leoreanu-Fotea [B. Davvaz, P. Corsini, V. Leoreanu-Fotea, Fuzzy n-ary sub-polygroups, Comput. Math. Appl. 57 (2008) 141–152]. Now, in this paper, the concept of (,q)-fuzzy n-ary sub-polygroups, -fuzzy n-ary sub-polygroups and fuzzy n-ary sub-polygroup with thresholds of an n-ary polygroup are introduced and some characterizations are described. Also, we give the definition of implication-based fuzzy n-ary sub-polygroups in an n-ary polygroup, in particular, the implication operators in Łukasiewicz system of continuous-valued logic are discussed.     

奇数变元代数免疫最优布尔函数的构造方法

代数免疫是随着代数攻击的出现而提出来的一个新的密码学特性。为了有效地抵抗代数攻击,密码系统中使用的布尔函数必须具有最佳的代数免疫。提出了递归构造奇数变元代数免疫最优布尔函数的一个方法。这是一个递归构造的方法,利用该方法,对任意的奇数,都可以构造相同变元数量的代数免疫最优布尔函数。     

一种新型非线性视频图像交叉加密算法

为了改善视频图像加密的安全和实时性能,提出了一种基于非线性的视频图像交叉加密算法。针对混沌系统中存在有限精度效应的影响和线性反馈移位寄存器生成序列的线性复杂度非常有限并且容易破解的问题,结合混沌技术和线性反馈移位寄存器技术,构造了非线性交叉加密算法的理论数学模型,阐述了算法的设计原理,介绍了实现的相关代码。通过与其他传统算法的理论分析和硬件实现的性能比较,结果表明：产生的视频图像密码序列在较低迭代次数来得到周期极大的非线性序列密码,其总体性能比可达到0．68,因此为高性能视频图像的传输提供了一种新的安全实时加密方法。     

An efficient delay-optimal distributed termination detection algorithm

Distributed termination detection is a fundamental problem in parallel and distributed computing and numerous schemes with different performance characteristics have been proposed. These schemes, while being efficient with regard to one performance metric, prove to be inefficient in terms of other metrics. A significant drawback shared by all previous methods is that, on most popular topologies, they take Ω(P)$\mathrm{\Omega }(P)$ time to detect and signal termination after its actual occurrence, where P   is the total number of processing elements. Detection delay is arguably the most important metric to optimize, since it is directly related to the amount of idling of computing resources and to the delay in the utilization of results of the underlying computation. In this paper, we present a novel termination detection algorithm that is simultaneously optimal or near-optimal with respect to all relevant performance measures on any topology. In particular, our algorithm has a best-case detection delay of Θ(1)$\mathrm{\Theta }(1)$ and a finite optimal worst-case detection delay on any topology equal in order terms to the time for an optimal one-to-all broadcast on that topology (which we accurately characterize for an arbitrary topology). On k-ary n  -cube tori and meshes, the worst-case delay is Θ(D)$\mathrm{\Theta }(D)$, where D   is the diameter of the target topology. Further, our algorithm has message and computational complexities of Θ(MD+P)$\mathrm{\Theta }(\mathit{MD}+P)$ in the worst case and, for most applications, Θ(M+P)$\mathrm{\Theta }(M+P)$ in the average case—the same as other message-efficient algorithms, and an optimal space complexity of Θ(P)$\mathrm{\Theta }(P)$, where M is the total number of messages used by the underlying computation. We also give a scheme using counters that greatly reduces the constant associated with the average message and computational complexities, but does not suffer from the counter-overflow problems of other schemes. Finally, unlike some previous schemes, our algorithm does not rely on first-in first-out (FIFO) ordering for message communication to work correctly.     

GF(pm)上周期为pn序列的m紧错线性复杂度*

综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror(S)的概念,提出紧错线性复杂度的概念。在GF(pm)上周期为pn序列的k错线性复杂度快速算法的基础上,给出m紧错线性复杂度的快速算法。其中p是素数。 编程实现了该算法, 并给出实验结果。     

On the linear span of the p -ary cascaded GMW sequences

In this paper, a recursion is derived to compute the linear span of the p-ary cascaded GMW sequences. It is the first time to determine the linear span of the p-ary cascaded GMW sequence without any restriction on the parameters completely. Whereas, the known result on the p-ary cascaded GMW sequence with the specific parameters in the literature could be viewed as a special case of the new result. Supported by the National Natural Science Foundation of China (Grant No. 60302015), the Foundation for the Author of National Excellent Doctoral Dissertation of China (Grant No. 200341), and Sichuan Youth Science Foundation (Grant No. 04ZQ026-048)     

一类新的4阶W-广义割圆序列的线性复杂度*

基于Whiteman-广义割圆,通过寻找序列特殊的特征集,构造了Zpq环上一类新的周期为pq、阶为4的广义割圆序列,并确定了该序列的线性复杂度,且该序列为平衡序列。结果表明,该类序列具有良好的线性复杂度性质,以它们作密钥流序列的密码系统具有抵抗B-M算法攻击的能力。     

基于流密码的可重构处理结构及其专用指令集研究

在对多种流密码算法生成结构进行分析的基础上,提出一种基于流密码的可重构处理结构,并在总结重构流密码算法使用频率较高的基本操作类型的基础上,为该流密码可重构处理结构设计了一种专用指令集。描述了指令的具体格式,并对指令性能进行了评估。结果表明,该指令集作用在该流密码可重构结构上可灵活高效地实现多种流密码算法。     

The linear complexity of new generalized cyclotomic binary sequences of order four

Whiteman generalized cyclotomic sequences are proven to exhibit a number of good randomness properties. In this paper we determine the linear complexity of some newly generalized cyclotomic sequences, of order four with period pq which are defined by Ding and Helleseth. The results show that all of these sequences have high linear complexity.     

Fp上周期序列S∞与S*∞的线性复杂度分析*

周期序列的线性复杂度是衡量密钥序列伪随机性的重要指标,周期序列的线性复杂度可以通过周期序列的极小多项式的次数求出。研究了有限域Fp上周期序列S∞的极小多项式的次数和由S∞及其对偶序列定义的一类新序列S*∞的极小多项式的次数之间的关系,建立了明确的关系式。这些结果对研究流密码密钥序列有一定的应用价值。