Welcome to the resource topic for
**2016/1025**

**Title:**

An Algorithm for Counting the Number of 2^n-Periodic Binary Sequences with Fixed k-Error Linear Complexity

**Authors:**
Wenlun Pan, Zhenzhen Bao, Dongdai Lin, Feng Liu

**Abstract:**

The linear complexity and k-error linear complexity of sequences are important measures of the strength of key-streams generated by stream ciphers. The counting function of a sequence complexity measure gives the number of sequences with given complexity measure value and it is useful to determine the expected value and variance of a given complexity measure of a family of sequences. Fu et al. studied the distribution of 2^n-periodic binary sequences with 1-error linear complexity in their SETA 2006 paper and peoples have strenuously promoted the solving of this problem from k=2 to k=4 step by step. Unfortunately, it still remains difficult to obtain the solutions for larger k and the counting functions become extremely complex when k become large. In this paper, we define an equivalent relation on error sequences. We use a concept of \textit{cube fragment} as basic modules to construct classes of error sequences with specific structures. Error sequences with the same specific structures can be represented by a single \textit{symbolic representation}. We introduce concepts of \textit{trace}, \textit{weight trace} and \textit{orbit} of sets to build quantitative relations between different classes. Based on these quantitative relations, we propose an algorithm to automatically generate symbolic representations of classes of error sequences, calculate \textit{coefficients} from one class to another and compute \textit{multiplicity} of classes defined based on specific equivalence on error sequences. This algorithm can efficiently get the number of sequences with given k-error linear complexity. The time complexity of this algorithm is O(2^{k\log k}) in the worst case which does not depend on the period 2^n.

**ePrint:**
https://eprint.iacr.org/2016/1025

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .