共查询到20条相似文献,搜索用时 15 毫秒
1.
Multi-sequences with Almost Perfect Linear Complexity Profile and Function Fields over Finite Fields 总被引:1,自引:0,他引:1
Chaoping Xing 《Journal of Complexity》2000,16(4):774
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. 相似文献
2.
具有2n线性复杂度的2n周期二元序列的3错线性复杂度 总被引:3,自引:0,他引:3
线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2n的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2n的2n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式, k=3,4.对于一般的线性复杂度为2n-m的2n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式. 相似文献
3.
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. 相似文献
4.
p元扩展序列的线性复杂度 总被引:1,自引:0,他引:1
给出了由周期为p~m-1的p元序列导出的周期为p~(em)-1的p元扩展序列的线性复杂度.作为一个实例,计算了扩展Legendre序列的线性复杂度. 相似文献
5.
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. 相似文献
6.
FCSR序列的线性复杂度 总被引:1,自引:0,他引:1
§ 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 … 相似文献
7.
Igor Shparlinski 《Designs, Codes and Cryptography》2001,23(1):5-10
We obtain a lower bound on the linear complexity of the powergenerator of pseudo-random numbers, which in some special cases is alsoknown as the RSA generator and as the Blum–Blum–Shubgenerator. In some very important cases this bound is essentially thebest possible. In particular, this implies that lattice reductionattacks on such generators are not feasible. 相似文献
8.
Pratulananda Das Prasanta Malik Ekrem Sava 《Applied mathematics and computation》2009,215(3):1030-1034
We investigate the structure of the set of all statistical limit points of a double sequence and prove certain results, mainly showing that this set can be characterized as a Fσ-set. 相似文献
9.
最近,丁存生基于新的割圆类(V_0,V_1)构造了循环码并研究了其性质.本文利用割圆类(V_0, V_1)构造了周期为pq的2阶二元序列,并计算了其自相关值、线性复杂度和极小多项式. 相似文献
10.
11.
本文研究了Feigenbaum吸引子和周期窗口中Feisenbaum吸引子决定的形式语言,讨论了它们的语法复杂性.证明了这类吸引子都是ETOL语言,从而是上下文有关语言(CSL);而不是上下文无关语言(CFL). 相似文献
12.
13.
On the distinctness of modular reductions of maximal length sequences modulo odd prime powers 总被引:1,自引:0,他引:1
We discuss the distinctness problem of the reductions modulo of maximal length sequences modulo powers of an odd prime , where the integer has a prime factor different from . For any two different maximal length sequences generated by the same polynomial, we prove that their reductions modulo are distinct. In other words, the reduction modulo of a maximal length sequence is proved to contain all the information of the original sequence.
14.
In this paper we give an approximate probability distribution for the maximum order complexity of a random binary sequence. This enables the development of statistical tests based on maximum order complexity for the testing of a binary sequence generator. These tests are analogous to those based on linear complexity. 相似文献
15.
Klapper (1994) showed that there exists a class of geometric
sequences with the maximal possible linear complexity when
considered as sequences over $GF(2)$, but these sequences have very
low linear complexities when considered as sequences over $GF(p)(p$ is an odd prime). This linear complexity of a binary sequence
when considered as a sequence over $GF(p)$ is called $GF(p)$
complexity. This indicates that the binary sequences with high
$GF(2)$ linear complexities are inadequate for security in the
practical application, while, their $GF(p)$ linear complexities are
also equally important, even when the only concern is with attacks
using the Berlekamp-Massey algorithm [Massey, J. L., Shift-register
synthesis and bch decoding, {\it IEEE Transactions on Information
Theory}, {\bf 15}(1), 1969, 122--127]. From this perspective, in
this paper the authors study the $GF(p)$ linear complexity of Hall''s
sextic residue sequences and some known cyclotomic-set-based
sequences. 相似文献
16.
Wilfried Meidl 《Designs, Codes and Cryptography》2004,33(2):109-122
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
n, where p is an odd prime and 2 is a primitive root modulo p
2, 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
n-periodic binary sequence. 相似文献
17.
Keisuke Hotta Masatora Inaba Akiko Yoshise 《Computational Optimization and Applications》2000,17(2-3):183-201
We consider the standard linear complementarity problem (LCP): Find (x, y) R
2n
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
0 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. 相似文献
18.
Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的. 相似文献
19.
Kenneth G. Paterson 《Designs, Codes and Cryptography》1998,14(3):247-259
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. 相似文献
20.
Robert M. Young 《Proceedings of the American Mathematical Society》1998,126(4):1139-1142
In this note, we give necessary and sufficient conditions for a system of complex exponentials to form a Riesz-Fischer sequence in for every positive number . The result provides a significant strengthening of the sufficient conditions recently stated by R. M. Reid (1995).