Deciding Irreducibility/Indecomposability of Feedback Shift Registers is NP-hard

Lin Wang

Feedback shift registers(FSRs) are a fundamental component in electronics and secure communication. An FSR $f$ is said to be reducible if all the output sequences of another FSR $g…