С конвенцией в эталонная реализация, повторение
$$u_{j+1}:=c\oplus(u_j\lll1)\oplus(u_j\vee(u_j\ggg1))$$
куда $с$ это $n$-битовая константа со всеми битами в $0$ кроме самого правого (иначе сказано $c=0^{n-1}\mathbin\|1$ ), $\оплюс$ побитовое XOR, $\вее$ побитовое ИЛИ, $\lll$ и $\гггг$ - это левое и правое вращение $n$-bit bistring перед оператором по количеству бит после.
Если мы изменим направление сдвигов, это просто отразит (круговое) отображение битов, поэтому структура цикла не изменится.
Имеет ли «Правило 30 с переключением битов» минимальную длину цикла $ {\ кал О} (2 ^ п) $ куда $n$ длина битовых векторов?
Нет, так как для нечетного $n$ существует минимальный цикл длины один. Эта фиксированная точка имеет двоичное выражение чередование $\frac{n+1}2\ 1$ и $\frac{n-1}2\ 0$ (в шестнадцатеричном формате: 55–55 за $n\bmod 4=3$ или же 15–55 за $n\bmod 4=1$). Таким образом, в дальнейшем мы ограничимся даже $n$.
Изучение малого $n$ не показывает никаких доказательств в пользу утверждения: минимальная длина цикла часто $3$, и, кажется, не взлетел.
n начало длины
2 2 0x0
4 5 0x1
6 3 0x03
8 6 0x14
10 3 0x07C
12 5 0x42F
14 7 0x035D
16 33 0x2D34
18 3 0x03E43
20 27 0x00A28
22 3 0x07C87C
24 4 0x102040
26 14 0x0ABB343
28 5 0x2D1E5A3
30 3 0x03E43E43
32 7 0x1B3AFA05
34 3 0x07C87C87C
36 13 0x0217F5A73
Для случайной функции ожидаемый размер цикла, начинающегося со случайной точки, близок к $\sqrt{\pi2^n/8}=\mathcal O(2^{n/2})$; см. Флажоле и Одлызко Статистика случайного сопоставления. Наименьший цикл обычно намного меньше (хотя я не знаю ожидаемого распределения). Таким образом, заявленная длина цикла была бы несколько неожиданной.
С другой стороны, функция имеет очень медленную диффузию, поэтому она очень далека от случайной функции.
Вот график для $n=14$.
