Multiplicative character sums of Fermat quotients and pseudorandom sequences

We prove a bound on sums of products of multiplicative characters of shifted Fermat quotients modulo p. From this bound we derive results on the pseudorandomness of sequences of modular discrete logarithms of Fermat quotients modulo p: bounds on the well-distribution measure, the correlation measure of order ?, and the linear complexity.     

On the linear complexity of binary lattices

Linear complexity is an important and frequently used measure of unpredictability and pseudorandomness of binary sequences. In this paper our goal is to extend this notion to two dimensions. We will define and study the linear complexity of binary lattices. The linear complexity of a truly random binary lattice will be estimated. Finally, we will analyze the connection between linear complexity and correlation measures, and we will utilize the inequalities obtained in this way for estimating the linear complexity of an important special binary lattice. Finally, we will study the connection between the linear complexity of binary lattices and of the associated binary sequences.     

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 …     

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.     

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.     

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.     

On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length 2p m

In this article, new classes of generalized cyclotomic binary sequences with period 2p ^m are proposed. We determine the linear complexity and autocorrelation of these sequences. The results show that the proposed generalized cyclotomic binary sequences have high linear complexity, but do not have desirable autocorrelation properties.     

Supersingular quotients of Fermat curves

We give formulas for the genera of all the possible quotient of a Fermat curve by a group of automorphisms in characteristic zero and for many classes of quotient curves also in positive characteristic. We use those results for giving evidence to the conjecture that, in any fixed positive characteristic, there should exist supersingular curves for any genus.     

On the -divisibility of Fermat quotients

The authors carried out a numerical search for Fermat quotients vanishing mod , for , up to . This article reports on the results and surveys the associated theoretical properties of . The approach of fixing the prime rather than the base leads to some aspects of the theory apparently not published before.

     

The linear complexity of a class of binary sequences with optimal autocorrelation

Binary sequences with optimal autocorrelation and large linear complexity have important applications in cryptography and communications. Very recently, a class of binary sequences of period 4p with optimal autocorrelation was proposed by interleaving four suitable Ding–Helleseth–Lam sequences (Des. Codes Cryptogr.,  https://doi.org/10.1007/s10623-017-0398-5), where p is an odd prime with \(p \equiv 1(\bmod 4)\). The objective of this paper is to determine the minimal polynomial and the linear complexity of this class of binary optimal sequences via a sequence polynomial approach. It turns out that this class of sequences has quite good linear complexity.     

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.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Expected values for the rational complexity of finite binary sequences

2-Adic complexity plays an important role in cryptology. It measures the difficulty of outputting a binary sequence using a feedback with carry shift register. This paper studies the 2-adic complexity of finite sequences by investigating the corresponding rational complexity whose logarithm to the base 2 is just equal to the 2-adic complexity. Experiments show that the logarithm to the base 2 of the expected values for rational complexity is a good approximation to the expected values for the 2-adic complexity. Both a nontrivial lower bound and a nontrivial upper bound on the expected values for the rational complexity of finite sequences are given in the paper. In particular, the lower bound is much better than the upper bound.     

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.      

2-Adic complexity of binary sequences with interleaved structure

In this paper, 2-adic complexity of some binary sequences with interleaved structure is investigated. Firstly, 2-adic complexity of low correlation zone (LCZ) sequences constructed by Zhou et al. [23] is completely determined. We show that their 2-adic complexity could attain the maximum if suitable parameters are chosen. Secondly, we also determine 2-adic complexity of optimal autocorrelation sequences constructed by Tang and Ding [16]. Results show that they have the maximum 2-adic complexity.