4.3. Сложность теоретико-числовых алгоритмов

Next: 4.4. Как отличить составное Up: 4. Алгоритмические проблемы теории Previous: 4.2. Система шифрования RSA Contents: Содержание

4.3. Сложность теоретико-числовых алгоритмов

Сложность алгоритмов теории чисел обычно принято измерять количеством арифметических операций (сложений, вычитаний, умножений и делений с остатком), необходимых для выполнения всех действий, предписанных алгоритмом. Впрочем, это определение не учитывает величины чисел, участвующих в вычислениях. Ясно, что перемножить два стозначных числа значительно сложнее, чем два однозначных, хотя при этом и в том, и в другом случае выполняется лишь одна арифметическая операция. Поэтому иногда учитывают еще и величину чисел, сводя дело к так называемым битовым операциям, т.е. оценивая количество необходимых операций с цифрами 0 и 1, в двоичной записи чисел. Это зависит от рассматриваемой задачи, от целей автора и т.д.

На первый взгляд странным также кажется, что операции умножения и деления приравниваются по сложности к операциям сложения и вычитания. Житейский опыт подсказывает, что умножать числа значительно сложнее, чем складывать их. В действительности же, вычисления можно организовать так, что на умножение или деление больших чисел понадобится не намного больше битовых операций, чем на сложение. В книге [7] описывается алгоритм Шенхаге - Штрассена, основанный на так называемом быстром преобразовании Фурье, и требующий $O(n \ln n \ln\!\ln n)$ битовых операций для умножения двух -разрядных двоичных чисел. Таким же количеством битовых операций можно обойтись при выполнении деления с остатком двух двоичных чисел, записываемых не более, чем цифрами. Для сравнения отметим, что сложение -разрядных двоичных чисел требует битовых операций.

Говоря в этой главе о сложности алгоритмов, мы будем иметь в виду количество арифметических операций. При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает интуитивных понятий той области математики, которой принадлежит алгоритм. Формализация же этих понятий требуется лишь тогда, когда речь идет об отсутствии алгоритма или доказательстве нижних оценок сложности. Более детальное и формальное обсуждение этих вопросов см. в главе 2.

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

Следующий алгоритм вычисляет $a^d \mod{m}$ за $O(\ln m)$ арифметических операций. При этом, конечно, предполагается, что натуральные числа и не превосходят по величине .