L-нотация

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

${\displaystyle L_{n}[\alpha ,c]}$ определяется формулой

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

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

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

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

${\displaystyle L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}}$

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

${\displaystyle L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}}$

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

Примеры

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

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

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

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

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

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

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

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

${\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}}$

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

История

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

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

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

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

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

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