L-нотация

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

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

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) в этой и предыдущей статье для формул, содержащих много логарифмов.

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

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

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

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

Примечания[править | править вики-текст]

  1. Hendirk W. Lenstra Jr. and Carl Pomerance, Primality testing with Gaussian periods, 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.