A linear feedback shift register is a shift register whose input is the exclusiveor of some of its outputs. The outputs that influence the input are called taps. A maximal LFSR produces an nsequence, unless it contains all zeros. The tap sequence of an LFSR can be represented as a polynomial mod 2  called the feedback polynomial. For example, if the taps are at positions 17 and 15 (as below), the polynomial is x^{17} + x^{15} + 1. If this polynomial is primitive, then the LFSR is maximal. LFSR's can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudorandom sequence, such as directsequence spread spectrum radio. Given an output sequence you can construct a LFSR of minimal size by using the BerlekampMassey algorithm A Galois LFSR, or a LFSR in Galois configuration is a variation on typical LFSR design. In Galois configuration, the output is individually xor'ed with each tap, before becoming the new input. Galois LFSRs do not concatenate every tap to produce the new input, thus it is possible for each tap to be computed in parallel, increasing the speed of execution.
Use in cryptography
LFSRs have long been used as a pseudorandom number generator for use in stream ciphers (especially in military cryptography), due to the ease of construction from simple electromechanical or electronic circuits, long periods, and very uniformly distributed outputs. However the outputs of LFSRs are completely linear, leading to fairly easy cryptanalysis. Three general methods are employed to reduce this problem in LFSR based stream ciphers:  Nonlinear combination of several bits from the LFSR state;
 Nonlinear combination of the outputs of two or more LFSRs; or
 Irregular clocking of the LFSR.
Important LFSRbased stream ciphers include A5/1, A5/2, and the shrinking generator.
External links  http://www.maximic.com/appnotes.cfm/appnote_number/1743
 http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html
