Notazione L

Da Wikipedia, l'enciclopedia libera.

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 \leq \alpha \leq 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[modifica | modifica wikitesto]

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.[1]

Storia[modifica | modifica wikitesto]

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".[2] 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.

The suddetta formula che implica due parametri fu introdotta da Arjen Lenstra ed Hendrik Lenstra nel loro articolo su "Algorithms in Number Theory".[3] 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.[4] 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 esecuione non è un limite superiore, perciò questa definizione non è quella preferita.

Note[modifica | modifica wikitesto]

  1. ^ Hendirk W. Lenstra Jr. e Carl Pomerance, "Primality testing with Gaussian periods", prestampa, 2011.
  2. ^ Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", in Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982.
  3. ^ Arjen K. Lenstra e Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
  4. ^ Alfred J. Menezes, Paul C. van Oorschot e Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996. ISBN 0-8493-8523-7.

Voci correlate[modifica | modifica wikitesto]