RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2025 Issue 18, Pages 134–137 (Mi pdma700)

Mathematical Methods of Cryptography

On the frequency characteristics in the complications of filter generators output sequences

O. V. Kamlovskii, S. A. Kuz'min, V. V. Mizerov, A. S. Tissin


Abstract: Let $P$ be the finite field with $q$ elements and let $F_1(x),\ldots,F_k(x)$ be pairwise coprimes polynomials over the field $P$ with the conditions $F_1(0)\ne 0$, $\ldots$, $F_k(0)\ne 0$, $\deg F_1(x)=m_1$, $\ldots$, $\deg F_k(x)=m_k$. For every $j=1,\ldots,k$ we consider resilient system of linear recurrent sequences $u_{j1},u_{j2},\ldots,u_{jt_j}$ over the field $P$ with minimal polynomial $F_j(x)$. We study the sequences $v$ constructed by the rule $v(i)=\varphi(v_1(i),\ldots,v_k(i))$, $i\ge 0$, where $v_j(i)=\varphi_j(u_{j1}(i),\ldots,u_{jt_j}(i))$ and $\varphi:P^k\to P$, $\varphi_j:P^{t_j}\to P$ for all $j=1,2,\ldots,k$. Let $N_l(z,v)$ denote the number of appearances of element $z\in P$ in the sequence $v(0),v(1),\ldots,v(l-1)$. When $\varphi_1,\ldots,\varphi_k$ are balanced functions and the function $\varphi$ is bijective for all of its variables, we prove that
$$\left| N_l(z, v) - \frac{l}{q}\right| \le (q-1)\sigma(\varphi) \sigma(\varphi_1)\ldots \sigma(\varphi_k)\left(\frac{4}{\pi^2} \ln T(F) + \frac{9}{5}\right)q^{({m_1+\ldots+m_k})/{2}-1}, $$
where $\sigma(\varphi),\sigma(\varphi_1),\ldots,\sigma(\varphi_k)$ are the curvatures of the functions. We generalize this result to the case of $r$-tuples.

Keywords: finite fields, linear recurrent sequences, linear feedback shift registers, combination generators, filter generators.

UDC: 512.552

DOI: 10.17223/2226308X/18/28



© Steklov Math. Inst. of RAS, 2025