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

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

Определение [ править ]

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

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

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

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

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

Когда 1 тогда ${\displaystyle \alpha }$

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

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

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

Примеры [ править ]

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

${\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}}.\,}$

Для задачи дискретного логарифмирования эллиптической кривой самым быстрым алгоритмом общего назначения является алгоритм гигантского шага маленького шага , время выполнения которого равно квадратному корню из группового порядка n . В 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-нотацию с большой буквы вокруг формулы, представленной в этой статье. ^[4] Это не стандартное определение. Большой предполагает, что время работы является верхней границей. Однако для алгоритмов целочисленного разложения и дискретного логарифмирования, для которых обычно используется L-нотация, время выполнения не является верхней границей, поэтому это определение не является предпочтительным.${\displaystyle O}$${\displaystyle O}$

Ссылки [ править ]