L-нотация

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

определяется формулой

,

где  — положительная константа, а  — константа .

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

Сомножитель в отражает доминирующую составляющую, а сомножитель относится ко всему менее значительному. При этом, когда равна 0,

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

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

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

для .

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

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

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

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

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

Эта форма имела только один параметр , в формуле был константой . Померанс использовал букву (или маленькую ) в этой и предыдущей статье для формул, содержащих много логарифмов.

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

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

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

Примечания

[править | править код]
  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.