变系数反馈移位寄存器及其序列的几个性质

本文给出了一类新的密钥流生成器一变系数反馈移位寄存器,得到了该密钥流生成器序列的几个重要的密码学性质,并在文中给出了严格的数学证明。     

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

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

FCSR序列的线性复杂度

§ 1　 IntroductionFeedback with carry shift register(FCSR) was first introduced by Klapper andGoresky in1 994[1 ] .The main idea of FCSR is to add a memory to linearfeedback shiftreg-ister(LFSR) .The structure is depicted in Fig.1 ,Fig.1where mn- 1 ∈Z,ai,qi∈ { 0 ,1 } and qr=1 .We refer to mn- 1 as memory,(mn- 1 ,an- 1 ,...,an- r)as state,r=log(q+ 1 ) as length,and q=-1 + q1 · 2 + ...+ qr· 2 ras connection integerof FCSR.The operation of the shiftregister is defined as follows:(1 …     

Register Synthesis for Algebraic Feedback Shift Registers Based on Non-Primes

In this paper, we describe a solution to the register synthesis problem for a class of sequence generators known as algebraic feedback shift registers (AFSRs). These registers are based on the algebra of -adic numbers, where is an element in a ring R, and produce sequences of elements in R/(). We give several cases where the register synthesis problem can be solved by an efficient algorithm. Consequently, any keystreams over R/() used in stream ciphers must be unable to be generated by a small register in these classes. This paper extends the analyses of feedback with carry shift registers and algebraic feedback shift registers by Goresky, Klapper, and Xu.     

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 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.     

有关顺序统计量的极大似然估计

讨论了一类参数空间受样本限制的极大似然估计问题.分析了随机变量分布的非零区域与似然函数定义域的对应关系,提出如果分布的非零区域受参数限制,则无论似然方程是否可解,参数的极大似然估计必然与样本顺序统计量X_((n))或X_((1))有关,并具体分析了似然估计一定等于、一定不等于和可能等于顺序统计量X_((n))(X_((1)))的三种情形,并给出了相应的判别条件.最后分析得出在第三种判别条件之下,似然估计是否取值于x_((n))(x_((1)))视具体的样本观测值决定.     

最大最小次序统计量的联合分布

X1,X2,…,Xn是来自总体X的简单随机样本,Nk=min1≤i≤k{Xi},Mk=max1≤i≤k{Xi}(k=1,2,…,n),本文给出了最小次序统计量与最大次序统计量的联合分布函数.     

Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.     

Modified constructions of binary sequences using multiplicative inverse

Two new families of finite binary sequences are constructed using multiplicative inverse. The sequences are shown to have strong pseudorandom properties by using some estimates of certain exponential sums over finite fields. The constructions can be implemented fast since multiplicative inverse over finite fields can be computed in polynomial time.     

On the Complexity of Partial Order Properties

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n ² for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k n ² / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.     

具有2n线性复杂度的2n周期二元序列的3错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n的2n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式, k=3,4.对于一般的线性复杂度为2n-m的2n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式.     

最大利润流问题及算法

最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .     

算子方程近似解直接方法的优化和信息复杂性研究进展

算子方程近似解直接方法的优化和信息复杂性是80年代发展起来的连续复杂性理论的两个主要方面,是计算机科学和数学的交叉研究领域．本文拟就这两个方面的研究进展做一简要介绍．     

订单带多类工件时的最大迟后问题

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。     

强相依高斯序列的最大值与和的联合渐近分布

{X_n,n≥1)是标准高斯序列,T_(ij)=cov(X_i,X_j)。本文在强相依条件rijlog(j-i)→r∈(0,∞)(j-i→ ∞)下,得到了高斯序列的最大值M_n与标准化部分和S_n=sum from i=1 to n(X_i/(E(sum from i=1 to n X_i)~2)/(1/2))     

Computing Approximate Solutions of the Maximum Covering Problem with GRASP

We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.     

An Incremental Algorithm for the Maximum Flow Problem

An incremental algorithm may yield an enormous computational time saving to solve a network flow problem. It updates the solution to an instance of a problem for a unit change in the input. In this paper we have proposed an efficient incremental implementation of maximum flow problem after inserting an edge in the network G. The algorithm has the time complexity of O((n)² m), where n is the number of affected vertices and m is the number of edges in the network. We have also discussed the incremental algorithm for deletion of an edge in the network G.     

Dn型非线性反馈移位寄存器

研究了一类Dynkin型非线性反馈移位寄存器,给出了n长码是Dn型反馈函数的周期码的充分必要条件,并得出了所有周期码及其周期。     

一类马尔可夫序列最大值的极限律

主要研究一类马尔可夫序列{Xn,n≥0}的最大值的极限分布.导出了这类序列最大值和最小值的分布表达式,利用经典极值理论,建立了规范化最大值max{X0,X1,…,Xn}与i.i.d序列{ξn,n≥1}的规范化最大值max{1ξ,2ξ,…,ξn+1}具有相同极限律的条件.