В академической литературе [2] обосновано, что M-последовательности строго соответствуют первому и третьему постулатам Голомба. В то же время работа [3] выдвигает гипотезу: любая двоичная последовательность, удовлетворяющая критериям R1 и R3, фактически является M-последовательностью. В связи с этим возникает фундаментальный вопрос: какую роль играет второй постулат в контексте последовательностей максимальной длины? Чтобы разобраться в этом, необходимо детально рассмотреть природу M-последовательностей, научный вклад Соломона Голомба и специфику предложенных им критериев псевдослучайности.
M-последовательности: природа и характеристики
M-последовательность (последовательность максимальной длины, англ. maximum-length sequence, MLS) представляет собой псевдослучайный двоичный цикл, формируемый регистром сдвига с линейной обратной связью (РСЛОС). Характерной чертой такой последовательности является достижение максимально возможного периода для заданной конфигурации регистра. С математической точки зрения она классифицируется как линейная рекуррента над конечным полем \( GF(2) \).
Для дальнейшего анализа примем, что мы имеем дело с чисто периодической структурой с глубиной рекурсии \( n \) и периодом \( r = 2^n — 1 \). Саму последовательность обозначим как \( \gamma = \gamma_1, \gamma_2, \dots \).
Критерии псевдослучайности: постулаты Голомба
Соломон Голомб, известный широкой аудитории как популяризатор полимино, внес значительный вклад в криптографию и теорию кодирования. В своем фундаментальном труде [1] он сформулировал три постулата, определяющих степень «случайности» последовательностей, генерируемых конечными автоматами. Соответствие этим критериям критически важно для потоковых шифров: любые статистические аномалии могут стать ключом к дешифровке для злоумышленника. Рассмотрим эти требования:
- R1 (Баланс): На отрезке периода \( r \) общее количество нулей и единиц должно быть максимально приближено друг к другу (разница не более единицы).
- R2 (Распределение серий): Серией называется непрерывная цепочка идентичных символов. Согласно постулату, примерно 1/2 всех серий должны иметь длину 1, 1/4 — длину 2, 1/8 — длину 3 и так далее.
- R3 (Автокорреляция): Значения автокорреляционной функции \( C_\gamma(\tau) = \sum_{t=1}^{r} \chi(\gamma_t + \gamma_{t+\tau}) \) должны стремиться к нулю для всех сдвигов \( \tau \), отличных от нуля (где \( \chi \) — отображение из \( F_2 \) в \(\{ -1, 1 \}\)).
Доказательство соответствия M-последовательностей постулату R2
Для идентификации серии из \( k \) единиц необходимо обнаружить в последовательности фрагмент вида \( 011\dots110 \) длиной \( k+2 \). Анализируя состояния регистра \( S_i = (\gamma_i, \dots, \gamma_{i+n}) \), мы можем подсчитать количество комбинаций, где начальные элементы соответствуют заданному шаблону. В M-последовательности таких состояний ровно \( 2^{n-k-2} \).
Важно отметить, что серии длиной более \( n \) невозможны, так как комбинация из \( n \) единиц встречается в цикле лишь однажды. Аналогичная логика применима и к сериям нулей. Суммируя все найденные варианты, получаем общее количество серий:
\( 2\sum_{k=1}^{n-2}2^{n-k-2} = 2(2^{n-2}-1) \)
Учитывая, что в силу максимальности периода состояния \( S_i \) проходят через все возможные ненулевые векторы, доля серий длины \( k \) составляет:
\( \frac{2 \cdot 2^{n-k-2}}{2(2^{n-2}-1)} \approx \frac{1}{2^k} \)
Это подтверждает, что M-последовательности идеально вписываются в рамки второго постулата.
Последовательности Лежандра
Пусть \( p \) — нечетное простое число. Символ Лежандра \( (\frac{n}{p}) \) определяется следующим образом: он равен 1, если \( n \) является квадратичным вычетом по модулю \( p \), и -1 в противном случае. Последовательность, составленная из таких символов, также демонстрирует псевдослучайные свойства.
Для таких последовательностей постулат R1 требует равенства количества положительных и отрицательных значений. Это условие выполняется, так как количество квадратичных вычетов по модулю \( p \) в точности равно количеству невычетов.
Доказательство: Заметим, что \( x^2 \equiv (x-p)^2 \pmod{p} \). Это ограничивает число вычетов величиной \( (p-1)/2 \). Поскольку среди квадратов чисел от \( 1 \) до \( (p-1)/2 \) нет совпадающих остатков по модулю \( p \), мы получаем ровно \( (p-1)/2 \) вычетов и столько же невычетов.
Что касается автокорреляции (R3), для последовательностей Лежандра она принимает вид:
\( C_{\tau} = \begin{cases} p, & \text{если } \tau = 0 \\ -1, & \text{если } p = 4k-1 \\ -3 \text{ или } 1, & \text{если } p = 4k+1 \end{cases} \)
Интересно, что постулат R2 для последовательностей Лежандра выполняется далеко не всегда. Например, при \( p = 11 \) распределение серий нарушается: серии длины 3 встречаются чаще, чем серии длины 2, что прямо противоречит критериям Голомба.
Разностные множества Адамара
Существует особый класс структур, удовлетворяющих R1 и R3 — это так называемые последовательности Адамара. Они неразрывно связаны с циклическими разностными множествами с параметрами \( v = 4n-1, k = 2n-1, \lambda = n-1 \).
Выделяют три основных типа таких конструкций:
- Случай простого \( v = 4n-1 \): сюда относятся последовательности Лежандра и последовательности Холла, базирующиеся на вычетах шестой степени (применимо для \( p = 4A^2 + 27 \)).
- Случай произведения \( v = p(p+2) \): последовательности Якоби, являющиеся развитием идей Лежандра.
- Случай \( v = 2^t — 1 \):
- Классические M-последовательности.
- Последовательности Гордона–Миллса–Уэлча (GMW).
- Уникальные примеры, обнаруженные Баумертом, Фредериксеном и другими исследователями в ходе вычислительных экспериментов для малых \( t \).
Список источников
- Golomb S. W. Shift Register Sequences. Laguna Hills, CA: Aegean Park, 1982.
- Агиевич С. В. Линейные рекуррентные последовательности. [Электронный ресурс].
- Теория кодирования: Линейные коды и последовательности. БГУ.
- Song H.-Y., Golomb S. W. On the existence of cyclic Hadamard difference sets. IEEE Trans. Inform. Theory, 1994.
- Hofer R., Winterhof A. Autocorrelation of Legendre sequences and their variations. 2016.
- Perron O. Bemerkungen über die Verteilung der quadratischen Reste. Math. Z., 1952.
- Hall M., Jr. A survey of difference sets. Proc. Amer. Math. Soc., 1956.
- Stanton R. G., Sprott D. A. A family of difference sets. Canadian J. Math., 1958.
