p元扩展序列的线性复杂度

给出了由周期为p~m-1的p元序列导出的周期为p~(em)-1的p元扩展序列的线性复杂度.作为一个实例,计算了扩展Legendre序列的线性复杂度.     

一类ρ元序列集的相关性和线性复杂度的分析

对于素数p和偶数n=2k,构造了一类周期为pn-1的pn条序列组成的p元序列集S(r),这里pk≠2(mod3),r与pk-1互素.利用d-齐次函数的性质,确定了这类序列集的相关函数取-1±pk,-1,-1+2.pk四值及相应分布;使用推广的Key方法证明了这类序列集具有较大的线性复杂度下界.这类序列集可适用于CDMA通信系统和密码系统中.     

一类P元序列集的相关性和线性复杂度的分析

对于素数P和偶数n=2k,构造了一类周期为P^n-1的P”条序列组成的P元序列集s（r）,这里P^k≠2（rood3）,r与P^k=1互素．利用d-齐次函数的性质,确定了这类序列集的相关函数取-1±P^k-1,-1＋2·p^k四值及相应分布;使用推广的Key方法证明了这类序列集具有较大的线性复杂度下界．这类序列集可适用于CDMA通信系统和密码系统中．     

用迹表示研究序列的线性复杂度

本文用迹表示式证明了序列的线性复杂度等于其秩矩阵的秩，并由此导出了正规基的计数公式．     

基于代数曲线上具有高广义联合线性复杂度的多重序列

多重序列的联合线性复杂度是衡量基于字的流密码体系安全的一个重要指标. 由元素取自F_q上的m 重序列和元素取自F_q^m 上的单个序列之间的一一对应, Meidl 和Özbudak 定义多重序列的广义联合线性复杂度为对应的单个序列的线性复杂度. 在本文中, 我们利用代数曲线的常数域扩张, 研究两类多重序列的广义联合线性复杂度. 更进一步, 我们指出这两类多重序列同时具有高联合线性复杂度和高广义联合线性复杂度.     

用迹表示研究序列的线性复杂度

本用迹表示式证明了序列的线性复杂度等于其秩矩阵的秩，并由此导出了正规基的计数公式。     

一类新的广义割圆序列的线性复杂度及其自相关值

最近,丁存生基于新的割圆类(V_0,V_1)构造了循环码并研究了其性质.本文利用割圆类(V_0, V_1)构造了周期为pq的2阶二元序列,并计算了其自相关值、线性复杂度和极小多项式.     

二元叠加码M_q(n,k,d)的线性性质

二元叠加码M_q(n,k,d)是一个非适应性分组测试算法的数学模型,它是一个d-disjunct矩阵.利用有限域F_2上向量的计算法则研究了二元叠加码M_q(n,k,d)的线性性质,分别得到了M_q(n,k,d)存在线性性质和不存在线性性质的条件,为进一步研究M_q(n,k,d)提供了依据.     

二元叠加码M_q~c(n,k,d)的性质

二元叠加码M_q~c(n,k,d)是二元叠加码M_q(n,k,d)的补阵,利用有限域F_2上向量的计算法则研究了二元叠加码M_q~c(n,k,d)的线性性质并证明了M_q~c(n,k,d)的析取(disjunct)性.     

M序列一个周期的复杂度

在流密码中,M序列及M序列一个周期复杂度是一个重要课题。Chan等人在文献[2]中对M序列的界和分布进行了讨论。本文将对M序列一个周期复杂度进行一些研究,并且主要讨论M序列一个周期复杂度的上下界,遍历性和分布情况。 注 本文在GF(2)上和n≥3情况下讨论。     

Linear Complexity of the Discrete Logarithm

We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.     

单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.     

How Many Bits have to be Changed to Decrease the Linear Complexity?

The k-error linear complexity of periodic binary sequences is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. For the period length p ⁿ, where p is an odd prime and 2 is a primitive root modulo p ², we show a relationship between the linear complexity and the minimum value k for which the k-error linear complexity is strictly less than the linear complexity. Moreover, we describe an algorithm to determine the k-error linear complexity of a given p ⁿ-periodic binary sequence.     

On the limit of maximal density of sequences with a Perfect Linear Complexity Profile

A binary sequence with a Perfect Linear Complexity Profile (PLCP) has all the jumps in its linear complexity profile of height exactly 1. We prove the conjecture made in Ho that the limit of the maximum density (proportion of ones) over all PLCPs of a particular length is 2/3 as the length tends to infinity.     

Multi-sequences with Almost Perfect Linear Complexity Profile and Function Fields over Finite Fields

Sequences with almost perfect linear complexity profile defined by Niederreiter (1997, Lecture Notes in Computer Science, Vol. 304, pp. 37–51, Springer-Verlag, Berlin/New York) are quite important for stream ciphers. In this paper, we investigate multi-sequences with almost perfect linear complexity profile and obtain a construction of such multi-sequences by using function fields over finite fields. Some interesting examples from this construction are presented to illustrate our construction.     

A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems

We consider the standard linear complementarity problem (LCP): Find (x, y) R ²ⁿ such that y = M x + q, (x, y) 0 and x _i y _i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P ₀ LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in Newton iterations where is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.     

Root Counting, the DFT and the Linear Complexity of Nonlinear Filtering

The method of root counting is a well established technique in the study of the linear complexity of sequences. Recently, Massey and Serconek [11] have introduced a Discrete Fourier Transform approach to the study of linear complexity. In this paper, we establish the equivalence of these two approaches. The power of the DFT methods are then harnessed to re-derive Rueppel's Root Presence Test, a key result in the theory of filtering of m-sequences, in an elegant and concise way. The application of Rueppel's Test is then extended to give lower bounds on linear complexity for new classes of filtering functions.     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.