Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
4.6 Неполиномиальные оценки
Существует громадное множество функций, растущих быстрее полиномов.
Определение 4.12 (Неполиномиально ограниченная функция). Функция f(n) : N I—> ]R называется не ограниченной никаким полиномом степени п, если для любого полинома р(п) существует натуральное число по, такое что для всех п > по выполняется условие f(n) > р(п).
Функция /(п) называется полиномиально ограниченной (polynomially bounded), если она не является неполиномиально ограниченной.
164
Часть II. Математические основы
Пример 4.3. Покажем, что для любого числа а>1,0<е<1 функции /i (n) = G"e(loe")1-E, /2 (П) = G(ioebgiogn)-
не ограничены никаким полиномом степени п.
Пусть р(п) — произвольный полином. Обозначим через d степень этого поли-1 нома, а через с — его наибольший коэффициент. Следовательно, р(п) < cnd. Во-первых, пусть no = max ^с, EJ^, тогда /i(n) > р(п) для всех п > по-
Во-вторых, пусть no = max (с, Jexp (exp (exp (d + 1)F))J)' тогла /2 fa) > pip) для всех п > по- ?
В отличие от задач с полиномиальным временем решения (детерминированным или рандомизированным), задачи с неполиномиальным временем решения считаются трудноразрешимыми или не имеющими решения. Это связано с ограниченностью ресурсов, необходимых для решения таких задач, поскольку при увеличении размера исходных данных затраты растут настолько быстро, что задача становится практически неразрешимой. Например, пусть TV — составное целое число, имеющее размер п (т.е. n = log TV). Тогда функция /i(log N) в примере 4.3,
где а » ехр(1,9229994----Ь о(1)), о(1) « е = \, характеризует временную
сложность факторизации числа N с помощью решета числового поля (Number Field Sieve-NFS) [70]:
exp((l,9229994--- + o(l))(logA0i(loglogA0§) - (4-6.1)
Выражение (4.6.1) является субэкспоненциальным (sub-exponential) по ./V. Если заменить число | числом 1, выражение станет экспоненциальным. Субэкспоненциальная функция растет намного медленнее, чем экспоненциальная, но намного быстрее, чем полиномиальная. Если число N состоит из 1024 бит, выражение (4.6.1) превышает 2s6. Это чрезвычайно большое число операций, которое невозможно выполнить даже с помощью крупной сети параллельных компьютеров. Формула субэкспоненциальной временной сложности справедлива также для алгоритма дискретного логарифмирования в конечном поле (см. определение 8.2 в разделе 8.4).
Следует, однако, отметить асимптотический характер сравнения функций, примененный в определении 4.12 (функция /(п) в определении 4.12 также асимптотически больше любого полинома, т.е. превышает любой полином при достаточно большом числе п). Даже если функция /(п) не ограничена ни одним полиномом степени п, зачастую при достаточно большом числе по функция /(п) оказывается меньше, чем некоторый полином р(п) при n ^ п$. Например, функция j2{p) в примере 4.3 при е = 0,5 остается меньше, чем квадратичная функция
Глава 4. Вычислительная сложность
165
п2 при всех п ^ 2742762245454927736743541, хотя функция асимптотически
больше, чем nd при любых d > 1. По этой причине на практике некоторые алгоритмы с неполиномиальной временной сложностью остаются эффективными при решении задач для небольших размеров входных данных. Примером такого алгоритма является Л-метод Полларда (раздел 3.6.1), позволяющий вычислять небольшие значения дискретного логарифма.
Используя О-символику (см. определение 4.2 в разделе 4.3.2.4), мы преднамеренно игнорируем любые постоянные коэффициенты в выражении для оценки сложности. Однако следует иметь в виду, что в выражениях для неполиномиальной сложности постоянные коэффициенты, стоящие в степени числа, приобретают большую важность (например, число 1,9229994--- + о(1) в выражении (4.6.1)). Например, если усечь число 1,9229994 в выражении (4.6.1) до единицы, получится новый алгоритм разложения целого числа на простые множители. Его сложность для целого числа, состоящего из 1024 бит, уменьшается с 286 до 245. Такое количество операций уже вполне доступно для современных технологий. Для метода решета числового поля основные усилия исследователей направлены на ускорение метода путем уменьшения степени (правда, такое сокращение может привести к росту затрат памяти).
Выше мы сформулировали определение неполиномиальной оценки для больших чисел. Теперь мы можем сформулировать это понятие для малых величин.
Определение 4.13 (Пренебрежимо малые величины). Функция е(п) : N w К имеет пренебрежимо малые значения по сравнению с числом п, если функция является неполиномиально ограниченной.
Например, для любого полинома р величина является пренебрежимо малой. По этой причине иногда говорят, что подмножество, состоящее из р(п) точек множества {1,2,3,..., 2П}, является пренебрежимо малым по сравнению с размером всего множества, или что подмножество, состоящее из р(п) точек множества {1,2,3,..., 2п}, является разреженным.
Если е — пренебрежимо малая величина, то число 1-е называется огромным (overwhelming quantity). (Как правило, этот эпитет относится к вероятности. — Прим. ред.) Следовательно, не разреженному (non-sparse) (т.е. плотному (dense)) подмножеству множества {1,2,3,..., 2п} принадлежит огромное количество точек этого множества.
