周期为2p2 的四阶二元广义分圆序列的线性复杂度

该文基于分圆理论,构造了一类周期为2p2的四阶二元广义分圆序列。利用有限域上多项式分解理论研究序列的极小多项式和线性复杂度。结果表明,该序列具有良好的线性复杂度性质,能够抗击B-M算法的攻击。是密码学意义上性质良好的伪随机序列。     

多重周期二元序列联合二次复杂度的计算

以Rizomiliotis所提出的计算单序列的二次复杂度算法为基础,结合线性方程组的解的判定方法,给出了一个求解任意有限域上多重周期序列联合二次复杂度的算法。算法的复杂性分析表明算法复杂度至多为序列长度的三次函数。     

一类可控序列的构造和分析

本文通过利用GF(2m)(m2)上L级m序列来控制其上的L级m序列的方法,构造出了一类具有较高线性复杂度的周期序列。这类序列的线性复杂度的下界为L((L+1)mLm)。     

CONSTRUCTING AND ANALYZING A CLASS OF CONTROLLABLE SEQUENCES

By using m-sequence over the finite field GF(2m) of degree L to control m-sequence over GF(2m) of degree L, a class of periodic sequences with large linear complexity is constructed. The lower bounds of the linear complexity of these sequences are L((L +1)m-Lm).     

Sequences with almost perfect linear complexity profiles and curvesover finite fields

For stream ciphers, we need to generate pseudorandom sequences which are of properties of unpredictability and randomness. A important measure of unpredictability and randomness is the linear complexity profile (l.c.p.) l_a(n) of a sequence a. A sequence a is called almost perfect if the l.c.p. is l_a(n)=n/2+O(1). Based on curves over finite fields, we present a method to construct almost perfect sequences. We also illustrate our construction by explicit examples from the projective line and elliptic curves over the binary field     

GF(q)上周期序列的线性复杂度分析

给出了有限域上周期序列在改变几个比特的情况下,其极小多项式及线性复杂度的计算公式,并对其中只改变了一个比特的序列进行了深入的分析,最后得出m序列及周期为2~n序列在改变任意一个比特后的线性复杂度。     

GF(3)上新型自缩控序列的周期与线性复杂度

Self-Shrinking Control (SSC) sequences are a class of important pseudo-random sequences, and pseudo-random sequences are widely used in many fields, such as communication encryption, recoding technology. In these applications, sequences are usually required to have large periods and high linear complexity. In order to construct pseudo-random sequences with higher period and higher linear complexity, a new SSC sequence model based on the m-sequence in GF (3) is constructed, the period and the linear complexity of the generated sequence are studied by using finite domain theory, this model greatly improves the period and the linear complexity of the generated sequence, and obtains a more accurate upper bound value of the linear complexity of the generated sequence. Thus, the anti-attack ability and security performance of the generated sequence in communication encryption are improved.     

一类可控序列线性复杂度的估计

本文运用指数集的概念，得到了任意有限域ＧＦ（ｑ）（ｑ＝ｐｍ）上Ｌ级ｍ－序列的多项式序列的线性复杂度，并导出了一类可控序列线性复杂度的上界，这个上界很可能是紧上界。当域特征ｐ＝２时，这类序列线性复杂度的上界为Ｌ＋１２［（Ｌ＋１）ｍ－１］，下界为［（Ｌ＋１）ｍ－１］。     

Periodic sequences with large k-error linear complexity

We establish the existence of periodic sequences over a finite field which simultaneously achieve the maximum value (for the given period length) of the linear complexity and of the k-error linear complexity for small values of k. This disproves a conjecture of Ding, Xiao, and Shan (1991). The result is of relevance for the theory of stream ciphers.     

An analysis of the structure and complexity of nonlinear binary sequence generators

A method of analysis is presented for the class of binary sequence generators employing linear feedback shift registers with nonlinear feed-forward operations. This class is of special interest because the generators are capable of producing very long "unpredictable" sequences. The period of the sequence is determined by the linear feedback connections, and the portion of the total period needed to predict the remainder is determined by the nonlinear feed-forward operations. The linear feedback shift registers are represented in terms of the roots of their characteristic equations in a finite field, and it is shown that nonlinear operations inject additional roots into the representation. The number of roots required to represent a generator is a measure of its complexity, and is equal to the length (number of stages) of the shortest linear feedback shift register that produces the same sequence. The analysis procedure can be applied to any arbitrary combination of binary shift register generators, and is also applicable to the synthesis of complex generators having desired properties. Although the discussion in this paper is limited to binary sequences, the analysis is easily extended to similar devices that generate sequences with members in any finite field.     

Fp上pn-周期序列的1-错线性复杂度

