I was wondering whether a LFSR could be approximated by a NN (output or current state). We know that a LFSR is called linear in some sort of mathematical sense, but is that true? Considering it follows Galois field mathematics. So can a Neural Network approximate a LFSR?

Answers with mathematical proof or actual experience is preferred.


According to the abstract of the following book, yes it's possible:

"Prediction of Sequences Generated by LFSR Using Back Propagation MLP"

Abstract: Prediction of the next bit in pseudorandom sequences is one of the main issues in cryptology in order to prove the robustness of the systems. Linear complexity has served as a reference measurement to evaluate the randomness of the sequences, comparing them with the shortest LFSR that can generate those sequences. Several tools based on artificial intelligence have also been used for the next bit prediction, such as the C4.5 classifier. In this paper, we apply a different approach, the back propagation neural networks, to predict the sequences generated by LFSR. The results confirm that these networks can predict the entire sequence knowing less input patterns than techniques based on classifiers.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.