基于多数的反馈移位寄存器

Question

线性反馈移位寄存器的工作方式是采用固定长度的位串b\in\{0,1\}^n，以及固定的“抽头”(位置)，并将异或应用于抽头，给出一个输出位，在移位后附加到b。

XOR是一个线性函数。在固定的抽头集上可以使用的一个自然非线性函数是一种“多数票”，其工作原理如下:如果大多数抽头为0，则输出1，反之亦然。(为此，最好有一个奇数的水龙头。)

基于多数的反馈移位寄存器的一个简单实现可以找到这里。

当然，一遍又一遍地运用这个“多数票”程序，最终会得到期刊。

有个问题。给定固定的位长n，选择合适的起始字符串b\in \{0,1\}^n和合适的抽头集的周期最大长度的下限是什么？

而且，我也无法确定这个概念是否和在哪里被研究过。

Answer 1

我把这个问题理解为问b(n) (最大的可能)，这样我们就可以显示不同的抽头点(以奇数表示)和n-bit状态，从而导致周期序列(最短)至少是b(n)步骤。

我用b(n)=2n-2为n\ge3做了一个构造。这些抽头是从MVFSR中删除的接下来的三位。状态为全零，除了下一个退出MVFSR的位.下面是一个n=8的例子:时间从左到右，MVSFR向下移动，下一个位进入顶部，三个点击用*标记。

   0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0
   0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
   0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
   0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0
   0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
*  0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0
*  0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
*  1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1

如果我们只允许一个水龙头，我们就可以到达b(n)=2n。

我希望b(n)能够得到改进(增加)，也许会变成指数级，但它已经超过了1 of 这个答案和2 of 这句话。

Answer 2

我会犹豫要求一个比1更好的下限。

我们注意到，对于多数投票反馈移位寄存器(以下简称MVFSR)，如果存在2k+1抽头，并且在任何时候寄存器的填充最多都是k零(分别是最多的k值)，那么寄存器将随后填充1 (分别为零)，并达到1的循环。

同样地，人们认为存在大量的实体主义，因为带有大量零填充稀疏的MVFSR很可能产生零反馈，而具有大量零填充的密集填充很可能产生一个反馈。启发式地，这将推动填充密度从1/2和向上述简并。

有可能产生MVFSR，在算术级数中设置的抽头会退化为较小寄存器的交织，从而达到与较小寄存器数目相等的稳定的长度周期，但这并不是一个好主意。

人们还可以注意到，MVFSR从填充到填充的地图有许多2对1的地图，这在最后的周期长度上有一个很差的上限。通常，如果第一个k+1抽头的2k为0或1(即在第一个2k抽头位置上没有确切的k零和k 1)，则填充最老的抽头位与反馈无关，因此我们创建了一个二对一。

Answer 3

我已经写了一些代码，只是蛮力，点击配置和小寄存器大小的起始值。所以我有一些价值，而不是一个分析结果。当然，结果取决于代码中没有任何bug (https://github.com/bmm6o/MVFSR)。

for width 4, max cycle length is 8
for width 5, max cycle length is 10
for width 6, max cycle length is 12
for width 7, max cycle length is 14
for width 8, max cycle length is 48
for width 9, max cycle length is 48
for width 10, max cycle length is 80
for width 11, max cycle length is 108
for width 12, max cycle length is 140
for width 13, max cycle length is 270
for width 14, max cycle length is 270
for width 15, max cycle length is 270
for width 16, max cycle length is 480
for width 17, max cycle length is 752
for width 18, max cycle length is 1520

从较小的值泛化可能是有风险的，但当宽度增加2时，它似乎会增加大约一倍。这个序列在OEIS中不存在。

你可能已经意识到了这一点，但是你的MVFSR进化的方式使得大多数州都有两个预图像。我不知道如何用它来对周期长度分布进行概率估计，但这似乎是有帮助的。

对于大多数密码学而言，对最大周期长度设置一个下限并不是最重要的问题。更重要的是最小长度，或者至少是一种描述和避免短周期的方法。这样，MVFSR就有一个严重的问题。在最优抽头选择下，只有2n长度的循环。