25 этюдов о шифрах - страница 8

С другой стороны, слова в любом алфавите можно легко перевести в двоичные слова. Пусть мы имеем дело с текстами на русском языке и пусть буквы «е» и «ё», а также «и» и «й» не различаются, а пробел между словами считается отдельной буквой (обозначение: _). Тогда наш алфавит состоит из тридцати двух символов. Рассмотрим теперь телеграфный код — старое техническое применение двоичной системы счисления. Он состоит тоже из 32 символов — двоичных слов длины 5. (Подробно о двоичной и других системах счисления можно прочитать в брошюре С.В. Фомина «Системы счисления» из серии «Популярные лекции по математике».) Сопоставим каждой букве двоичное слово длины 5 следующим образом:

_ → 00000, A → 00001, Б → 00010, B → 00011, Г → 00100, Д → 00101, ... , Ю → 11110, Я → 11111.

Заменив в тексте каждую букву на соответствующее двоичное слово, получим двоичный вид нашей информации — некоторую последовательность нулей и единиц (или, как принято говорить, битов). Подобным образом можно поступить и с любым другим алфавитом.

На практике создаются специальные устройства, которые позволяют автоматически переводить вводимую человеком текстовую информацию в двоичную.

Более того, в настоящее время практически любая информация — речь, телевизионные сигналы, музыка и др. — может храниться и пересылаться в двоичном виде. Для работы с такой информацией используют специальные устройства: например, АЦП и ЦАП (аналого-цифровой и цифро-аналоговый преобразователи), устройства для цифровой записи и воспроизведения музыки.

Таким образом, двоичные слова и двоичные последовательности — типовые объекты в криптографических исследованиях.

Подумайте сами:

1. Докажите, что каждое натуральное число n единственным образом представляется в виде n=2^>k+a_>k−12^>k−1+...+a_>12+a_>0, где k — некоторе целое неотрицательное число, а каждое из чисел a_>k−1, ..., a_>0 — либо 0, либо 1.

Понятие последовательности известно еще со школьных лет. Однако последовательности, которые там изучались, были детерминированными — они однозначно восстанавливались по их нескольким элементам. Так, арифметическая и геометрическая прогрессии восстанавливаются по любым двум своим подряд идущим членам. Значения многочлена в целых точках также образуют детерминированную последовательность: она определяется любыми n+1 своими членами, где n — степень данного многочлена (докажите это!).

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

Пусть мы подбрасываем «правильную» монету. В зависимости от того, как она падает, полагаем очередной член последовательности равным 0 (орел) или 1 (решка). Как показывает опыт, обычно нельзя угадать, как монета упадет в очередной раз. Однако, если подбрасывать монету достаточно долго, примерно в половине случаев выпадет орел, а в половине — решка. Говорят, что монета падает случайным образом, причем в каждом подбрасывании с одинаковой вероятностью ½ выпадает орел (0) или решка (1).

Однако бывают ситуации («кривая монета»), когда орел и решка выпадают с разной вероятностью — p и q соответственно (p≠q). Отметим, что p+q=1! В случайной двоичной последовательности, полученной на основе подбрасывания «кривой монеты», p можно считать частотой появления нуля, а q — частотой появления единицы.

Для тех кто изучал пределы, уточним: если обозначить через S_>0(k) число нулей, а через S_>1(k) — число единиц среди k первых членов нашей последовательности, то тогда предел отношения S_>0(k)/k равен p и предел отношения S_>1(k)/k равен q при k стремящемся к бесконечности.

Контрольный вопрос. Пусть мы случайным образом подбрасываем монету, причём p=q=½ и первые сто членов соответствующей последовательности равны 1 (100 раз подряд выпала решка). Чему равно вероятность того, что 101-ым членом этой последовательности снова будет 1?

Правильный ответ на этот вопрос