Let S be a string in the set (0,1) produced by taking the AND of the output of t

Question

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table of the AND gate that you will end up with a string consisting of (approximately) 75% zeroes and 25% ones with the ones being psuedorandomly distributed , so to speak, in a string of zeroes. My question is given any number of observed output bits in the sequence , is it possible to predict WHEN the AND gate will output a one ?

Explanation / Answer

Yup, it's possible. This generator is easily broken, as each output bit has degree only two. There's an efficient algorithm that, given the first n bits of output from the generator, will let you predict all the future outputs from the generator with 100% accuracy.

Let x1,

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.