An efficient algorithm for software generation of binary linear recurrences
We describe a method for efficient software generation of binary linear sequences. Suppose that a machine sized word can hold an unsigned integer between 0 and 2(w) - 1 and a binary linear sequence (s((t)))(tgreater than or equal to0) has a characteristic polynomial of degree n having l nonzero coefficients. Then given nw initial bits of the sequence, it is possible to generate successive blocks of (s((t)))(tgreater than or equal to0) of length w bits each. The time required to generate each block is equal to the time required to perform l bitwise XOR operations on machine sized words. Compared to the basic method of sequence generation, this provides a w-fold increase in speed.
linear binary recurrence linear feedback shift register (lfsr)