## Abstract

The linear complexity of sequences is an important measure to gauge the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu, Niederreiter, and Su [3] studied linear complexity and 1-error linear complexity of 2 ^{n} -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ^{n} -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ^{n} -periodic binary sequences with fixed 2-error or 3-error linear complexity L, when the Hamming weight of the binary representation of 2 ^{n} - L is . Using this characterization we obtain the counting function for the number of 2 ^{n} -periodic binary sequences with fixed k-error linear complexity L for k = 2 and 3 when .

Original language | English |
---|---|

Title of host publication | Sequences and Their Applications - SETA 2008 - 5th International Conference, Proceedings |

Pages | 252-265 |

Number of pages | 14 |

DOIs | |

State | Published - 2008 |

Event | 5th International Conference on Sequences and Their Applications, SETA 2008 - Lexington, KY, United States Duration: Sep 14 2008 → Sep 18 2008 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5203 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 5th International Conference on Sequences and Their Applications, SETA 2008 |
---|---|

Country/Territory | United States |

City | Lexington, KY |

Period | 9/14/08 → 9/18/08 |

### Bibliographical note

Funding Information:This material is based upon work supported by the National Science Foundation under Grant No. CCF-0514660. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

## Keywords

- K-error linear complexity
- Linear complexity
- Periodic sequence

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science (all)

## Fingerprint

Dive into the research topics of '2^{n}-Periodic binary sequences with fixed k-error linear complexity for k = 2 or 3'. Together they form a unique fingerprint.