Fibonacci LFSR is described on wiki, it's pretty simple.
I'd like to calucate the period of some Fibonacci's LFSR and use generated sequence for ciphering later.
Let's take and example from wiki:
x16 + x14 + x13 + x11 + 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);
My weakly try so far in 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;
}
Problem:
If i try to modulate work of i.e.
x321 + x14 + x13 + x11 + 1;
i got an error:"Fatal error: Maximum execution time of 30 seconds exceeded in /var/www/Dx02/test.php";
Can i somehow optimize (accelerate :) ) the calculation?
Any help is appreciated. Thank you and excuse me for my English.