c# - Fibonacci LFSRs 计算优化

Question

Fibonacci LFSR wiki上有介绍，很简单。
我想计算一些 Fibonacci 的 LFSR 的周期，然后使用生成的序列进行加密。
让我们以维基为例:

x¹⁶ + x¹⁴ + x¹³ + x¹¹ + 1;

//code from wiki:
include <stdint.h>
uint16_t lfsr = 0xACE1u;
unsigned bit;
unsigned period = 0;
do {
  /* taps: 16 14 13 11; characteristic polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
  bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
  lfsr =  (lfsr >> 1) | (bit << 15);
  ++period;
} while(lfsr != 0xACE1u);

到目前为止我在 php 中的弱尝试:

function getPeriod(){
    $polynoms = array(16, 14, 13, 11);
    $input = $polynoms[0] - 1;
    $n = sizeof($polynoms);
    for ($i = 1; $i < $n; $i++)
        $polynoms[$i] = $polynoms[0] - $polynoms[$i];
    $polynoms[0] = 0;
    //reversed polynoms == array(0, 2, 3, 5);
    $lfsr = 0x1; //begining state       
    $period = 0;
    //gmp -- php library for long numbers;
    $lfsr = gmp_init($lfsr, 16);
    do {            
        $bit = $lfsr; //bit = x^16 >> 0;

        for($i = 1; $i < $n; $i++) {
            //bit ^= lfsr >> 2 ^ lfst >> 3 ^ lfst >> 5;
            $bit = gmp_xor($bit, ( gmp_div_q($lfsr, gmp_pow(2, $polynoms[$i])) ));                  
        }
        //bit &= 1;
        $bit = gmp_and($bit, 1);            
        //lfsr = $lfsr >> 1 | $lsfr << (16 - 1);
        $lfsr = gmp_or( (gmp_div_q($lfsr, 2)), (gmp_mul($bit, gmp_pow(2, $input))) );

        $period++;
    } while (gmp_cmp($lfsr, 0x1) != 0);
    echo '<br />period = '.$period;
    //period == 65535 == 2^16 - 1; -- and that's correct;
            //                        I hope, at least;
    return $period;
}

问题:
如果我尝试调整 i.e. 的工作

x³²¹ + x¹⁴ + x¹³ + x¹¹ + 1;

我得到一个错误:“ fatal error :/var/www/Dx02/test.php 中超过 30 秒的最大执行时间”；

我能以某种方式优化(加速 :) )计算吗？

感谢任何帮助。谢谢，请原谅我的英语不好。

Answer 1

您根本无法使用像 x^321 + ... 这样的多项式来做到这一点；

如果多项式选择得当，周期长度为 2^231 -1，这大约是 4.27 *10^96。如果我没记错的话，这个数字是被认为超过了宇宙中的原子数...(严格来说，我指的是发布的 C 代码，因为我不懂 php，但这肯定没有区别。)

但是，有一种数学方法可以计算周期的长度，而无需进行蛮力攻击。不幸的是，这不能用几行来解释。如果您有扎实的数学背景(尤其是有限域的计算)，我很乐意为您寻找有用的引用资料。

编辑:计算使用多项式 p(x) 获得的 LFSR 周期的第一步是获得 p(x) mod 2 的因式分解，即在 GF(2) 中。为此，我建议使用 Mathematica 或 Maple(如果可用)等软件。您也可以尝试免费提供的 Sage，例如参见http://www.sagemath.org/doc/constructions/polynomials.html了解使用详情。

p(x) 的周期由其阶数 e 给出，这意味着 p(x) 减去 x^e+1 的最小数。不幸的是，我目前无法提供更多信息，我需要几天时间才能找到我几年前上过的一门类(class)的讲义...

一个小例子:p(x) = (x^5+x^4+1) = (x^3+x+1)*(x^2+x+1)，各个周期为2^ 3-1=7 和 2^2-1=3，由于多项式的因式各不相同，所以p(x)的周期是3*7=21，我在C++中也验证过了。