big-o - 在 O(1) 时间内移动 LFSR 循环？

Question

我想知道是否有一种方法可以结合两个概念:LFSR 和 Barrel Shifters

我正在寻找一种方法，在 O(1) 时间内将 LFSR 循环移动给定的移动次数。

我希望找到的是一个简单的过程，其中我拥有 LFSR 的当前状态以及我希望从该状态转变的次数作为快速/简单过程的参数。

起初我只是想查看所有的抽头，然后将抽头移动 1 并再次查看它们，每次都找到位的移位并将其附加到末尾，但当然这不是 O( 1) 如果我想移动太多次以至于点击会“滑出”原始 LFSR 状态，这会变得很复杂。

如果不是在 O(1) 时间内，是否有比单独执行每个轮类更有效的方法来执行多个轮类？

Answer 1

总的来说，我倾向于说答案是否定的。原因是如果存在这样的算法，那么我们可以在 O(1) 时间内计算 LFSR 生成的序列中的任何给定位。这似乎不太可能在一般情况下实现。

但是，您可以进行一些预计算以稍微加快速度。请注意，在任何固定数量的步骤之后，LFSR 中每个单元的状态都是初始状态的位的线性组合。因此，如果您预先计算每个单元格的线性组合中的系数 1 步、2 步、4 步、8 步等，那么您应该能够在相对较短的时间内向前跳很多步。当然，这实际上只会在您之前提到的“滑落”情况下为您提供有用的加速。