斐波那契 LFSR 计算优化

Question

斐波那契 LFSR 在 wiki 上有描述，非常简单。
我想计算一些斐波那契 LFSR 的周期，并使用生成的序列进行稍后的加密。
让我们以 wiki 为例：

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;
}

问题：
如果我尝试调整 ie 的工作

x³²¹ + x¹⁴ + x¹³ + x¹¹ + 1；

我收到错误：“致命错误：/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 的最小数。不幸的是，我现在无法提供更多信息，我需要几天的时间才能找到我几年前上过的课程的讲义......

一个小例子：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++中验证过。

Answer 2

为了对此进行优化，我们需要记住 PHP 在解析代码方面有很大的开销，因为它没有编译，所以我们需要自己做尽可能多的工作。您应该始终使用 xdebug+KCachegrind（例如）分析您的 CPU/内存敏感代码，以查看 PHP 在哪里浪费了大部分时间。您的代码中只有 12% 花费在 gmp_* 函数计算上，大部分时间花费在代码解析上。

在我的笔记本上（速度相当慢），我的代码运行 2.4 秒，而不是您的代码 3.5 秒，但对于更大的程度，差异应该更明显（例如 19 次幂给出 19 秒与 28 秒）。虽然不多，但也有一些。

我在代码中留下了评论，但如果您有任何疑问 - 请随时询问。我使用函数创建来替换主循环内的“for($i = 1; $i < $n; $i++)”循环。

另外，我认为您应该将 $period 变量的类型更改为 GMP（并将 $period++ 更改为 gmp_* 函数），因为它可能大于系统上的最大整数。

function getPeriod() {
    $polynoms = array(16, 14, 13, 11);


    $highest = $polynoms[0];
    $input = $highest - 1;

    //Delete first element of array - we don't need it anyway
    array_shift($polynoms);

    $polynoms_count = count($polynoms);

    //You always repeat gmp_pow(2, $input) and it's result is constant,
    //so better precalculate it once.
    $input_pow = gmp_pow(2, $input);

    //Start function creation.
    //If you don't use PHP accelerators, then shorter variable names
    //work slightly faster, so I replaced some of names
    //$perion->$r,$bit -> $b, $lfsr -> $l, $polynoms -> $p
    $function_str = '$r=0;';
    $function_str .= 'do{';

    //Now we need to get rid of your loop inside loop, we can generate
    //static functions chain to replace it.
    //Also, PHP parses all PHP tokens, even ';' and it takes some time,
    //So, we should write as much one-liners as we can.
    $function_str .= '$b=gmp_xor($b=$l';


    foreach ($polynoms AS $id => &$polynom) {
        //You always repeat gmp_pow(2, $polynoms[$i]) and it's result is constant,
        //so better precalculate it once.
        $polynom = gmp_pow(2, $highest - $polynom);

        //We create our functions chain here
        if ($id < $polynoms_count - 1) {
            $function_str.=',gmp_xor(gmp_div_q($l,  $p[' . $id . '])';
        } else {
            $function_str.=',gmp_div_q($l,  $p[' . $id . '])';
        }
    }

    //Close all brackets
    $function_str.=str_repeat(')', $polynoms_count);

    //I don't know how to optimize the following, so I left it without change
    $function_str.=';';
    $function_str.='$l = gmp_or((gmp_div_q($l, 2)), (gmp_mul(gmp_and($b, 1), $i_p)));';
    $function_str.='$r++;';
    $function_str.='} while (gmp_cmp($l, 0x1));';
    $function_str.='return $r;';

    //Now, create our funciton
    $function = create_function('$l,$p,$i_p', $function_str);


    //Set begining states
    $lfsr = 0x1;
    $lfsr = gmp_init($lfsr, 16);


    //Run function
    $period = $function($lfsr, $polynoms, $input_pow);

    //Use result
    echo '<br />period = ' . $period;
    return $period;
}