Cryptography and Communications Компьютерные сети и коммуникации

Pattern sets for $$\mathbb {F}_q$$-sequences invariant under the continued fraction operator K (the Berlekamp-Massey algorithm)

Mónica del P. Canales, Sergio Jara C., Michael Vielhaber
Springer Nature · 2025-08-11 · DOI 10.1007/s12095-025-00833-3

Аннотация

Abstract We show that for all infinite sequences $$s\in \mathbb {F}_q^\omega $$ s ∈ F q ω , two properties are preserved under forward and backward application of the continued fraction operator K (the modified Berlekamp-Massey Algorithm). The first preserved property is that if $${\text {supp}}(s)\subset [r]_n$$ supp ( s ) ⊂ [ r ] n , that is, the positions of the nonzero elements of s lie in a certain residue class modulo n , then also $${\text {supp}}(\textbf{K}(s))\subset [r]_n$$ supp ( K ( s ) ) ⊂ [ r ] n . The other property applies only to fields with characteristic two: if the sequence consists of symbol pairs $$(s_{2n-1},s_{2n}$$ ( s 2 n - 1 , s 2 n ) with $$s_{2n} = \alpha s_{2n-1}$$ s 2 n = α s 2 n - 1 for a fixed $$\alpha \in \mathbb {F}_{2^k}$$ α ∈ F 2 k , for all $$n\in \mathbb {N}$$ n ∈ N and $$t:= \textbf{K}(s)$$ t : = K ( s ) , then also $$t_{2n} = \alpha t_{2n-1}$$ t 2 n = α t 2 n - 1 for all $$n\in \mathbb {N}$$ n ∈ N . We furthermore determine all sets $$V\subset \mathbb {F}_q^m$$ V ⊂ F q m invariant under K for certain finite fields, that is, for which $$\textbf{K}:V^\omega \rightarrow V^\omega $$ K : V ω → V ω and conjecture that there are no others even in the general case. In the binary case, $$\mathbb {F}_{2^k}$$ F 2 k , we apply the result to a certain binary tree associated with the isometry K .

Читать у издателя →