L-нотация

L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как [math]\displaystyle{ L_n[\alpha,c] }[/math] для [math]\displaystyle{ n }[/math] стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом [math]\displaystyle{ n }[/math] представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиске в нём кратчайшего пути, или натуральное число в алгоритмах разложении его на простые сомножители.

[math]\displaystyle{ L_n[\alpha,c] }[/math] определяется формулой

[math]\displaystyle{ L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}} }[/math],

где [math]\displaystyle{ c }[/math] — положительная константа, а [math]\displaystyle{ \alpha }[/math] — константа [math]\displaystyle{ 0 \leq \alpha \leq 1 }[/math].

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

Сомножитель [math]\displaystyle{ e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}} }[/math] в [math]\displaystyle{ L_n[\alpha,c] }[/math] отражает доминирующую составляющую, а сомножитель [math]\displaystyle{ e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}} }[/math] относится ко всему менее значительному. При этом, когда [math]\displaystyle{ \alpha }[/math] равна 0,

[math]\displaystyle{ L_n[0, c] = e^{(c + o(1)) \ln\ln n} = (\ln n)^{c + o(1)} }[/math]

является многочленом от ln n, в то время как при [math]\displaystyle{ \alpha }[/math] равном 1,

[math]\displaystyle{ L_n[1, c] = e^{(c + o(1)) \ln n} = n^{c + o(1)} }[/math]

является экспонентой от ln n (и, поэтому, полиномом от n). Если же [math]\displaystyle{ \alpha }[/math] находится где-то между 0 и 1, то функция [math]\displaystyle{ L_n[\alpha,c] }[/math] субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная).

Примеры

Многие алгоритмы разложения чисел на простые сомножители имеют субэкспоненциальную временну́ю сложность. Лучшим методом с точки зрения экономии вычислительных ресурсов является общий метод решета числового поля, который имеет оценку:

[math]\displaystyle{ L_n[1/3, c] = e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}} }[/math]

для [math]\displaystyle{ c = (64/9)^{(1/3)} }[/math].

Лучшим алгоритмом, до разработки решета числового поля, был метод квадратичного решета, который имеет оценку сложности:

[math]\displaystyle{ L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}} }[/math]

Для задачи дискретного логарифмирования эллиптической кривой, самым быстрым общеприменимым алгоритмом является алгоритм больших и малых шагов - алгоритм Шенкса, имеющий асимптоматическую оценку времени работы равную квадратному корню от порядка группы n. В L-нотации это записывается:

[math]\displaystyle{ L_n[1, 1/2] = n^{1/2+o(1)} }[/math]

Существование теста простоты AKS, который работает в полиномиальное время, означает, что сложность теста простоты должна быть не более

[math]\displaystyle{ L_n[0, c] = (\ln n)^{c+o(1)} }[/math]

и доказано, что c не должно превышать 6.

История

[math]\displaystyle{ L }[/math]-нотация была определена в литературе в различном виде. Первым применил [math]\displaystyle{ L }[/math]-нотацию Карл Померанс в его работе «Анализ и сравнение некоторых алгоритмов факторизации целых чисел».

Эта форма имела только один параметр [math]\displaystyle{ c }[/math], [math]\displaystyle{ \alpha }[/math] в формуле был константой [math]\displaystyle{ 1/2 }[/math]. Померанс использовал букву [math]\displaystyle{ L }[/math] (или маленькую [math]\displaystyle{ l }[/math]) в этой и предыдущей статье для формул, содержащих много логарифмов.

Вышеприведенная формула, содержащая два параметра, была введена Арьеном Ленстрой и Хендриком Ленстрой в их статье «Алгоритмы в теории чисел», где нотация была использована при анализе дискретного логарифмирования алгоритма Копперсмита. В настоящее время нотация является наиболее употребимой в литературе.

Руководство по прикладной криптографии определяет L-нотацию как:

[math]\displaystyle{ L_n[\alpha,c]=O(e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}). }[/math]

Это не является стандартным определением. [math]\displaystyle{ O }[/math] предполагает, что время работы агента, выполняющего алгоритм, ограничено сверху. Однако, для разложения целого числа и дискретного логарифмирования [math]\displaystyle{ L }[/math]-нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.