Notazione L

La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come $L_n[\alpha ,c]$ per una variabile limitata $n$ tendente a infinito. Come la notazione O-grande, è usata di solito per rendere in maniera approssimativa la complessità computazionale di un particolare algoritmo.

Essa è definita come

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

dove c è una costante positiva, e $\alpha$ è una costante $0\le \alpha \le 1$.

La notazione L si usa principalmente nella teoria computazionale dei numeri, per esprimere la complessità degli algoritmi per i problemi difficili della teoria dei numeri, ad es. per la fattorizzazione degli interi e per i metodi di soluzione dei logaritmi discreti. Il beneficio di questa notazione è che semplifica l'analisi di questi logaritmi. La $e^{c(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}$ esprime il termine dominante, e la $e^{o(1)(\ln n{)}^{\alpha }(\ln \ln n{)}^{1-\alpha }}$ copre tutto ciò che è minore.

Quando $\alpha$ è 0, allora

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

è una funzione polinomiale di ln n; quando $\alpha$ è 1, allora

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

è una funzione completamente esponenziale di ln n (e quindi polinomiale in n).

Se $\alpha$ è compreso tra 0 e 1, la funzione è subesponenziale (e superpolinomiale).

Esempi

Molti algoritmi multiuso di fattorizzazione degli interi hanno complessità temporali subesponenziali. Il migliore è il crivello dei campi di numeri generale, che ha un tempo di esecuzione stimato di

$L_n[1/3,c]=e^{(c+o(1))(\ln n{)}^{1/3}(\ln \ln n{)}^{2/3}}$

per $c=(64/9{)}^{1/3}$. Il migliore di tali algoritmi anteriormente al crivello dei campi di numeri era il crivello quadratico, che ha tempo di esecuzione

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

Per il problema del logaritmo discreto delle curve ellittiche, il più veloce algoritmo multiuso è l'algoritmo baby-step giant-step. che ha un tempo di esecuzione sull'ordine della radice quadrata dell'ordine del gruppo n. Nella notazione L questo sarebbe

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

L'esistenza del test di primalità AKS, che funziona in tempo polinomiale, significa che è noto che la complessità temporale per i test di primalità è al massimo

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

dove si è provato che c è al massimo 6.

Storia

La notazione L è stata definita in varie forme nella letteratura. Il primo uso venne da Carl Pomerance nel suo scritto "Analysis and comparison of some integer factoring algorithms". Questa forma aveva soltanto il parametro $c$: l'$\alpha$ nella formula era $1/2$ per gli algoritmi che egli stava analizzando. Pomerance aveva usato la lettera $L$ (o la minuscola $l$) in questo e in precedenti studi per formule che coinvolgevano molti logaritmi.

La suddetta formula con due parametri fu introdotta da Arjen Lenstra ed Hendrik Lenstra nel loro articolo su "Algorithms in Number Theory". Fu introdotta nella loro analisi di un algoritmo di logaritmi discreti di Coppersmith. Questa è la forma usata più comuneme in letteratura oggi.

Lo Handbook of Applied Cryptography definisce la notazione L con una $O$ grande intorno alla formula presentata in questo articolo. Questa non è la definizione normale. La $O$ grande suggerirebbe che il tempo di esecuzione è un limite superiore. Tuttavia, per gli algoritmi di fattorizzazione degli interi e di logaritmi discreti per i quali si usa comunemente la notazione L, il empo di esecuzione non è un limite superiore, perciò questa definizione non è quella preferita.

Voci correlate

• Stima asintotica