An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

作者：Kuijper M^*; Pinto R

来源：Designs, Codes and Cryptography, 2017, 83(2): 283-305.

DOI：10.1007/s10623-016-0226-3

• Iterative algorithms
• Minimal basis
• Parametrization
• Polynomial modules
• Sequences
• Shift registers

The construction of shortest feedback shift registers for a finite sequence S1,..., S-N is considered over finite chain rings, such as Z(pr). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers S-1,..., S-N, thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with S-1, and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence SN,..., S-1. The complexity order of the algorithm is shown to be O( rN(2)).

• 出版日期2017-5