Proof of Rueppel's linear complexity conjecture (Corresp.)
Zong-Duo Dai · IEEE Transactions on Information Theory · 1986
Rueppel has conjectured that, for alln\geq 1, the subsequence consisting of the firstndigits of the binary sequence(1,1,0,1,0,0,0,1,0^{7},1,0^{15},1, \cdots )has linear complexity\lfloor (n + 1)/2 \rightfloor. This conjecture is proved, and a minimum length generator is found for eachn. The proof utilizes properties of an element in an extension field of the field of rational functions over GF(2).