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))
t
0 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))
t0 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.
Key words Linear Binary Recurrence - Linear feedback shift register (LFSR)
Acknowledgement We would like to thank Subhamoy Maitra, Sandeepan Choudhury and Kishan Chand Gupta for discussions and helpful comments. We would also like to thank Professor Harald Niederreiter for pointing out that Lemma 2 can be easily derived from Corollary 1 of [4]. Finally, we thank the reviewers for pointing out several typos in the paper.