L-нотація

L-нотація — асимптотична нотація, аналогічна до О-нотації, записується як ${\displaystyle L_{n}[\alpha ,c]}$ при ${\displaystyle n}$, що прямує до нескінченності. Подібно до O-нотації, L-нотація зазвичай застосовується для оцінки обчислювальної складності алгоритмів. При цьому ${\displaystyle n}$ є деяким параметром вхідних даних алгоритму, пропорційним їх розміру: наприклад, кількість вершин і ребер у вхідному графі в алгоритмах пошуку найкоротшого шляху, або натуральне число в алгоритмах розкладання його на прості множники. Перевага L-нотації над O-нотацією полягає в тому, що вона спрощує аналіз алгоритмів.

Визначення

Нехай ${\displaystyle c>0}$, ${\displaystyle \alpha \in [0,1],}$ тоді

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

Множник ${\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)}}$ є поліномом від ${\displaystyle \ln n}$.

При ${\displaystyle \alpha =1}$ ${\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}}$ є експонентою від ${\displaystyle \ln n}$ (і також поліномом від ${\displaystyle n}$).

При ${\displaystyle 0<\alpha <1}$ ${\displaystyle L_{n}[\alpha ,c]}$ є субекспоненційною, тобто росте повільніше, ніж експонента з основою, більшою за 1, але швидше за будь-який поліном від ${\displaystyle \ln n}$.

Історія

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

Формулу, яка містить два параметри, запровадили ^[en] та ^[en] у своїй статті «Алгоритми в теорії чисел». Таку нотацію вони застосували для аналізу алгоритму Копперсміта обчислення дискретного логарифма. Їхня форма нотації частіше трапляється в сучасній літературі.

У літературі з криптографії трапляється визначення L-нотації через O-велике:

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

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

Приклади

Багато алгоритмів факторизації цілих чисел загального призначення мають субекспоненційну часову складність. Асимтотично найшвидшим є метод решета числового поля з оцінкою складності:

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

Для задачі дискретного логарифма на еліптичній кривій, найшвидшим алгоритмом загального призначення є ^[en]: час роботи оцінюється як квадратний корінь від порядку групи ${\displaystyle n}$. У L-нотації це записується наступним чином:

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

Тест простоти AKS потребує (поліноміального часу). Це означає, що складність тесту простоти може бути не більшою за

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

доведено, що ${\displaystyle c}$ не перевищує 6.

Примітки

1. Carl Pomerance. Analysis and comparison of some integer factoring algorithms. — 1982. — Т. Part 1. — С. 89-139.
2. Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
3. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. . http://www.cacr.math.uwaterloo.ca/hac/.
4. Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.