Русская Википедия:L-нотация
L-нотация — это асимптотическая нотация, аналогичная О-нотации, записывается как <math>L_n[\alpha,c]</math> для <math>n</math> стремящимся к бесконечности. Подобно O-большому, L-нотация обычно используется для приближённой оценки вычислительной сложности конкретного алгоритма. При этом <math>n</math> представляет собой некоторый параметр входных данных алгоритма, пропорциональный их размеру: например, число вершин и рёбер во входном графе в алгоритмах поиска в нём кратчайшего пути, или натуральное число в алгоритмах разложения его на простые сомножители.
<math>L_n[\alpha,c]</math> определяется формулой
- <math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>,
где <math>c</math> — положительная константа, а <math>\alpha</math> — константа <math>0 \leq \alpha \leq 1</math>.
L-нотация используется в основном в вычислительной теории чисел для выражения сложности алгоритмов для трудных проблем теории чисел, например, алгоритмов решета разложения натуральных чисел на простые сомножители и методов вычисления дискретных логарифмов. Преимущество такой нотации заключается в упрощении анализа алгоритмов.
Сомножитель <math>e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> в <math>L_n[\alpha,c]</math> отражает доминирующую составляющую, а сомножитель <math>e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> относится ко всему менее значительному. При этом, когда <math>\alpha</math> равна 0,
- <math>L_n[0, c] = e^{(c + o(1)) \ln\ln n} = (\ln n)^{c + o(1)}</math>
является многочленом от ln n, в то время как при <math>\alpha</math> равном 1,
- <math>L_n[1, c] = e^{(c + o(1)) \ln n} = n^{c + o(1)}</math>
является экспонентой от ln n (и, поэтому, полиномом от n). Если же <math>\alpha</math> находится где-то между 0 и 1, то функция <math>L_n[\alpha,c]</math> субэкспоненциальная, т. е. растёт медленнее, чем экспоненциальная функция с основанием больше 1 (или сверх-полиномиальная).
Примеры
Многие алгоритмы разложения чисел на простые сомножители имеют субэкспоненциальную временну́ю сложность. Лучшим методом с точки зрения экономии вычислительных ресурсов является общий метод решета числового поля, который имеет оценку:
- <math>L_n[1/3, c] = e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}</math>
для <math> c = (64/9)^{(1/3)}</math>.
Лучшим алгоритмом, до разработки решета числового поля, был метод квадратичного решета, который имеет оценку сложности:
- <math>L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}</math>
Для задачи дискретного логарифмирования эллиптической кривой, самым быстрым общеприменимым алгоритмом является алгоритм больших и малых шагов - алгоритм Шенкса, имеющий асимптоматическую оценку времени работы равную квадратному корню от порядка группы n. В L-нотации это записывается:
- <math>L_n[1, 1/2] = n^{1/2+o(1)}</math>
Существование теста простоты AKS, который работает в полиномиальное время, означает, что сложность теста простоты должна быть не более
- <math>L_n[0, c] = (\ln n)^{c+o(1)}</math>
и доказано, что c не должно превышать 6.[1]
История
<math>L</math>-нотация была определена в литературе в различном виде. Первым применил <math>L</math>-нотацию Карл Померанс в его работе «Анализ и сравнение некоторых алгоритмов факторизации целых чисел»[2].
Эта форма имела только один параметр <math>c</math>, <math>\alpha</math> в формуле был константой <math>1/2</math>. Померанс использовал букву <math>L</math> (или маленькую <math>l</math>) в этой и предыдущей статье для формул, содержащих много логарифмов.
Вышеприведенная формула, содержащая два параметра, была введена Арьеном Ленстрой и Хендриком Ленстрой в их статье «Алгоритмы в теории чисел»[3], где нотация была использована при анализе дискретного логарифмирования алгоритма Копперсмита. В настоящее время нотация является наиболее употребимой в литературе.
Руководство по прикладной криптографии определяет L-нотацию как[4]:
- <math>L_n[\alpha,c]=O(e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}).</math>
Это не является стандартным определением. <math>O</math> предполагает, что время работы агента, выполняющего алгоритм, ограничено сверху. Однако, для разложения целого числа и дискретного логарифмирования <math>L</math>-нотация, используемая для оценки, не является верхней границей, так что такое определение не совсем корректно.
Примечания
- ↑ Hendirk W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods Шаблон:Wayback, preprint, 2011.
- ↑ Carl Pomerance, Analysis and comparison of some integer factoring algorithms Шаблон:Wayback, 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 Шаблон:Wayback. CRC Press, 1996. ISBN 0-8493-8523-7.
