L-нотация

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

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

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

,

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

Примечания

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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, 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. CRC Press, 1996. ISBN 0-8493-8523-7.