Remarks on the <Emphasis Type="Italic">k</Emphasis>-error linear complexity of <Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic sequences

Recently the first author presented exact formulas for the number of 2 ⁿ -periodic binary sequences with given 1-error linear complexity, and an exact formula for the expected 1-error linear complexity and upper and lower bounds for the expected k-error linear complexity, k ≥ 2, of a random 2 ⁿ -periodic binary sequence. A crucial role for the analysis played the Chan–Games algorithm. We use a more sophisticated generalization of the Chan–Games algorithm by Ding et al. to obtain exact formulas for the counting function and the expected value for the 1-error linear complexity for p ⁿ -periodic sequences over prime. Additionally we discuss the calculation of lower and upper bounds on the k-error linear complexity of p ⁿ -periodic sequences over .      

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.     

A counterexample concerning the 3-error linear complexity of 2 n -periodic binary sequences

In this article, we present a counterexample to Theorem 4.2 and Theorem 5.2 by Kavuluru (Des Codes Cryptogr 53:75–97, 2009). We conclude that the counting functions for the number of 2 ⁿ -periodic binary sequences with fixed 3-error linear complexity by Kavuluru are not correct.     

Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity \({L_{n,k}(\underline{s})/n}\) of random binary sequences \({\underline{s}}\) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of \({L_{n,k}(\underline{s})/n}\) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that \({\lim_{n\rightarrow\infty} L_{n,k}(\underline{s})/n = 1/2}\) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.     

Reducing the calculation of the linear complexity of u2 v -periodic binary sequences to Games–Chan algorithm

We show that the linear complexity of a u2 ^v -periodic binary sequence, u odd, can easily be calculated from the linear complexities of certain 2 ^v -periodic binary sequences. Since the linear complexity of a 2 ^v -periodic binary sequence can efficiently be calculated with the Games-Chan algorithm, this leads to attractive procedures for the determination of the linear complexity of a u2 ^v -periodic binary sequence. Realizations are presented for u = 3, 5, 7, 15.      

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.     

Orthonormal bases associated with multi-knot piecewise linear function sequences on [0, 1)<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We investigate two classes of orthonormal bases for L^2（[0, 1）^n）. The exponential parts of those bases are multi-knot piecewise linear functions which are called spectral sequences. We characterize the multi-knot piecewise linear spectral sequences and give an application of the first class of piecewise linear spectral sequences.     

On the k-error linear complexity of sequences with period 2pn over GF(q)

In this paper, we first optimize the structure of the Wei–Xiao–Chen algorithm for the linear complexity of sequences over GF(q) with period N =  2p ⁿ , where p and q are odd primes, and q is a primitive root modulo p ². The second, an union cost is proposed, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2p ⁿ over GF(q) is derived, where p and q are odd primes, and q is a primitive root modulo p ². The third, we give a validity of the proposed algorithm, and also prove that there exists an error sequence e ^N , where the Hamming weight of e ^N is not greater than k, such that the linear complexity of (s + e) ^N reaches the k-error linear complexity c. We also present a numerical example to illustrate the algorithm. Finally, we present the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.     

Some results concerning cryptographically significant mappings over GF(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

In this paper we investigate the existence of permutation polynomials of the form F(x) = x ^d  + L(x) over GF(2 ⁿ ), L being a linear polynomial. The results we derive have a certain impact on the long-term open problem on the nonexistence of APN permutations over GF(2 ⁿ ), when n is even. It is shown that certain choices of exponent d cannot yield APN permutations for even n. When n is odd, an infinite class of APN permutations may be derived from Gold mapping x ³ in a recursive manner, that is starting with a specific APN permutation on GF(2 ^k ), k odd, APN permutations are derived over GF(2 ^k+2i ) for any i ≥ 1. But it is demonstrated that these classes of functions are simply affine permutations of the inverse coset of the Gold mapping x ³. This essentially excludes the possibility of deriving new EA-inequivalent classes of APN functions by applying the method of Berveglieri et al. (approach proposed at Asiacrypt 2004, see [3]) to arbitrary APN functions.     

Principal forms <Emphasis Type="Italic">X</Emphasis><Superscript>2</Superscript>+<Emphasis Type="Italic">nY</Emphasis><Superscript>2</Superscript> representing many integers

In 1966, Shanks and Schmid investigated the asymptotic behavior of the number of positive integers less than or equal to x which are represented by the quadratic form X ²+nY ². Based on some numerical computations, they observed that the constant occurring in the main term appears to be the largest for n=2. In this paper, we prove that in fact this constant is unbounded as n runs through positive integers with a fixed number of prime divisors.     

Some results on 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> designs with clear two-factor interaction components

Clear effects criterion is one of the important rules for selecting optimal fractional factorial designs, and it has become an active research issue in recent years. Tang et al. derived upper and lower bounds on the maximum number of clear two-factor interactions (2fi’s) in 2 ^n−(n−k) fractional factorial designs of resolutions III and IV by constructing a 2 ^n−(n−k) design for given k, which are only restricted for the symmetrical case. This paper proposes and studies the clear effects problem for the asymmetrical case. It improves the construction method of Tang et al. for 2 ^n−(n−k) designs with resolution III and derives the upper and lower bounds on the maximum number of clear two-factor interaction components (2fic’s) in 4 ^m 2 ⁿ designs with resolutions III and IV. The lower bounds are achieved by constructing specific designs. Comparisons show that the number of clear 2fic’s in the resulting design attains its maximum number in many cases, which reveals that the construction methods are satisfactory when they are used to construct 4 ^m 2 ⁿ designs under the clear effects criterion. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10571093, 10671099 and 10771123), the Research Foundation for Doctor Programme (Grant No. 20050055038) and the Natural Science Foundation of Shandong Province of China (Grant No. Q2007A05). Zhang’s research was also supported by the Visiting Scholar Program at Chern Institute of Mathematics.     

Existence of three HMOLS of type 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript><Emphasis Type="Italic">u</Emphasis><Superscript>1</Superscript>

A Latin squares of order v with ni missing sub-Latin squares （holes） of order hi （1 〈= i 〈 k）, which are disjoint and spanning （i.e. ∑k i=l1 nihi = v）, is called a partitioned incomplete Latin squares and denoted by PILS. The type of PILS is defined by （h1n1 h2n2…hknk ）. If any two PILS inaset of t PILS of type T are orthogonal, then we denote the set by t-HMOLS（T）. It has been proved that 3-HMOLS（2n31） exist for n ≥6 with 11 possible exceptions. In this paper, we investigate the existence of 3-HMOLS（2nu1） with u ≥ 4, and prove that 3-HMOLS（2~u1） exist if n ≥ 54 and n ≥7/4u ＋ 7.     

Construction of pseudorandom binary sequences using additive characters over GF(2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>) II

In a series of papers Mauduit and Sárközy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 ^k ) will be studied.     

