Feedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR f is said to be reducible if all the output sequences of another FSR g can also be generated by f and the FSR g costs less memory than f . A FSR is said to be decomposable if it has the same set of output sequences as a cascade connection of two FSRs. Two polynomial‐time computable transformations from Boolean circuits to FSRs are proposed such that the output FSR of the first (resp. second) transformation is irreducible (resp. indecomposable) if and only if the input Boolean circuit is satisfiable. Through the two transformations, it is proved that deciding irreducibility (indecomposability) of FSRs is NP ‐hard. Additionally, FSRs are constructed to show that there exist infinitely many irreducible (resp. indecomposable) FSRs which are decomposable (resp. reducible).

Lattice‐based encryption schemes are significant cryptographic primitives to defend information security against quantum menace, and the decryption failure rate is related to both theoretical and realistic security. We quantitatively analyze how the floating‐point arithmetic and neglecting small probabilities impact the precision, and propose a new effective and efficient test of the failure probability. Therein explicit criteria are given to select the floating‐point datatype and to decide which small probabilities should be abandoned. Furthermore, the outcome is theoretically ensured to meet a given precision. Moreover, by combining the heuristic estimate and the precise simulation, this test is more efficient than previously neglecting small probabilities in a practical way.