Лемма 3.1

Пример 3.1

Определение 3.1

Последовательность называется периодической с периодом , если — наименьшее натуральное число, для которого

при всех .

Отрезок длины есть подпоследовательность из , состоящая из идентичных символов, ограниченная иными символами. Если отрезок начинается в момент , то справедливы условия

Мы различаем следующие отрезки:

блок длины ,

лакуна длины .

Автокорреляцияпериодической последовательности с периодом определяется формулой:

(3.1)

где (соответственно, ) обозначает число совпадений (соответственно, несовпадений) на полном периоде между и ; вторая последовательность есть последовательность , сдвинутая влево на позиций. Таким образом,

Заметим, что можно также написать .

Рассмотрим периодическую последовательность с периодом , заданную ее первыми элементами.

С помощью функций Count, Length, Mod, RotateLeft и Table пакета "Mathematica" легко вычисляются все значения автокорреляционной функции , .

segment = {1, 1, 0, 1, 0, 0, 0, 0};

p = Length[segment];

Table[2*Count[Mod[

segment - RotateLeft[segment,k],2],0] - p) / p, {k, 0, p – 1}]

|| {1, 0, 0, 0, -1/2, 0, 0, 0}

Если кратно , получаем , , так что . В этом случае говорят о внутрифазовой автокорреляции. Если не делит , то говорят о внефазовой автокорреляции. В этом случае значение лежит между и .

Определение 3.2 (Golombs Randomness Postulates)

G1: Количество нулей и единиц в одном периоде приблизительно совпадает, т.е. вероятности их появления , если четно, и , если нечетно.

G2: Половина отрезков в цикле имеют длину 1, четверть отрезков имеют длину 2, восьмая часть отрезков имеют длину 3 и т.д.; кроме того, половина отрезков данной длины — лакуны, другая половина — блоки.

G3: Внефазовая автокорреляция имеет одно и то же значение для всех .

G1 утверждает, что нули и единицы встречаются приблизительно с одной и той же вероятностью. Их появления легко подсчитать с помощью функции Count пакета "Mathematica".

segment = {1, 1, 0, 1, 0, 0, 0, 0};

Count[segment,0]

Count[segment,1]

|| 5

|| 3

G2 утверждает, что после комбинации 011 символ 0 (приводящий к блоку длины 2) имеет ту же вероятность, что и символ 1 (приводящий к блоку длины ), и т.п. Таким образом, G2 говорит, что конкретные -граммы встречаются с правильными частотами. Эти частоты можно вычислить с помощью функций Count,Length,RotateLeft, Table и Take пакета "Mathematica":

segment={0,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1};

p = Length[segment];

ngram = {1, 0, 1}; k = Length[ngram];

Count[Table[Take [

RotateLeft[segment, i], k] == ngram, {i, p}], True]

|| 3

Интерпретация постулата G3 более трудна. Это условие говорит, что число совпадений в данной последовательности и в ее сдвинутой версии не дает никакой информации о периоде последовательности, если сдвиг не кратен периоду. Похожая ситуация описывается в лемме 3.1, где такое сравнение позволяет определить длину ключа, использованного в шифре Виженера. В криптографических приложениях слишком велико для такого подхода.

Пусть — двоичная последовательность с периодом , удовлетворяющая постулатам случайности Голомба. Тогда нечетно и принимает значение , когда не делится на .

Доказательство. Рассмотрим циклическую -матрицу с верхней строкой . Подсчитаем двумя способами число всех совпадений за вычетом числа несовпадений между верхней строкой и всеми прочими строками. В силу постулата G3 построчный подсчет дает вклад для каждой строки с номером . В целом получается значение . Теперь мы подсчитаем ту же сумму по столбцам, рассматривая число совпадений за вычетом числа несовпадений между всеми нижними клетками и верхней.

Случай четного

В силу G1 вклад каждого столбца равен , так как каждый столбец содержит в точности совпадений нижних клеток с верхней и в точности несовпадений. Сумма этих значений по всем столбцам равна . Приравнивая два значения суммы, получаем . Однако из равенства (3.1) следует, что число целое. Это невозможно, когда , так как .

Случай нечетного

Для столбцов получаем вклад , равный 0, а для столбцов — вклад , равный . Следовательно, значение суммы есть . Приравнивание этой суммы к дает .

Хорошо известный критерий и спектральный критерий дают способы проверки свойств псевдослучайности данной последовательности.

Имеются также свойства криптографической природы, которым должна удовлетворять последовательность на рис. 3.1.

С1: период последовательности должен быть очень большим (величиной порядка 10⁵⁰);

С2: последовательность должна легко генерироваться;

С3: знание части открытого текста и соответствующего шифртекста (атака с известным открытым текстом) не должно позволить криптоаналитику сгенерировать всю последовательность .