The Shortest Register With Non-Linear Update for Generating a Given Finite or Periodic Sequence

摘要

The use of feedback and feedforward functions in the construction of binary machines to generate a given finite or periodic sequence allows us to minimize the expected circuit-size. Using these functions a Register with Non-linear Update (RNLUs) is constructed which minimizes the expected circuit-size. However, from the practical standpoint, in order to construct a good stream cipher, the generated sequences must be periodic. It is, therefore, necessary to minimize the expected circuit-size of RNLUs which can generate the given random finite or periodic sequences. In this letter, the properties of feedback shift registers (FSRs) are studied for both random finite and periodic sequences to construct the shortest (minimal variables in the support set of feedback and feedforward functions) RNLUs, which can generate one or more than one-bit output at each clock cycle with asymptotically smaller expected circuit-size from all previously constructed algorithms for generating the given sequences.