Сергей Дориченко - 25 этюдов о шифрах
Для тех кто изучал пределы, уточним: если обозначить через S0(k) число нулей, а через S1(k) — число единиц среди k первых членов нашей последовательности, то тогда предел отношения S0(k)/k равен p и предел отношения S1(k)/k равен q при k стремящемся к бесконечности.
Контрольный вопрос. Пусть мы случайным образом подбрасываем монету, причём p=q=½ и первые сто членов соответствующей последовательности равны 1 (100 раз подряд выпала решка). Чему равно вероятность того, что 101-ым членом этой последовательности снова будет 1?
Правильный ответ на этот вопрос: ½. Так как q=½, а случайность нашей последовательности как раз и означает, что каждый очередной её член равен 1 с вероятностью q независимо от того, какими были предыдущие её члены.
Обычно последовательности, с которыми на практике приходится иметь дело, вообще говоря, не строго случайные (неслучайные). Изучение случайных и неслучайных двоичных последовательностей имеет важное значение для криптографии. Например, выявление закономерностей в шифрованных сообщениях очень полезно при вскрытии шифра (см. этюд 2.7). В этюде 2.5 вы также узнаете, что для построения абсолютно стойкого шифра необходимо уметь получать совершенно случайный ключ.
Задачам различения случайной и неслучайной последовательностей, а также выявления закономерностей в неслучайных последовательностях посвящено много исследований в различных областях математики. Так, например, один из основных разделов математической статистики — это проверка статистических гипотез, в котором, в частности, разрабатываются методы различения гипотез о природе и характеристиках наблюдаемых последовательностей. Другой пример — это активно изучаемый в современной теоретической криптографии гипотетический объект — псевдослучайный генератор. При изучении этого объекта используются многочисленные результаты теории сложности алгоритмов и вычислений. Говоря неформально, псевдослучайный генератор вырабатывает такие последовательности, которые трудно отличить от случайных и из которых трудно извлечь закономерности. Строгие определения необходимых понятий выходят за рамки нашей книги.
Близким по духу, но более простым и хорошо известным, особенно для программистов, является такой объект, как датчик случайных чисел. Это — некоторое устройство или программа, которая вырабатывает псевдослучайные последовательности. Псевдослучайные последовательности в некоторых ситуациях считают неотличимыми от случайных, причем для разных ситуаций и задач подбирают подходящие датчики. Чем более сильные требования накладываются на случайность вырабатываемых последовательностей, тем более сложным является соответствующий датчик случайных чисел. Многие шифрмашины можно считать датчиками случайных чисел, удовлетворяющими очень высоким требованиям на качество вырабатываемых последовательностей.
Опишем, например, один простейший датчик, предложенный в 1949 году Д.Х. Лемером и в дальнейшем получивший название линейного конгруэнтного метода. Для заданного начального числа a0 он вырабатывает бесконечную последовательность натуральных чисел {ak} по следующему рекуррентному закону:
ak=d+ak−1 ∙ ℓ(modN).
Здесь параметры датчика d, ℓ, N — некоторые целые числа. Запись a=b(modN), вообще говоря, означает, что a−b делится на число N; в данном случае в качестве ak берется остаток от деления d+ak−1 ∙ ℓ на N.
Поскольку все члены последовательности {ak} — неотрицательные целые числа, не превосходящие N−1, то среди них найдутся два одинаковых, скажем ai и ai+t. Тогда, как легко видеть, ai=ai+t для k≥i, т.е. последовательность — периодическая с длиной периода t. Конечно, периодичность не вполне согласуется с нашими представлениями о случайности, но, оказывается, можно подбирать такие параметры датчика, чтобы период был достаточно большим и у последовательности были многие признаки случайности.
Следует отметить, что «хорошей во всех отношениях случайной последовательности» практически не существует: насколько «хорошей» является случайная последовательность, зависит от ее назначения.
Подумайте сами:
1. Докажите следующее утверждение: вероятность того, что при k подбрасываниях кривой монеты ℓ раз выпадет орёл, равняется:
2. Придумайте такие числа d, ℓ и N, чтобы N было не слишком маленьким и длина периода последовательности, полученной линейным конгруэнтным методом, была близка к N.
3. Придумайте какой-нибудь свой датчик случайных чисел.
2.3. Что такое алгоритм и его сложность
Под алгоритмом, если говорить неформально, можно понимать четко описанную последовательность действий, приводящую к определенному результату.
Понятие алгоритма очень долго оставалось интуитивным понятием. Только в 30-е годы XX века в работах выдающихся математиков Д. Гильберта, А. Черча, С. Клини, Э. Поста и А. Тьюринга были предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Тем самым формировалась теория алгоритмов — новое направление в математике, которое стало впоследствии теоретической основой развития вычислительной техники. В настоящее время теория алгоритмов бурно развивается, многие ее понятия проясняются и уточняются (доказуемость, разрешимость, эффективность и др.).
С нематематическими алгоритмами мы постоянно встречаемся в жизни (таковыми можно считать, например, рецепт приготовления борща или инструкцию о проведении экзамена в школе). Простейшим примером математического алгоритма может служить хорошо известный алгоритм Евклида, при помощи которого можно найти наибольший общий делитель двух чисел. А такой вид деятельности, как программирование — это постоянная работа с алгоритмами.
Очень важным понятием в математике (интуитивно ясным, но не очень просто формализуемым) является сложность алгоритма. Приведем простой пример. Пусть требуется угадать задуманное число, про которое известно, что оно натуральное и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить «да» или «нет». Одним из способов (алгоритмов) угадывания может быть такой: последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное число не будет найдено. В худшем случае для этого потребуется 999 вопросов. Однако можно предложить и другой алгоритм, позволяющий угадать число за 10 вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да, то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов уменьшается в два раза. Здесь сложностью алгоритма можно считать число вопросов. Тогда первый алгоритм в 100 раз «сложнее» второго.
Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать число совершаемых операций. При этом, если в алгоритме встречаются только умножение и сложение, под сложностью часто понимается только число умножений, поскольку эта операция требует существенно большего времени. На практике необходимо также учитывать стоимость операций, выполняемых алгоритмом, и т.п.
В математической теории сложности вычислений рассматриваются алгоритмы решения не конкретных задач, а так называемых массовых задач. Массовую задачу удобно представлять себе в виде бесконечной серии индивидуальных задач. Индивидуальная задача характеризуется некоторым размером, т.е. объемом входных данных, требуемых для описания этой задачи. Если размер индивидуальной задачи — некоторое натуральное число n, тогда сложность алгоритма решения массовой задачи становится функцией от n. Приведем два примера.
Рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Ясно, что таких ключей — 2n, и поэтому в данном алгоритме 2n шагов, т.е. его сложность равна 2n. Это — простейший пример экспоненциального алгоритма (его сложность выражается через n экспонентой). Большинство экспоненциальных алгоритмов — это просто варианты полного перебора.
