Linear decomposition of discrete functions in terms of shift-composition operation

We investigate the shift-composition operation of discrete functions that arises under shift register's homomor-phisms. For an arbitrary function over a finite field, all right linear decompositions are described in terms of shift-composition. Moreover, we study the possibility for representing an arbitrary function by a shift-composition of three functions such that both external functions are linear. It is proved that in the case of a simple field, the concepts of reducibility and linear reducibility coincide for linear functions and quadratic functions that are linear in the external variable.

Keywords

Authors

References