周期序列的线性复杂度和k-错线性复杂度是衡量密钥流序列随机性的两个重要指标.该文给出了Fp上pn-周期的序列所有可能的1-错线件复杂度的值以及具有给定1-错线性复杂度的序列个数.更进一步,该文给出了Fp上pn-周期的序列1-错线性复杂度的期望.     

四元本原序列最高权位的线性复杂度

极小多项式和线性复杂度是序列用于保密通信和扩频通信的重要参数，本文利用有限域上迹函数理论和组合数学的知识决定了四元本原序列的最高权位序列的极小多项式和线性复杂度。     

一种新的Shrinking序列周期及线性复杂度

给出了一种新的Shrinking序列模型,并且利用有限域理论,解决了这种新的Shrinking序列的周期及线性复杂度界。     

Galois环导出p元序列中元素组的分布及其渐近均匀性

r-样式的分布是有限域上序列伪随机性的一个重要方面。就此问题本文对域R/pR上一类序列作了考察，这类序列得自于Galois环R＝GR（p^m,p^n）上其特征多项式f(x）在模p下本原的线性递归序列（包括极大长序列）的p-adic展开，即所谓Galois环导出p元序列，我们得到了这种序列上独立r-样式分布的一个估计，作为推论，r-样式的分布关于f(x)的次数是渐近均匀的。     

2-adic complexity of SLCE sequence

Aiming at the 2-adic complexity of Sidelnikov-Lempel-Cohn-Eastman sequences,autocorrelation function value of this kind of sequence was obtained by using the cyclotomic number.Based on the relationship between 2-adic complexity and autocorrelation function,properties of 2-adic complexity value were analyzed.According to the greatest common divisor between the autocorrelation function value and the period of SLCE sequence,the condition that the 2-adic complexity of a SLCE sequence reaches its maximum value was given.The results show that 2-adic complexity of SLCE sequence on many finite field can reach the maximum value.     

有限长序列线性相关的快速算法研究

线性相关在信号处理中具有十分重要的作用,因此研究线性相关的快速运算具有重要意义。本文根据有限长序列的线性相关的定义,首先给出了基于快速傅立叶变换（Fast Fourier Transform,FFT）直接计算线性相关的快速算法,记为直接FFT算法;其次针对长度相差较大的有限长序列,提出了一种分段求和FFT算法,相比于直接FFT法,具有更小的运算量。仿真结果表明,相比于根据定义直接计算线性相关,直接FFT算法显著减少了运算量,且序列长度越长,改善效果越明显;若参与线性相关的两个序列长度相差较大,则相比于直接FFT算法,分段求和FFT算法具有更小的运算量,且序列长度差距越大,改善效果越好。     

Optimal large linear complexity frequency hopping patterns derivedfrom polynomial residue class rings

We construct new sequences over finite rings having optimal Hamming correlation properties. These sequences are useful in frequency hopping multiple-access (FHMA) spread-spectrum communication systems. Our constructions can be classified into linear and nonlinear categories, both giving optimal Hamming correlations according to Lempel-Greenberger (1974) bound. The nonlinear sequences have large linear complexity and can be seen as a generalized version of GMW sequences over fields     

2n-周期二元序列的3-错误序列分布

线性复杂度和k- 错线性复杂度是度量密钥流序列密码强度的重要指标。为了更好地研究序列的随机性,该文通过将序列的k-错线性复杂度的计算转化为求Hamming重量最小的错误序列的方法,讨论了序列不同k-错线性复杂度条件下对应的k-错误序列的分布情况。基于Games-Chan算法,该文给出了线性复杂度为2n的2n-周期二元序列的3错误序列的计数公式,计算机编程验证了该文方法的正确性。     

Z4上周期为2p2的四元广义分圆序列的线性复杂度

该文根据特征为4的Galois环理论,在Z₄上利用广义分圆构造出一类新的周期为2p2(p为奇素数)的四元序列,并且给出了它的线性复杂度。结果表明,该序列具有良好的线性复杂度性质,能够抗击Berlekamp-Massey (B-M)算法的攻击,是密码学意义上性质良好的伪随机序列。     

Coding theorems for individual sequences

A quantity called the {em finite-state} complexity is assigned to every infinite sequence of elements drawn from a finite sot. This quantity characterizes the largest compression ratio that can be achieved in accurate transmission of the sequence by any finite-state encoder (and decoder). Coding theorems and converses are derived for an individual sequence without any probabilistic characterization, and universal data compression algorithms are introduced that are asymptotically optimal for all sequences over a given alphabet. The finite-state complexity of a sequence plays a role similar to that of entropy in classical information theory (which deals with probabilistic ensembles of sequences rather than an individual sequence). For a probabilistic source, the expectation of the finite state complexity of its sequences is equal to the source's entropy. The finite state complexity is of particular interest when the source statistics are unspecified.