Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Does anyone know a good proof that a LFSR (with XOR feedback and seeded with non-zero starting state) will never enter zero state?
It is obvious that a zero state will always get stuck in a zero state, but what is the proof that nonzero states cannot cycle into the zero state eventually?
Any linear map (as used in the LFSR next bit computation) gives zero output when loaded by the all zero state, by definition of linearity. So one can never leave the all zero state, which maps onto itself. As @poncho points out the LFSR state mapping is reversible so one can never enter that isolated all zero state from any of the remaining states.
