L表記

L表記は、ビッグO 表記に類似した漸近表記で、無限大に向かう束縛変数に対して特定のアルゴリズムの計算の複雑さなど、関数の増加率を大まかに伝えるために使用されます。 ${\displaystyle L_{n}[\alpha ,c]}$ ${\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 表記法は主に計算数論で使用され、整数因数分解のふるいや離散対数を解く方法など、難しい数論の問題に対するアルゴリズムの複雑さを表現します。この表記法の利点は、これらのアルゴリズムの分析が簡素化されることです。 は主要な項を表現し、 は それより小さい項すべてを処理します。 ${\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 表記法は文献を通じてさまざまな形式で定義されています。最初に使用されたのは、Carl Pomeranceの論文「いくつかの整数因数分解アルゴリズムの分析と比較」です。^[2]この形式にはパラメータ のみがありました。つまり、式の は、彼が分析していたアルゴリズムのものです。Pomerance は、この論文と以前の論文で、多くの対数を含む式に 文字(または小文字の)を使用していました。${\displaystyle c}$${\displaystyle \alpha}$${\displaystyle 1/2}$${\displaystyle L}$${\displaystyle l}$

2つのパラメータを含む上記の式は、Arjen LenstraとHendrik Lenstraが「数論におけるアルゴリズム」という論文で導入しました。^{[3]これは、} Coppersmithの離散対数アルゴリズム の分析で導入されました。これは、今日の文献で最も一般的に使用されている形式です。

応用暗号ハンドブックでは、この記事で紹介した式を囲む大括弧でL表記を定義しています。 ^[4] これは標準的な定義ではありません。大括弧は実行時間が上限であることを示唆しています。しかし、L表記が一般的に使用される整数因数分解アルゴリズムや離散対数アルゴリズムでは、実行時間は上限ではないため、この定義は推奨されません。 ${\displaystyle O}$${\displaystyle O}$