Journal article

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

M Kuijper, R Pinto

DESIGNS CODES AND CRYPTOGRAPHY | SPRINGER | Published : 2017

Abstract

The construction of shortest feedback shift registers for a finite sequence S1, … , SN is considered over finite chain rings, such as Zpr. A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers S1, … , SN, thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with S1, 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, … , S1. The complexity order ..

View full abstract

Grants

Awarded by Portuguese Foundation for Science and Technology Fundacao para a Ciencia e a Tecnologia (FCT)


Funding Acknowledgements

We would like to thank Anna-Lena Trautmann as well as the anonymous reviewers for helpful comments. Partly supported by the Australian Research Council (ARC); partly supported by Portuguese funds through the Center for Research and Development in Mathematics and Applications (CIDMA), and The Portuguese Foundation for Science and Technology Fundacao para a Ciencia e a Tecnologia (FCT), within project UID/MAT/04106/2013