Primes of the form <Emphasis Type="Italic">x</Emphasis><Superscript>2</Superscript> + (<Emphasis Type="Italic">x</Emphasis> + 1)<Superscript>2</Superscript>. Proper divisors of composites of the same form

The aim of the present paper is to characterize prime numbers of the form n = x ² + (x + 1)² and to obtain certain proper divisors of composite numbers of the same form, i.e. divisors d of n such that 1 < d < n.      

The existence of global attractors for 2D Navier-Stokes equations in <Emphasis Type="Italic">H</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript> spaces

In this paper, we prove that the 2D Navier-Stokes equations possess a global attractor in Hk（Ω,R2） for any k ≥ 1, which attracts any bounded set of Hk（Ω,R2） in the H^k-norm. The result is established by means of an iteration technique and regularity estimates for the linear semigroup of operator, together with a classical existence theorem of global attractor. This extends Ma, Wang and Zhong＇s conclusion.     

On linear complexity of binary lattices,II

The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.     

Remarks on the uniform and <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-convergence of trigonometric series

Chaundry and Jolliffe [1] proved that if a _k is a nonnegative sequence tending monotonically to zero, then a necessary and sufficient condition for the uniform convergence of the series Σ _k=1^∞ a _k sin kx is lim _k→∞ ka _k = 0. Lately, S. P. Zhou, P. Zhou and D. S. Yu [4] generalized this classical result. In this paper we propose new classes of sequences for which we get the extended version of their results. Moreover, we generalize the results of S. Tikhonov [2] on the L ¹-convergence of Fourier series.     

On improved asymptotic bounds for codes from global function fields

We analyse a binary cyclotomic sequence constructed via generalized cyclotomic classes by Bai et al. (IEEE Trans Inforem Theory 51: 1849–1853, 2005). First we determine the linear complexity of a natural generalization of this binary sequence to arbitrary prime fields. Secondly we consider k-error linear complexity and autocorrelation of these sequences and point out certain drawbacks of this construction. The results show that the parameters for the sequence construction must be carefully chosen in view of the respective application.      

On sequences of maps into <Emphasis Type="Italic">S</Emphasis><Superscript>1</Superscript> with equibounded <Emphasis Type="Italic">W</Emphasis><Superscript>1/2</Superscript> energies

In the last years there has been some interest in studying mappings in the fractional Sobolev space W^1/2(, S¹), see e.g., [4] [3] [15] [12] and the paper [5]. Motivated by these papers, we characterize here in the framework of Cartesian currents, see [9], the class of weak limits of sequences of smooth mappings with values into S¹ with equibounded W^1/2 energies.     

Laminar currents in ℙ<Superscript>2</Superscript>

 In this paper we study laminar currents in ℙ². Given a sequence of irreducible algebraic curves (C _n ) converging in the sense of currents to T, we find geometric conditions on the curves ensuring that the limit current T is laminar. This criterion is then applied to meromorphic dynamical systems in ℙ², and laminarity of the dynamical ``Green' current is obtained for a wide class of meromorphic self maps of ℙ², as well as for all bimeromorphic maps of projective surfaces. Received: 24 September 2001 / Published online: 10 February 2003 Mathematics Subject Classification (2000): 32U40, 37Fxx, 32H50