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}$-нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.

Примечания

1. Hendirk W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods Архивная копия от 25 февраля 2012 на Wayback Machine, preprint, 2011.
2. Carl Pomerance, Analysis and comparison of some integer factoring algorithms Архивная копия от 4 февраля 2021 на Wayback Machine, In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
3. Arjen K. Lenstra and Hendrik W. Lenstra, Jr, «Algorithms in Number Theory», in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1990.
4. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography Архивная копия от 7 марта 2005 на Wayback Machine. CRC Press, 1996. ISBN 0-8493-8523-7.