25 этюдов о шифрах - [8]
Следует отметить, что «хорошей во всех отношениях случайной последовательности» практически не существует: насколько «хорошей» является случайная последовательность, зависит от ее назначения.
Подумайте сами:
1. Докажите следующее утверждение: вероятность того, что при k подбрасываниях кривой монеты ℓ раз выпадет орёл, равняется:
2. Придумайте такие числа d, ℓ и N, чтобы N было не слишком маленьким и длина периода последовательности, полученной линейным конгруэнтным методом, была близка к N.
3. Придумайте какой-нибудь свой датчик случайных чисел.
2.3. Что такое алгоритм и его сложность
Под алгоритмом, если говорить неформально, можно понимать четко описанную последовательность действий, приводящую к определенному результату.
Понятие алгоритма очень долго оставалось интуитивным понятием. Только в 30-е годы XX века в работах выдающихся математиков Д. Гильберта, А. Черча, С. Клини, Э. Поста и А. Тьюринга были предложены формальные определения алгоритма на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Тем самым формировалась теория алгоритмов — новое направление в математике, которое стало впоследствии теоретической основой развития вычислительной техники. В настоящее время теория алгоритмов бурно развивается, многие ее понятия проясняются и уточняются (доказуемость, разрешимость, эффективность и др.).
С нематематическими алгоритмами мы постоянно встречаемся в жизни (таковыми можно считать, например, рецепт приготовления борща или инструкцию о проведении экзамена в школе). Простейшим примером математического алгоритма может служить хорошо известный алгоритм Евклида, при помощи которого можно найти наибольший общий делитель двух чисел. А такой вид деятельности, как программирование — это постоянная работа с алгоритмами.
Очень важным понятием в математике (интуитивно ясным, но не очень просто формализуемым) является сложность алгоритма. Приведем простой пример. Пусть требуется угадать задуманное число, про которое известно, что оно натуральное и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить «да» или «нет». Одним из способов (алгоритмов) угадывания может быть такой: последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное число не будет найдено. В худшем случае для этого потребуется 999 вопросов. Однако можно предложить и другой алгоритм, позволяющий угадать число за 10 вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да, то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов уменьшается в два раза. Здесь сложностью алгоритма можно считать число вопросов. Тогда первый алгоритм в 100 раз «сложнее» второго.
Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать число совершаемых операций. При этом, если в алгоритме встречаются только умножение и сложение, под сложностью часто понимается только число умножений, поскольку эта операция требует существенно большего времени. На практике необходимо также учитывать стоимость операций, выполняемых алгоритмом, и т.п.
В математической теории сложности вычислений рассматриваются алгоритмы решения не конкретных задач, а так называемых массовых задач. Массовую задачу удобно представлять себе в виде бесконечной серии индивидуальных задач. Индивидуальная задача характеризуется некоторым размером, т.е. объемом входных данных, требуемых для описания этой задачи. Если размер индивидуальной задачи — некоторое натуральное число n, тогда сложность алгоритма решения массовой задачи становится функцией от n. Приведем два примера.
Рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Ясно, что таких ключей — 2>n, и поэтому в данном алгоритме 2>n шагов, т.е. его сложность равна 2>n. Это — простейший пример экспоненциального алгоритма (его сложность выражается через n экспонентой). Большинство экспоненциальных алгоритмов — это просто варианты полного перебора.
Рассмотрим теперь алгоритм умножения столбиком двух n-значных чисел. Он состоит из n>2 умножений однозначных чисел, т.е. его сложность, измеренная количеством таких умножений, равна n>2. Это — простейший пример полиномиального алгоритма (его сложность выражается через n полиномом).
Достаточно очевидно, что для решения одной и той же математической задачи могут быть предложены различные алгоритмы. Поэтому под сложностью задачи понимают минимальную сложность алгоритмов ее решения. Возвращаясь теперь к этюду 1.6, можно сказать в новых терминах, что стойкость шифра — это сложность задачи его вскрытия.
В математике есть много задач, для решения которых пока не удалось построить полиномиальный алгоритм. К ним относится, например, задача коммивояжера: есть
