L-notatie - L-notation

L - notatie is een asymptotische notatie analoog aan big-O-notatie , aangeduid alseen gebonden variabele neigt naar oneindigheid . Net als big-O-notatie, wordt het meestal gebruikt om de ongeveer brengen computationele complexiteit van een bepaald algoritme . ${\ Displaystyle L_ {n} [\ a, c]}$ ${\ N} displaystyle$

Definitie

Hieronder wordt verstaan

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

waarbij c een positieve constante en is een constante . ${\ Displaystyle \ alpha}$${\ Displaystyle 0 \ eq \ a \ 1 eq}$

L-notatie wordt meestal gebruikt in computationele getaltheorie , de complexiteit van algoritmen voor moeilijke drukken getaltheorie problemen, bijvoorbeeld zeven te ontbinden in priemfactoren en werkwijzen voor het oplossen van discrete logaritmen . Het voordeel van deze notatie is dat het de analyse van deze algoritmen vereenvoudigt. Het drukt de dominante term, en het zorgt voor alles kleiner. ${\ Displaystyle e ^ c {(\ ln n) ^ {\ alpha} (\ ln \ ln n) ^ {1- \ alpha}}}$${\ Displaystyle e ^ {o (1) (\ ln n) ^ {\ alpha} (\ ln \ ln n) ^ {1- \ alpha}}}$

Wanneer 0 is, ${\ Displaystyle \ alpha}$

${\ Displaystyle L_ {n} [\ a, c] = L_ {n} [0, c] = e ^ {(c + o (1)) \ ln \ ln n} = (\ ln n) ^ {c + o (1)} \,}$

een polynoom functie van ln  n ; wanneer 1 is, ${\ Displaystyle \ alpha}$

${\ Displaystyle L_ {n} [\ a, c] = L_ {n} [1, c] = e ^ {(c + o (1)) \ ln n} = n ^ {c + o (1)} \,}$

een volledig exponentiële functie van ln  n (en daardoor polynoom n ).

Indien tussen 0 en 1, de functie subexponential ln  n (en superpolynomial ). ${\ Displaystyle \ alpha}$

Voorbeelden

Veel general-purpose ontbinden in priemfactoren algoritmen subexponential tijd complexiteit . Het beste is de getallenlichamenzeef , die een verwachte looptijd van heeft

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

voor . De beste dergelijke algoritme vóór het nummerveld zeef was kwadratische zeef die looptijd heeft ${\ Displaystyle c = (64/9) ^ {1/3} \ ca. 1.923}$

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

Voor de elliptische curve discrete logaritme probleem, de snelste algemene algoritme is de baby stap giant-stap algoritme, dat een looptijd van de orde van de vierkantswortel van de groepsvolgorde heeft n . In L -notatie zou dit

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

Het bestaan van de AKS-test , die loopt in polynomiale tijd betekent dat de tijdscomplexiteit voor priemtesten bekend is dat hoogstens

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

waarin c is bewezen hoogstens 6 te zijn.

Geschiedenis

L-notatie is gedefinieerd in verschillende vormen gedurende de literatuur. Het eerste gebruik van het kwam van Carl Pomerance in zijn paper "Analyse en vergelijking van een aantal integer factoring algoritmen". Deze vorm had alleen de parameter: de in de formule was voor de algoritmes hij analyseerde. Pomerance gebruik hadden gemaakt van de brief (of kleine letters ) in deze en eerdere papieren voor formules die betrokken zijn veel logaritmes. ${\ Displaystyle c}$${\ Displaystyle \ alpha}$${\ Displaystyle 1/2}$${\ Displaystyle L}$${\ L} displaystyle$

De bovenstaande formule waarbij twee parameters werd geïntroduceerd door Arjen Lenstra en Hendrik Lenstra in hun artikel over "algoritmen in de getaltheorie". Het werd geïntroduceerd in hun analyse van een discrete logaritme algoritme van koperslager . Dit is de meest gebruikte vorm in de literatuur van vandaag.

Het Handbook of Applied Cryptography definieert de L-notatie met een grote rond de formule in dit artikel. Dit is niet de standaard definitie. De grote zou suggereren dat de looptijd is een bovengrens. Voor het gehele getal en ontbinden discrete logaritme algoritmen die L-notatie gewoonlijk wordt gebruikt voor de looptijd is geen bovengrens, zodat deze definitie niet de voorkeur. ${\ Displaystyle O}$${\ Displaystyle O}$

Referenties