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

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

Определение

Это определяется как

$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 }}$ выражает доминирующий термин, а $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ заботится обо всем меньшем.

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

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

– полилогарифмическая функция ( полиномиальная функция от ln n );

Когда $\alpha$ тогда 1

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

является полностью экспоненциальной функцией от ln n (и, следовательно, полиномиальной по n ).

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

Примеры

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

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

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

$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.

История

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

Приведенная выше формула с двумя параметрами была представлена ​​Арьеном Ленстрой и Хендриком Ленстрой в их статье «Алгоритмы в теории чисел». Он был введен при анализе дискретного логарифмирования алгоритма Копперсмита . Это наиболее часто используемая форма в современной литературе.

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