L符號

L符號是個類似大O符號的漸近符號，標記為${\displaystyle L_{n}[\alpha ,c]}$，多用於表示特定演算法的計算複雜性。

定義

L符號的定義如下：

${\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符號主要用於計算數論，表示困難數論問題之演算法的複雜性，如整數分解的篩法及離散對數的解法。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 n的多項式函數；而當${\displaystyle \alpha }$為1時，

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

則會是ln n的指數函數（即n的多項式函數）。

當${\displaystyle \alpha }$介於0與1之間時，L符號為ln n的次指數（與超越多項數）函數。

例子

許多通用的整數分解演算法都具有次指數複雜度，其中目前已知最快的為普通數域篩選法，其時間複雜度估算為

${\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}$。在普通數域篩法出現前，最快的整數分析演算法為二元篩法（英語：Quadratic sieve），其時間複雜度估算為

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

對橢圓曲線離散對數問題而言，目前已知最快的通用演算法為大步小步法（英語：Baby-step giant-step），其時間複雜估算為群階的開平方。以L符號表示為

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

目前已知最快測試一個數是否為質數的演算法為AKS質數測試，其時間複雜度為多項式時間，以L符號表示為

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

其中，c已被證明至多為6^[1]。

歷史

最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解演算法的分析與比較》（Analysis and comparison of some integer factoring algorithms）^[2]。在此論文中，L符號的參數只有${\displaystyle c}$，其中的${\displaystyle \alpha }$則因其所分析的演算法而設為${\displaystyle 1/2}$。

具有兩個參數的L符號則由阿爾揚·倫斯特拉（英語：Arjen Lenstra）及亨德里克·倫斯特拉在其論文《數論中的演算法》（Algorithms in Number Theory）^[3]中首次引入，用以分析唐·科普斯密思（英語：Don Coppersmith）的離散對數演算法，為現在數學文獻中最常使用的形式。

參考資料

1. Hendrik W. Lenstra Jr.; Carl Pomerance. Primality testing with Gaussian periods (PDF). 2011 [2018-04-01]. （原始內容 (PDF)存檔於2012-02-25）.
2. Carl Pomerance. Analysis and comparison of some integer factoring algorithms (PDF). Computational Methods in Number Theory, Part 1. Mathematisch Centrum. 1982: 89–139 [2018-04-01]. （原始內容存檔 (PDF)於2021-02-04）.
3. Arjen K. Lenstra; Hendrik W. Lenstra, Jr. Algorithms in Number Theory. Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity. 1991.