一个LFSR需要多少位才能生成特定数量的序列？

Question

我需要生成16次伪随机的64位数据序列。线性反馈移位寄存器(LFSR)应该有多少位才能做到这一点？

也就是说，初始种子的位数是多少？这个数字怎么算？我们能把这个数目减到最少吗？它应该是一个固定的位数吗？

Answer 1

带有n-bit LFSR的本原反馈多项式将遍历所有2^n-1可能的非零状态.您将需要一个LFSR来生成16\times 64 = 1024位。一个11位的LFSR将循环通过2^{11} - 1 = 2047状态并输出尽可能多的比特，因此就您的目的而言，11位状态就足够了。

如果反馈多项式不是本原的，则周期是不可预测的，但不是最大的。x^{11}+x^9+1是一个适用于最大长度11位LFSR的原始多项式的例子.

非常重要的是要知道LFSR并不是加密安全的。在只知道密钥流的n位(如果反馈多项式是秘密的话，则为2n位)之后，可以中断-bit LFSR。