|
Automata Theory
Peculiar properties of the $p$-linear decomposition of $p$-linear functions in terms of the shift-composition operation
I. V. Cherednik MIREA – Russian Technological University (RTU MIREA), Moscow, Russia
Abstract:
We analyze the shift-composition operation on discrete functions which occurs under homomorphisms of finite shift registers. We prove that for a prime $p$, in the class of all functions that are linear in the extreme variables, the notions of reducibility and $p$-linear reducibility coincide for $p$-linear functions. Furthermore, we show that a linear function irreducible in the class of all linear functions has no $p$-linear divisors that are bijective in the rightmost variable, and in some cases, has no $p$-linear divisors at all.
Keywords:
shift register, homomorphisms of shift registers, shift-composition, finite fields, $p$-linear functions, matrix polynomial factorization, skew polynomials, skew linear recurrence sequences.
Received: 04.06.2020 Revised: 07.11.2020 Accepted: 08.11.2020
Citation:
I. V. Cherednik, “Peculiar properties of the $p$-linear decomposition of $p$-linear functions in terms of the shift-composition operation”, Probl. Peredachi Inf., 56:4 (2020), 64–80; Problems Inform. Transmission, 56:4 (2020), 358–372
Linking options:
https://www.mathnet.ru/eng/ppi2329 https://www.mathnet.ru/eng/ppi/v56/i4/p64
|
Statistics & downloads: |
Abstract page: | 98 | Full-text PDF : | 18 | References: | 18 | First page: | 3 |
|