L-notation

L - notation er en asymptotisk notation, der ligner O-notation , skrevet somfor at tendere til uendeligt . Ligesom Big O bruges L-notation normalt til at tilnærme beregningskompleksiteten af en bestemt algoritme . Samtidigrepræsenterer den en eller anden parameter for algoritmens inputdata, proportional med deres størrelse: for eksempel antallet af hjørner og kanter i inputgrafen i algoritmer til at finde den korteste vej i den, eller et naturligt tal ialgoritmer til at dekomponere det i simple faktorer . $L_{n}[\alpha ,c]$ $n$ $n$

$L_{n}[\alpha ,c]$ bestemmes af formlen

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

hvor er en positiv konstant og er en konstant . $c$ $\alfa$ $0\leq \alpha \leq 1$

L -notationen bruges primært i beregningsmæssig talteori til at udtrykke kompleksiteten af algoritmer til svære problemer i talteori , såsom sigtealgoritmer til faktorisering af naturlige tal til primfaktorer og metoder til beregning af diskrete logaritmer . Fordelen ved denne notation er at forenkle analysen af algoritmer.

Faktoren i afspejler den dominerende komponent, og faktoren refererer til alt mindre væsentligt. Men når det er 0, $e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $L_{n}[\alpha ,c]$ $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $\alfa$

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

er et polynomium i ln n , mens når lig med 1, $\alfa$

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

er en eksponent for ln n (og derfor et polynomium af n ). Hvis den er et sted mellem 0 og 1, så er funktionen subeksponentiel, det vil sige, den vokser langsommere end en eksponentiel funktion med en base større end 1 (eller superpolynomium). $\alfa$ $L_{n}[\alpha ,c]$

Eksempler

Mange algoritmer til at dekomponere tal i primfaktorer har subeksponentiel tidskompleksitet. Den bedste metode med hensyn til at spare beregningsressourcer er den generelle talfeltsigtemetode , som har estimatet:

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

for . ${\displaystyle c=(64/9)^{(1/3)))$

Den bedste algoritme, før udviklingen af talfeltsigten, var den kvadratiske sigtemetode , som har et kompleksitetsestimat på:

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

For problemet med den diskrete logaritme af en elliptisk kurve er den hurtigste generelt anvendelige algoritme algoritmen for store og små trin - Shanks-algoritmen , som har et asymptomatisk køretidsestimat svarende til kvadratroden af rækkefølgen af gruppen n . I L -notation skrives dette:

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

Eksistensen af en AKS primalitetstest , som kører i polynomisk tid , betyder, at kompleksiteten af en primalitetstest højst må være

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

og det er bevist, at c ikke må overstige 6. [1]

Historie

$L$ -notation er blevet defineret i litteraturen på forskellige måder. -notationen blev først anvendt af Karl Pomerans i hans arbejde "Analyse og sammenligning af nogle heltalsfaktoriseringsalgoritmer" [2] . $L$

Denne form havde kun én parameter , som var en konstant i formlen . Pomerans brugte et bogstav (eller lille ) i denne og den foregående artikel til formler, der indeholder mange logaritmer. $c$ $\alfa$ $1/2$ $L$ $l$

Ovenstående formel, der indeholder to parametre, blev introduceret af Arjen Lenstra og Hendrik Lenstra i deres papir "Algorithms in Number Theory" [3] , hvor notationen blev brugt i analysen af den diskrete logaritme af Coppersmith 's algoritme . I øjeblikket er notationen den mest anvendte i litteraturen.

Den anvendte kryptografimanual definerer L -notationen som [4] :

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

Dette er ikke en standarddefinition. antager, at køretiden for den agent, der udfører algoritmen, er afgrænset ovenfra. Men for heltalsfaktorisering og diskret logaritme er -notationen, der bruges til evaluering, ikke en øvre grænse, så en sådan definition er ikke helt korrekt. $O$ $L$

Noter

↑ Hendirk W. Lenstra Jr. og Carl Pomerance, Primalitetstest med gaussiske perioder Arkiveret 25. februar 2012 på Wayback Machine , fortryk, 2011.
↑ Carl Pomerance, Analyse og sammenligning af nogle heltal factoring algoritmer Arkiveret 4. februar 2021 på Wayback Machine , I Mathematisch Centrum Computational Methods in Number Theory, del 1, s. 89-139, 1982.
↑ Arjen K. Lenstra og Hendrik W. Lenstra, Jr., "Algorithms in Number Theory", i Handbook of Theoretical Computer Science (bind A): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot og Scott A. Vanstone. Handbook of Applied Cryptography Arkiveret 7. marts 2005 på Wayback Machine . CRC Press, 1996. ISBN 0-8493-8523-7 .