Periodicity and correlation properties of \(d\)-FCSR sequences (Q702173)

For integers \(d \geq 1\), \(p \geq 2\), let \(X^d-p\) be an irreducible polynomial over the rational numbers with root \(\pi\). Then any element of the field \(\mathbb Q[\pi]\) can be expressed as a fraction \(u/q\) with \(u,q \in \mathbb Z[\pi]\). An element of \(\mathbb Z_\pi\), the ring of \(\pi\)-adic integers consisting of all formal expressions \(\alpha = a_0+a_1\pi+a_2\pi^2+\ldots\), \(0 \leq a_i\leq p-1\), is in \(\mathbb Q[\pi]\) if and only if the coefficient sequence \((a_0,a_1,a_2,\ldots)\) is ultimately periodic. Conversely \(u/q \in \mathbb Q[\pi]\) with \(u,q \in \mathbb Z[\pi]\) lies in \(\mathbb Z_\pi\) if and only if \(q = \sum_{i=0}^{d-1}q_i\pi^i\) with \(\gcd(q_0,p) = 1\). When \(p=2\) the corresponding coefficient sequence may be generated with a simple shift register with carry (FCSR), where the feedback connections are determined by \(q\) and the initial loading by \(u\), \textit{M. Goresky} and \textit{A. Klapper} [Lect. Notes Comput. Sci. 950, 215--222 (1995; Zbl 0879.94019), J. Cryptology 10, 111--147 (1997; Zbl 0874.94029)]. In this paper this algebraic framework is used to analyze these FCSR-sequences. In particular conditions on \(u\) are presented such that the sequence is purely periodic and for certain cases a simpler arithmetic description of these sequences is given. Moreover for \(p=2\) the arithmetic cross-correlation, the with-carry analog of the ordinary cross-correlation (the difference is that the sum of two binary sequences is defined via the sum of the corresponding \(\pi\)-adic numbers), is analyzed. It turns out that certain families of FCSR-sequences have ideal arithmetic cross-correlation, i.e. all nontrivial arithmetic cross-correlations are identically zero.