M-последовательности, последовательности Лежандра, Якоби и разностные множества Адамара / Хабр

В лекции [2] доказывается, что M-последовательность удовлетворяет первому и третьему постулатам Голомба, а в [3] формулируется гипотеза Голомба о том, что если двоичная последовательность удовлетворяет постулатам R1 и R3, то она является M-последовательностью. Возникает закономерный вопрос, а как же второй постулат связан с M-последовательностями? Но обо всём по порядку и начнём с того, что такое M-последовательность, кто такой Голомб, и что за постулаты он выдвигал.

M-последовательности

М-последовательность или последовательность максимальной длины (англ. maximum-length sequence, MLS) — псевдослучайная двоичная последовательность, порожденная регистром сдвига с линейной обратной связью (РСЛОС) и имеющая максимальный период. М-последовательность является линейной рекуррентой над полем GF(2).

Далее, для простоты будем считать, что мы рассматриваем чисто периодическую последовательность с глубиной рекурсии и периодом . Саму последовательность будем обозначать $\gamma = \gamma_1, \gamma_2, ...$ .

Постулаты Голомба для двоичных последовательностей

Если вы заядлый читатель библитечки Кванта, то возможно вам знакомо имя Соломона Голомба как автора книги про полимино и изобретателя шашмат, однако известен он не только этим. В своей книге [1] он выдвинул три постулата, которым должны удовлетворять последовательности, получающиеся при помощи конечного автомата, чтобы считаться псевдослучайными. Это свойство очень важно например для поточных криптосистем, иначе злоумышленник сможет предсказывать гамму пользуясь статистическими особенностями генерируемой последовательности. Сформулируем сами постулаты:

R1: На отрезке $\gamma_1, . . . , \gamma_𝑟$ число нулей незначительно отличается от числа единиц.
R2: На отрезке периода примерно половина серий имеет длину 1, четверть — длину 2, восьмая часть — длину 3 и далее, пока количество серий фиксированной длины больше одного (серией называется максимальная подпоследовательность из одинаковых символов).
R3: Значения автокорреляционной функции
$𝐶_𝛾(𝜏) = \sum^r_{t=1} 𝜒(𝛾_𝑡 + 𝛾_{𝑡+𝜏} )$
близки к 0 для всех $\tau = 1, 2, . . . , 𝑟 − 1$ . Здесь $𝜒: F_2 → \{−1, 1\}, 𝑎 ↦(−1)^a$ .

Доказательство того, что M-последовательность удовлетворяет R1 и R3 доступно изложено, например, тут [2].

Докажем, что M-последовательность удовлетворяет R2

Чтобы обнаружить серию из единиц на самом деле следует искать фрагмент вида 011...110 длины соответственно. Анализировать будем состояния $S_i = (\gamma_i, ... , \gamma_{i+n})$ и считать количество состояний у которых первые элементов соответствуют нашему шаблону. Всего таких состояний в точности $2^{n-k-2}$ . Серий длины больше быть вообще не могло, т.к. состояние из единиц, в силу максимальности периода, встречается ровно один раз. Серии из или единиц не могли встретится более одного раза, иначе состояние 111...10 встретилось бы больше одного раза. Аналогичные рассуждения применим и для серий из нулей. То есть всего мы обнаружили

$2\sum_{k=1}^{n-2}2^{n-k-2} = 2(\frac{2^{n-3}(2^{-n+2}-1)}{2^{-1}-1})= 2(2^{n-2}-1)$

различных серий. Т.к. для M-последовательности пробегают все возможные векторы длины , кроме нулевого, и все они различны (в силу максимальности периода), то доля серий длины :

$\frac{2 \cdot 2^{n-k-2}}{2(2^{n-2}-1)} \approx \frac{1}{2^k}$

Последовательности Лежандра

Пусть какое-то нечётное простое число, символом Лежандра $\left( \frac{n}{p} \right)$ называется

$\left( \frac{n}{p} \right) = \begin{cases} 1 & \text{если найдётся } x \text{ такой, что } x^2 \equiv n \pmod{p}, \\ -1 & \text{в противном случае.} \end{cases}$

Нетрудно показать, что последовательность Лежандра вида $\left( \frac{0}{p} \right), \left( \frac{1}{p} \right), ...$ удовлетворяет R1 и R3, с той оговоркой [1], что раз последовательность уже не двоичная, то первый постулат требует равенства количеств -1 и 1, а функция автокорреляции примет вид:

$C_{\tau} = \sum_{n=0}^{p-1} \gamma_n \gamma_{n + \tau}$

причём она должна принимать ровно два значения

$C_{\tau} = \begin{cases} p & \text{if } \tau = 0, \\ -1 & \text{if } 1 \leq \tau \leq p-1. \end{cases}$

