Оптимизация расчета Фибоначчи LFSR

Question

Фибоначчи LFSR описывается в вики, все довольно просто.Я хотел бы вычислить период некоторого LFSR Фибоначчи и использовать сгенерированную последовательность для шифрования позже.Давайте возьмем пример из вики:

х ¹⁶ + х ¹⁴ + х ¹³ + х ¹¹ + 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;
}

Проблема: Если я попытаюсь модулировать работу, например,

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

я получил ошибку: " Неустранимая ошибка: превышено максимальное время выполнения в 30 секунд в /var/www/Dx02/test.php";Могу ли я как-то оптимизировать (ускорить :)) расчет?Любая помощь приветствуется.Спасибо и извините за мой английский.

Answer 1

Вы просто не можете сделать это таким образом с полиномом, как x ^ 321 + ...;

Если полином выбран правильно, вы получите длину периода 2^ 231 -1, и это примерно 4,27 * 10 ^ 96.Если я не ошибаюсь, считается, что это число превышает количество атомов во вселенной ... (Строго говоря, я имею в виду опубликованный C-код, поскольку я не знаю php, но это, безусловно, не имеет значения.)

Тем не менее, существует математический метод для вычисления длины периода без атаки методом грубой силы .К сожалению, это не может быть объяснено в нескольких строках.Если вы хорошо разбираетесь в математике (особенно в вычислениях в конечных полях), я буду рад найти для вас полезную справку.

РЕДАКТИРОВАТЬ: Первый шаг в вычисленииПериод LFSR, полученный с использованием полинома p (x), заключается в получении факторизации p (x) mod 2, т.е. в GF (2).Для этого я рекомендую использовать программное обеспечение, такое как Mathematica или Maple, если оно доступно.Вы также можете попробовать свободно доступный Sage, см., Например, http://www.sagemath.org/doc/constructions/polynomials.html для получения подробной информации об использовании.

Период p (x) определяется порядком e, что означает наименьшее число, такое что p (х) ныряет х ^ е + 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 (например), чтобы увидеть, где PHP тратит большую часть своего времени.С вашим кодом только 12% тратится на вычисления функций gmp_ *, большую часть времени тратится на разбор кода.

На моем ноутбуке (это довольно медленно) мой код выполняется 2,4 с вместо 3,5 с для вашегокод, но для большей степени разница должна быть более заметной (например, 19 мощность дает 19 против 28 секунд).Это не много, но немного.

Я оставил комментарии внутри кода, но если у вас есть вопросы - не стесняйтесь спрашивать.Я использовал создание функции, чтобы заменить этот цикл 'for ($ i = 1; $ i <$ n; $ i ++)' внутри вашего основного цикла. </p>

Кроме того, я думаю, вам следует изменить тип переменной $ periodв GMP (и $ period ++ to gmp_ * function), поскольку она может быть больше максимального целого числа в вашей системе.

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