L符号

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符号主要用于计算数论（英语：Computational number theory），表示困难数论问题之算法的复杂性，如整数分解的筛法及离散对数的解法。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符号的文献为卡尔·帕梅朗斯（英语：Carl Pomerance）所著的论文《一些整数分解算法的分析与比较》（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）的离散对数算法，为现在数学文献中最常使用的形式。