Хорошо известно, что для простого квадратичных вычетов по модулюстолько же сколько и невычетов.

Доказательство. Заметим, что $x^2 \equiv (x-p)^2 (\text{ mod } p)$ . Получили, что квадратичных вычетов не более чем $\frac{p-1}{2}$ . Докажем, что среди $1^2, 2^2, ..., \frac{p-1}{2}^2$ нет повторяющихся остатков по модулю . Предположим противное, пусть нашлись $x^2 \equiv y^2 \text{ mod } p$ , тогда или делится на , но значения обоих выражений меньше , получили противоречие. $\square$

Таким образом мы показали, что для последовательности Лежандра выполняется R1.

В [5] можно найти, что функция автокорреляции принимает следующие значения

$C_{\tau} = \begin{cases} p & \text{if } \tau = 0, \\ (-1 - \left(\frac{\tau}{p}\right) \left(1 + (-1)^{\frac{p-1}{2}}\right) ) & \text{if } 1 \leq \tau \leq p-1, \end{cases}$

что в свою очередь иллюстрирует выполнение R3 для . Кратко обоснуем откуда взялась эта формула. Случай $\tau = 0$ тривиален, т.к. каждое слагаемое будет равно 1, так что далее будем предполагать $\tau \neq 0$ .

Случай 1 (): Тогда сдвиг на любое $\tau$ вправо не меняет соотношения квадратичных вычетов и невычетов, по-прежнему остаётся вычетов и невычетов [6]. Тогда рассмотрим пары ( $\gamma_n, \gamma_{n+\tau}$ ), если пар (вычет, вычет) — штук, то пар (вычет, невычет) — соответственно, следовательно пар (невычет, невычет) — , а пар (невычет, вычет) — . Подставив данные в нашу исходную формулу получим, что $C_{\tau} = \frac{-1}{p}$ .

Случай 2 (): Также в [6] говорится, что если $\tau$ - квадратичный вычет, то вычетов после сдвига будет , невычетов —. Если $\tau$ невычет, то наоборот невычетов — , а вычетов — . Рассуждая аналогично предыдущему случаю получим, что $C_{\tau} = \frac{-3}{p}$ , если $\tau$ — вычет, и $C_{\tau} = \frac{1}{p}$ , если невычет.

Однако интересно, что в общем случае для последовательностей Лежандра не обязан выполняться постулат R2. Рассмотрим например последовательность при .

11-1111-1-1-11-111-1111...

Всего серий на отрезке периода 6, но серий длины 2 — $\frac{1}{6}$ , а серий длины 3 — $\frac{1}{3}$ , что не соответствует R2.

Разностные множества Адамара

Оказывается, можно описать класс последовательностей, которые удовлетворяют R1 и R3. Такие последовательности называются последовательностями Адамара и эквивалентны циклическим разностным множествам Адамара с параметрами $v = 4n -1, k = 2n -1, \lambda = n-1$ , где $n \geq 2$ , - целое.

Определение. Пусть — положительное целое число, и пусть обозначает множество вычетов по модулю . Пусть — -элементное подмножество . Назовём циклическим ( $v, k, \lambda$ )-разностным множеством, если для любого ненулевого $d \in U$ существует ровно $\lambda$ пар (), где $x, y \in D$ , таких что $d \equiv (x - y) \pmod{v}$ .

Известно [4], что такие последовательности могут быть трёх типов:

1) v = 4n - 1 и v — простое.

Последовательность Лежандра
Последовательность Холла, основанная на вычетах шестой степени (Hall's sextic residue construction): специальный тип двоичной последовательности , в которой , если является вычетом шестой степени по модулю , и в противном случае, для простых чисел , удовлетворяющих условию $p \equiv 1 \text{ mod } 6$ .
В модульной арифметике целое число a является вычетом шестой степени по модулю , если $x^{6}\equiv a \text{ (mod } p)$ имеет решение для , иначе — невычетом.
Согласно [7] , $A \in Z$ .

2) v = p(p+2) , где p — простое.

Последовательность Якоби. Такая последовательность является обобщением последовательности Лежандра. Подробное описание её построения можно найти в [8].

3) v = 2^t - 1 для некоторого целого числа t.

Последовательности, генерируемые линейными регистрами сдвига (также называемые M-последовательностями) для всех значений .
Последовательности Гордона–Миллса–Уэлча (GMW-последовательности) для некоторых составных значений .
Три разрозненных примера при , найденные Баумертом и Фредериксеном; два разрозненных примера при , найденные Ченгом; и два разрозненных примера при , найденные Драйером. Эти примеры не имеют иного объяснения. (Полный перебор был выполнен только для $t \leq 9$ , $v \leq 511$ ).