219

М7. Одноразовый блокнот дешифровать невозможно

В одноразовом блокноте все буквы встречаются с одинаковой частотой. Поэтому, сколько бы знаков гаммы нам ни было известно, мы не сможем предсказать, каким будет следующая буква. Поэтому все последовательности знаков гаммы равновероятны. Это означает, что сообщение, зашифрованное с помощью одноразового блокнота, может быть "расшифровано" в любой открытый текст подходящей длины, поскольку предполагаемая последовательность знаков гаммы не имеет никаких свойств, позволяющих отличить её от любой другой. Допустим, например, что шифрованный текст

QLXEBáYEMUCáAFNQQ

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

JLIPDáBCFDUáIMBQY,

то расшифрованный текст будет таким:

HAPPYXCHRISTMAS.

Если же гамма была следующей:

DRVTXáYNPIUáINFFM,

то получается такой открытый текст:

NUCLEARXMISSILE.

Поскольку все случайные отрезки гаммы длиной 15 знаков являются равновероятными, то каждый из этих вариантов является возможным ответом, и более того, существует более 1021 других возможных ответов, большая часть которых, правда, будет абсолютно бессмысленна.

Глава 8

М8. Частота появления случайных чисел на странице

220

Можно ожидать, что на странице, содержащей 100 двузначных случайных чисел, любое число из диапазона от 00 до 99 должно встретиться один раз. Вероятность того, что конкретное число не встретится на конкретном месте, равна 0,99. Поскольку все числа случайные, то вероятность того, что конкретное число вообще не встретится на странице из 100 чисел, равна

(0,99)100, то есть (1-1/100)100.

Это значение приблизительно равно e-1, где число e=2,71828... - это основание натуральных логарифмов (об этом уже упоминалось выше, см. М1). Поскольку e-1=0,37 с точностью до двух десятичных знаков, то, следовательно, на типовой странице из 100 двузначных случайных чисел около 37 значений не должны встретиться вовсе. С другой стороны, там должно быть около

100e 1 3!

(т.е. около 6) значений, которые встречаются трижды. Можно также ожидать, что найдется одно число, которое встретится четыре раза, так как в этом случае ожидаемое число равно

100e 1 , 4!

и это значение лежит между 1 и 2.

(Мы, в действительности, утверждаем здесь следующее: вероятность того, что конкретное двузначное число встретится на странице из 100 случайных чисел ровно n раз, приблизительно равна

e 1 . n!

Это - частный случай распределения вероятностей, известного в теории вероятностей как распределение Пуассона. Всесторонне математическое исследование данного вопроса, подтверждающее правильность сделанного здесь утверждения, можно найти в книгах по теории вероятностей, например в [8.1])

221

М9. Комбинирование двух последовательностей двоичных знаков гаммы, имеющих отклонения

Если данные числовые последовательности независимы, но имеют отклонение в пользу нуля с вероятностью (0,5+x), то в последовательности, полученной суммированием этих последовательностей по модулю 2, вероятность нуля будет равна

(0,5+x)2 + (0,5-x)2 = 0,5+2x2.

Так, например, если x=0.01, то отклонение суммы двух последовательностей будет всего лишь 0.0002. (Если обе последовательности каким-либо образом связаны, то данное рассуждение неверно. Например, в случае двух идентичных числовых последовательностей их сумма по модулю 2 состоит из одних нулей.)

М10. Последовательность типа Фибоначчи

Будем следовать обозначениям, введенным в М5. Элементы этой последовательности порождаются линейной рекуррентой

U(n+1) = 2Un + U(n-1).

Для доказательства делимости на 5 каждого третьего элемента последовательности заметим, что, согласно рекуррентной формуле,

Un = 2U(n-1) + U(n-2),

поэтому, подставляя выражение для Un в выражение для U(n+1), получаем:

U(n+1) = 5U(n-1) + 2U(n-2).

И если Un-2 делится на 5, то отсюда следует, что U(n+1) также должно делиться на 5. Так как элемент U0 (который равен 0) делится на 5, то на 5 делятся также элементы U3, U6 и т.д.

Теперь рассмотрим утверждение о том, что отношение соседних элементов последовательности стремится к значению (1+ 2). Как и раньше, будем предполагать, что общий член последовательности Un можно представить в виде:

Un A n B n .

222

Применив рекуррентную формулу и начальные условия Un = 0 и U1 = 1, получаем: для того, чтобы общий член последовательности был представим в указанном виде, необходимо, чтобы и являлись корнями квадратного уравнения

X2 - 2X - 1 = 0,

причем B = -A, откуда получаем значения

= (1+ 2), = (1- 2) и A =(1/2 2).

Отношение соседних элементов последовательности довольно быстро сходится к значению , так как по абсолютной величине меньше единицы и поэтому значения его степеней довольно быстро убывают. Поскольку= (1+ 2), то утверждение доказано.

М11. Двоичные линейные рекурренты

Как и можно было бы предположить после анализа чисел Фибоначчи и аналогичных им последовательностей, нам необходимо исследовать свойства многочлена степени k, сопоставленного линейной рекурренте степени k. Общий вид подобной рекурренты таков:

Un = a1U(n-1) + a2U(n-2) + ...+ akU(n-k),

а ассоциированный с ней многочлен выглядит так:

Xk + a1Xk-1 + ... +ak = 0.

Напомним, что все вычисления выполняются по модулю 2, так что -as - это то же самое, что +as. Поскольку рекуррента является двоичной и имеет степень k, то все ее коэффициенты (или множители) равны либо 0, либо 1, и, более того, последний коэффициент, ak, можно положить равным 1. Поэтому существует 2(k-1) различных наборов коэффициентов.

Математическое исследование периодов двоичных последовательностей, порождаемых линейными рекуррентами, слишком сложно, чтобы приводить его здесь. Однако можно сформулировать необходимый нам основной результат следующим образом.

Теорема

223

Пусть (n) обозначает количество натуральных чисел, меньших n и не имеющих с n общих делителей. Тогда число двоичных линейных рекуррент степени k, порождающих последовательности знаков гаммы максимального периода 2k-1, равно

2k 1 .

k

Функция (n) называется -функцией Эйлера (произносится "фи"). Ее очень просто вычислить. Пусть p1, p2, ..., pr - все различные простые числа, такие что n делится без остатка на некоторую степень каждого из них. Тогда

(n) n( p1 1)( p2 1)...( pr 1) . p1 p2 ... pr

Так, например, для k=12 получаем

212-1=4095=3 3 5 7 13,

и поэтому

(4095)= 4095 2 4 6 12 =1728.

3 5 7 13

Таким образом, число двоичных линейных рекуррент степени 12, порождающих двоичные последовательности максимального периода 4095, равно

172812 =144,

что и утверждается в главе 8. Заметим, что хотя 4095 делится на 32, соответствующая дробь, входящая в функцию Эйлера, равна двум третям, а не восьми девятым.

Аналогично, для k=23 число двоичных линейных рекуррент степени23, порождающих двоичные последовательности максимального периода (223-1), равно

223 1 ,

23

то есть