Skip to main navigation Skip to search Skip to main content

Distribution of linear and second-highest degree parts of maximum-length feedback functions

  • Beihang University

Research output: Contribution to journalArticlepeer-review

Abstract

De Bruijn sequences are maximum-length sequences generated by feedback shift registers. The study of their feedback functions is very important and has attracted a lot of attention. Many necessary conditions are proposed so far. In this manuscript, based on the complementary and converse properties of de Bruijn sequences, and on some special cross-join pairs in de Bruijn sequences, we give several properties about the proportions of linear part and second-highest degree part of de Bruijn sequence feedback functions. We prove that at least 34 proportion de Bruijn sequence feedback functions of order n have their second-highest degree n-2. We also exhaust all possible Boolean functions and discover all feedback functions of order 6 de Bruijn sequences and feedback functions with second-highest degree 2, of order 7, 8 and 9 de Bruijn sequences. Then we statistically analyze these functions according to their linear parts, second-highest degrees and number of terms. The result shows that their distribution according to degree n-2 parts is almost uniform. But the distribution according to linear parts has significant bias, which means that certain kinds of feedback functions are more likely to generate de Bruijn sequences.

Original languageEnglish
Pages (from-to)121-138
Number of pages18
JournalCryptography and Communications
Volume17
Issue number1
DOIs
StatePublished - Jan 2025

Keywords

  • de Bruijn sequence
  • Distribution
  • Feedback function
  • Linear part
  • Second-highest degree

Fingerprint

Dive into the research topics of 'Distribution of linear and second-highest degree parts of maximum-length feedback functions'. Together they form a unique fingerprint.

Cite this