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] субэкспоненциальна (или сверх-полиномиальна).

Примеры[править | править исходный текст]

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

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

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

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

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

Это не является стандартным определением. 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.