Pseudo-Random-Generator
移位旋轉隨機數發生器
讓 $ \omega $ 表示非負整數的集合。為了 $ n\in\omega\setminus{0} $ 定義旋轉函式 $$ \text{rot}_n:{0,1}^n \to {0,1}^n $$經過 $ x \mapsto x’ $ 在哪裡
- $ x’k = x{k+1} $ 為了 $ k\in{0,\ldots, n-2} $ ， 和
- $ x_{n-1} = x_0 $ .
讓 $ \bar{0}n \in {0,1}^n $ 成為常數 $ 0 $ - 長度序列 $ n $ . 使固定 $ s_0\in {0,1}^n $ 並定義一個函式 $ f{n,s_0} : \omega\to {0,1}^n $ 通過設置歸納
- $ f_{n,s_0}(0) = \bar{0}_n $ ， 和
- $ f_{n,s_0}(k+1) = f_{n,s_0}(k) ;\oplus ; \text{rot}n(f{n,s_0}(k)) ; \oplus ; s_0 $ .
（經過 $ \oplus $ 我們表示在 $ \mathbb{Z}/2\mathbb{Z} $ ，或等效地，按位異或。）
**問題。**對於什麼值 $ n\in\omega\setminus{0} $ 在那兒 $ s_0\in {0,1}^n $ 這樣函式的圖像 $ f_{n,s_0} : \omega\to {0,1}^n $ 是所有 $ {0,1}^n $ （IE $ f_{n,s_0} : \omega\to {0,1}^n $ 是滿格的）？
我認為只為 $ n=1 $ .
地圖 $ x\mapsto x\oplus\mathrm{rot}(x)\oplus s_0 $ 是 2 比 1，因為 $ x $ 和 $ x\oplus 1111\ldots 1 $ 兩者都映射到相同的值。因此，一半的值 $ {0,1}^n $ 不要躺在這張地圖的圖像中。我們的起點最多可以擷取一個缺失值 $ 0 $ , 但剩下的 $ 2^{n-1}-1 $ 點永遠不會出現在圖像中。