首页  > 学术科研 > 学术交流


来源:代数编码团队  作者:数学科研     日期:2017/11/20 22:49:41   点击数:252  


报告内容:DeBruijn sequences from LFSRs



报告摘要:A binary de Bruijn sequence of order $n$ is a cyclic sequence of period $2^n$, in which each $n$-bit pattern appears exactly once. De Bruijn sequences have important applications in cryptography, communication and coding theory for their desirable characteristics such as long periods, large complexities and good randomness properties. For example, de Bruijn sequences are useful in random number generation, which is essential for secure communication especially for generation of cryptographic keys, nonces and salts; in stream cipher designs, feedback shift registers (FSRs) that can generate de Bruijn sequences are commonly used. All three hardware-oriented Ecrypt eStream competition finalists, namely Trivium, Grain and Mickey use these registers as their main building block. However, the theory of nonlinear FSRs is far less developed and comprehended in comparison with that of linear FSRs). It is well known that the number of unique de Bruijn sequences is equal to $2^{2^{n-1}-n}$, however only a very small number are known to have simple and efficient constructions, and the properties of the constructed sequences are not well understood. This fact would be best captured by a quote in Fredricksen’s excellent survey: ``\textit{When a mathematician on the street is presented with the problem of generating a de Bruijn sequence, one of the three things happens: he gives up, or produces a sequence based on a primitive polynomial, or produces the prefer-one sequence. Only rarely a new algorithm is proposed.}” Fredricksen’s statement might appear a little subjective, unfortunately it turned out to be more or less true in the last 40 years.


Although there wasn’t much development in the research on deBruijn sequences, some constructions of de Bruijn sequences from LFSRs have been proposed in recent years. This talk will introduce recent research progress in this direction.

报告人简介:李春雷于2001 至2008 年间在湖北大学完成数学系学士学位和密码学硕士学位。在2008 至2014年期间,李春雷先后就读于武汉大学,挪威卑尔根大学,并相应取得信息安全专业博士学位和可靠通信专业博士学位;现就职于卑尔根大学。在攻读硕士和博士学位期间,李春雷在国际知名期刊上发表高质量学术论文20 余篇,其中包括在计算机学会(CCF)建议的A 类期刊IEEE Transaction on Information Theory 上发表论文6篇。