L-обозначение - L-notation

L-обозначение является асимптотический обозначение, аналогичное нотация big-O, обозначенный как ${\displaystyle L_{n}[\alpha ,c]}$ для связанная переменная ${\displaystyle n}$ стремящийся к бесконечности. Как и обозначение большого O, оно обычно используется для грубой передачи вычислительная сложность конкретного алгоритм.

Определение

Он определяется как

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

где c - положительная постоянная, а ${\displaystyle \alpha }$ это постоянная ${\displaystyle 0\leq \alpha \leq 1}$.

L-нотация используется в основном в вычислительная теория чисел, чтобы выразить сложность алгоритмов для сложных теория чисел проблемы, например сита для целочисленная факторизация и методы решения дискретные логарифмы. Преимущество этой записи в том, что она упрощает анализ этих алгоритмов. В ${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ выражает доминирующий термин, а ${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ заботится обо всем меньшем.

Когда ${\displaystyle \alpha }$ равно 0, то

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

это полиномиальная функция из lnп;

Когда ${\displaystyle \alpha }$ равно 1, тогда

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

полностью экспоненциальная функция из lnп (и тем самым полином от п).

Если ${\displaystyle \alpha }$ находится между 0 и 1, функция субэкспоненциальный из lnп (и суперполином ).

Примеры

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

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

для ${\displaystyle c=(64/9)^{1/3}\approx 1.923}$. Лучшим таким алгоритмом до сита числовых полей был алгоритм квадратное сито у которого есть время работы

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

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

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

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

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

где c оказалось не более 6.^[1]

История

L-нотация была определена в различных формах в литературе. Первое его использование пришло из Карл Померанс в своей статье «Анализ и сравнение некоторых алгоритмов целочисленного факторинга».^[2] Эта форма имела только ${\displaystyle c}$ параметр: ${\displaystyle \alpha }$ в формуле было ${\displaystyle 1/2}$ для алгоритмов, которые он анализировал. Померанс использовал письмо ${\displaystyle L}$ (или нижний регистр ${\displaystyle l}$) в этой и предыдущих статьях для формул, содержащих много логарифмов.

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

Справочник по прикладной криптографии определяет L-нотацию с большим ${\displaystyle O}$ вокруг формулы, представленной в этой статье.^[4] Это не стандартное определение. Большой ${\displaystyle O}$ предполагает, что время работы является верхней границей. Однако для алгоритмов целочисленного разложения и дискретного логарифмирования, для которых обычно используется L-нотация, время выполнения не является верхней границей, поэтому это определение не является предпочтительным.

использованная литература

1. Хендрик В. Ленстра-младший и Карл Померанс, "Проверка примитивности с гауссовскими периодами", препринт, 2011 г., http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
2. Карл Померанс, "Анализ и сравнение некоторых алгоритмов целочисленного факторизации", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf
3. Арьен К. Ленстра и Хендрик В. Ленстра-младший, «Алгоритмы в теории чисел», в Справочнике по теоретической информатике (том A): алгоритмы и сложность, 1991.
4. Альфред Дж. Менезес, Пол К. ван Оршот и Скотт А. Ванстон. Справочник по прикладной криптографии. CRC Press, 1996. ISBN  0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/.