De Bruijn序列的构造、性能分析和应用

Studying sequences generated by Nonlinear Feedback Shift Registers (NFSRs) is an important research direction in cryptography. A special class of NFSR sequences is the class of de Bruijn sequences with good pseudorandomness. It has extensive applications in many domains such as communication, cryptography, and bioinformatics. This project aims to systematically study de Bruijn sequences using various mathematical tools. The main objective is to propose new construction methods capable of efficiently generating de Bruijn sequences in very large numbers and for larger orders. We also plan to analyze the linear complexity as well as the auto- and cross-correlation properties of the sequences. We will look into emerging applications of such sequences, especially in two domains. First, in communications, we will scrutinize their possible deployment in spread spectrum and construct spreading sequences from de Bruijn sequences. Second, in bioinformatics, the usefulness of de Bruijn and derived sequences in DNA-based data storage has recently been shown. We intend to continue our investigation along this topic. The above motivations strengthen our resolve to investigate NFSR sequences. We believe that at the end of this project we would be able to provide important parameter choices in the design of secure stream ciphers，produce more sequences with desirable properties for secure communication systems, and to solve some basic problems in DNA-based data storage such as determining the information rates and efficient encoding schemes.

非线性反馈移位寄存器(NFSR)序列研究是密码学中重要的研究方向之一。De Bruijn序列是一类特殊的NFSR序列，由于具有良好的伪随机性质，在通信、密码学、生物信息等领域中有广泛的应用。本项目将利用多种数学工具对de Bruijn序列进行系统研究：研究快速生成高阶de Bruijn序列和大de Bruijn序列集的新方法；分析de Bruijn序列的线性复杂度、自相关和互相关性质。同时深入研究de Bruijn序列在如下两个领域中的应用：在通信领域中，研究可用于扩频通信的de Bruijn序列的构造；在生物信息领域中，继续研究de Bruijn序列在基于DNA的数据存储中的应用。该项目的研究将极大促进NFSR序列的研究进展，为建立安全的流密码体制提供重要的选择，为安全通信系统提供更多的性质优良的信号序列，并解决基于DNA的数据存储中的码率、编码方案等基本问题。

非线性反馈移位寄存器(NFSR)序列研究是密码学中重要的研究方向之一。De Bruijn序列是一类特殊的NFSR序列，由于具有良好的伪随机性质，在通信、密码学、生物信息等领域中有广泛的应用。本项目重点研究de Bruijn序列，利用多种数学工具分析de Bruijn序列的性质和各种生成方法，讨论它的推广以及在多个领域中的应用。系统地研究了基于线性反馈移位寄存器(LFSR)利用并圈法生成de Bruijn序列的问题，给出了确定圈结构的方法、判定共轭对的方法和生成de Bruijn序列的具体算法，彻底地解决了这个问题。在生成大周期de Bruijn序列时，利用数学工具把确定共轭对转换为求解Zech对数问题，解决了大周期无法求共轭对问题。考虑了串联移位寄存器的圈结构，通过求解线性方程组来判定圈以及圈的状态，具有很好的创新。利用简单LFSR和并圈法，通过快速判定圈之间的共轭对，得到可以生成指数数量的de Bruijn序列的快速算法。深入研究贪婪算法生成de Bruijn序列问题，得出给定反馈函数和初始状态可以生成de Bruijn序列的充要条件，给出多类新的序列，涵盖了已有典型序列，并利用并圈法思想推广了贪婪算法。推广了de Bruijn序列的结果，得到多类具有重量限制的广义de Bruijn序列的快速生成算法，并对k-置换的广义de Bruijn序列的计数问题进行研究，首次得出了k较小时精确的计数公式。利用de Bruijn序列的研究结果，考虑了基于DNA的数据存储技术，解决了对应DNA编码的码率问题。利用de Burijn序列的研究结果和方法，讨论了多种密码序列的性质和构造方法，对重要的密码序列的复杂度和相关性质进行了深入分析，并构造出多类具有良好密码性质的序列。