Notazione L

Da Wikipedia, l'enciclopedia libera.

La notazione L è una notazione asintotica analoga alla notazione O-grande, denotata come per una variabile limitata 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

dove c è una costante positiva, e è una costante .

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 esprime il termine dominante, e la copre tutto ciò che è minore.

Quando è 0, allora

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

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

Se è 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

per . Il migliore di tali algoritmi anteriormente al crivello dei campi di numeri era il crivello quadratico, che ha tempo di esecuzione

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'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

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 : l' nella formula era per gli algoritmi che egli stava analizzando. Pomerance aveva usato la lettera (o la minuscola ) 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 grande intorno alla formula presentata in questo articolo.[4] Questa non è la definizione normale. La 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]