L-notation

L - notation är en asymptotisk notation som liknar O-notation , skriven somför att tendera mot oändligheten . Liksom Big O , används L-notation vanligtvis för att approximera beräkningskomplexiteten för en viss algoritm . Samtidigtrepresenterar den någon parameter för algoritmens indata, proportionell mot deras storlek: till exempel antalet hörn och kanter i inmatningsgrafen i algoritmer för att hitta den kortaste vägen i den, eller ett naturligt tal i algoritmer för att bryta ner det i enkla faktorer . $L_{n}[\alpha ,c]$ $n$ $n$

$L_{n}[\alpha ,c]$ bestäms av formeln

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

där är en positiv konstant och är en konstant . $c$ $\alfa$ $0\leq \alpha \leq 1$

L -notationen används främst i beräkningstalteori för att uttrycka komplexiteten hos algoritmer för svåra problem inom talteorin , såsom siktalgoritmer för att faktorisera naturliga tal till primtal och metoder för att beräkna diskreta logaritmer . Fördelen med denna notation är att förenkla analysen av algoritmer.

Faktorn in återspeglar den dominerande komponenten, och faktorn avser allt som är mindre betydande. Men när det är 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)))

är ett polynom i ln n , medan när lika med 1, $\alfa$

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

är en exponent för ln n (och därför ett polynom för n ). Om den är någonstans mellan 0 och 1, så är funktionen subexponentiell , det vill säga den växer långsammare än en exponentialfunktion med en bas som är större än 1 (eller superpolynom). $\alfa$ $L_{n}[\alpha ,c]$

Exempel

Många algoritmer för att dekomponera tal i primtalsfaktorer har subexponentiell tidskomplexitet. Den bästa metoden när det gäller att spara beräkningsresurser är den allmänna sifferfältsmetoden , som har uppskattningen:

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

för . ${\displaystyle c=(64/9)^{(1/3)))$

Den bästa algoritmen, innan utvecklingen av talfältssikten, var den kvadratiska siktmetoden , som har en komplexitetsuppskattning av:

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

För problemet med den diskreta logaritmen för en elliptisk kurva är den snabbaste allmänt tillämpliga algoritmen algoritmen för stora och små steg - Shanks-algoritmen , som har en asymtomatisk uppskattning av körtiden lika med kvadratroten av ordningen av gruppen n . I L -notation skrivs detta:

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

Förekomsten av ett AKS-primalitetstest , som körs i polynomtid , innebär att komplexiteten hos ett primalitetstest måste vara högst

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

och det är bevisat att c inte får överstiga 6. [1]

Historik

$L$ -notation har definierats i litteraturen på olika sätt. -notationen tillämpades först av Karl Pomerans i hans arbete "Analys och jämförelse av några heltalsfaktoriseringsalgoritmer" [2] . $L$

Denna form hade bara en parameter , som var en konstant i formeln . Pomerans använde en bokstav (eller liten ) i denna och föregående artikel för formler som innehåller många logaritmer. $c$ $\alfa$ $1/2$ $L$ $l$

Ovanstående formel som innehåller två parametrar introducerades av Arjen Lenstra och Hendrik Lenstra i deras uppsats "Algorithms in Number Theory" [3] , där notationen användes i analysen av den diskreta logaritmen av Coppersmiths algoritm . För närvarande är notationen den mest använda i litteraturen.

Manualen för tillämpad kryptografi definierar L -notationen som [4] :

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

Detta är inte en standarddefinition. antar att körtiden för agenten som exekverar algoritmen är begränsad från ovan. Men för heltalsfaktorisering och diskret logaritm är -notationen som används för utvärdering inte en övre gräns, så en sådan definition är inte helt korrekt. $O$ $L$

Anteckningar

↑ Hendirk W. Lenstra Jr. och Carl Pomerance, Primalitetstestning med gaussiska perioder Arkiverad 25 februari 2012 på Wayback Machine , förtryck, 2011.
↑ Carl Pomerance, analys och jämförelse av några heltalsfaktoreringsalgoritmer Arkiverad 4 februari 2021 på Wayback Machine , I Mathematisch Centrum Computational Methods in Number Theory, del 1, pp. 89-139, 1982.
↑ Arjen K. Lenstra och Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", i Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot och Scott A. Vanstone. Handbook of Applied Cryptography Arkiverad 7 mars 2005 på Wayback Machine . CRC Press, 1996. ISBN 0-8493-8523-7 .