从部分已知序列中找到LFSR的初始状态

Question

如果我知道生成序列的部分，是否有更快的方法（甚至可能）找到 m 位 LFSR 的初始状态？

示例：给定 m=16，反馈多项式为 x^16 + x^12 + x^3 + x^1 + 1，部分序列为 '001010001000011001001110001110010000100011011100000001101000100110010111010100 1100000011111010111000100001101011101011011011101111110000000001111111010010110100001011000101011111100110101010001110000000'

我们能否找出 LFSR 的初始状态是什么？ 如果可以的话，所需的已知序列的最小长度是多少？

上面的示例以所有 1 作为初始状态，并使用以下方式生成：

import pylfsr
L1 = pylfsr.LFSR(fpoly=[16,12,3,1], initstate='ones')
seq = L1.runKCycle(2**16)
seq = L1.arr2str(seq)

期待：我期待任何知道如何编写程序和代码来获得初始状态的人

Answer 1

原则上这是可能的。请参阅：https://en.wikipedia.org/wiki/Berlekamp–Massey_algorithm（有关更多背景信息，另请参阅：https://crypto.stackexchange.com/questions/16203/berlekamp-massey-to-construct -最小-lfsr）

在 Python 中，您还可以根据观察到的位建立适当的线性方程组，然后使用像

z3-solver

这样的包来尝试求解它们。