# Shift-rotating random number generator

Let $$\omega$$ denote the set of non-negative integers. For $$n\in\omega\setminus\{0\}$$ define the rotation function $$\text{rot}_n:\{0,1\}^n \to \{0,1\}^n$$ by $$x \mapsto x'$$ where

• $$x'_k = x_{k+1}$$ for $$k\in\{0,\ldots, n-2\}$$, and
• $$x_{n-1} = x_0$$.

Let $$\bar{0}_n \in \{0,1\}^n$$ be the constant $$0$$-sequence of length $$n$$. Fix $$s_0\in \{0,1\}^n$$ and define a function $$f_{n,s_0} : \omega\to \{0,1\}^n$$ inductively by setting

• $$f_{n,s_0}(0) = \bar{0}_n$$, and
• $$f_{n,s_0}(k+1) = f_{n,s_0}(k) \;\oplus \; \text{rot}_n(f_{n,s_0}(k)) \; \oplus \; s_0$$.

(By $$\oplus$$ we denote componentwise addition in $$\mathbb{Z}/2\mathbb{Z}$$, or equivalently, bitwise XOR.)

Question. For what values of $$n\in\omega\setminus\{0\}$$ is there $$s_0\in \{0,1\}^n$$ such that the image of the function $$f_{n,s_0} : \omega\to \{0,1\}^n$$ is all of $$\{0,1\}^n$$ (i.e. $$f_{n,s_0} : \omega\to \{0,1\}^n$$ is surjective)?

• What does this have to do with cryptography? The above generator is obviously not cryptographically secure. BTW: the standard notation for the set of nonnegative integers is $\mathbb{N}$ Apr 2 at 16:41
• @poncho: It seems that there is no canonical/universal notation for the set of non-negative integers. Regarding the usage of $\omega$, see, for example, this comment on Mathoverflow. Apr 3 at 4:27
• Why is LFSR cryptographically secure, but not the above procedure? But maybe it's better to ask the question on mathoverflow Apr 3 at 7:49

I think only for $$n=1$$.
The map $$x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0$$ is 2-to-1 since $$x$$ and $$x\oplus 1111\ldots 1$$ both map to the same value. It follows that half of the values of $$\{0,1\}^n$$ do not lie in the image of this map. We can capture at most one missing value with our start point $$0$$, but the remaining $$2^{n-1}-1$$ points will never occur in the image.
• Thanks for the beautiful observation that $x$ and $x + 111\ldots111$ map to the same value! Apr 3 at 17:18