将32位LFSR分解为两个16位LFSR，序列相同。

Question

今天我在想这件事。

对于32位的LFSR来说，有可能吗？

x^32 + x^30 + x^28 + x^26 + x^22 + x^21 + x^20 + x^16 + x^14 + x^12 + x^10 + x^8 + x^7 + x^6 + x^2 + x^1 + 1

生成两个16位LFSR，哪个xor对彼此产生32位序列？

编辑:我的措辞不太准确

有一个LFSR序列，其已知明文为64位。

1010111000000011
1111001010111001
0001010011010111
1001001111101101

众所周知，这个LFSR是建立在两个16位LFSR之上的，它们一起给出了与上面的LFSR相同的序列。

是否有可能产生两个未知的16位LFSR？

从技术上讲，你有很多线性关系，

例如，您知道第一个LFSR中的第一个位或第二个LFSR中的第一个位是1。

Answer 1

如果给定的64位序列已知为两个16位LFSR输出的逐位异或和，那么Berlekamp-Massey算法所发现的度-32 LFSR反馈多项式确实是两个16位LFSR的(16位)反馈多项式的乘积，正如@poncho所述，需要将度-32多项式分解为两个16次多项式。但是，请注意，当这两个16次多项式不可约时，这是可以保证的，但是如果这两个16次多项式不是不可约的或者不是相对素数的话，就会有问题。例如，当算法应用于64位序列时，Berlekamp-Massey算法(它找到将生成给定序列的最短LFSR )可能会给出长度小于32的LFSR。