L-notasyonu - L-notation

L - gösterimde bir olduğunu asimptotik benzer gösterim Büyük O gösterimi olarak gösterilmektedir,for a bağlı değişken sonsuza eğilimi . Büyük O notasyonu gibi, genellikle kabaca iletmek için kullanılan hesaplama karmaşıklığı belirli bir algoritma . ${\ Displaystyle L_ {n} [\ a, c]}$ ${\ Displaystyle n}$

Tanım

Bu gibi tanımlanmıştır

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

burada C , bir pozitif bir sabittir ve bir sabittir . ${\ Displaystyle \ a}$${\ Displaystyle 0 \ leq \ a \ leq 1}$

L-gösterimde çok kullanılan hesaplama sayısı teorisi zor için algoritmaların karmaşıklığı ifade etmek için, sayılar teorisi sorunları, örneğin elek tamsayıdır çarpanlara ve çözmek için yöntemler ayrık logaritma . Bu gösterimde yararı bu algoritmaların analizini kolaylaştırmasıdır. Baskın terimini dile getiriliyor ve daha küçük her şeyi halleder. ${\ Displaystyle e ^ {C (\ ln n) ^ {\ a} (\ ln \ ln n) ^ {1- \ a}}}$${\ Displaystyle e ^ {o- (1) (\ ln n) ^ {\ a} (\ ln \ ln n) ^ {1- \ a}}}$

Zaman 0, daha sonra ise ${\ Displaystyle \ a}$

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

a, polinom fonksiyonu LN  n ; zaman daha sonra 1 ${\ Displaystyle \ a}$

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

Tam bir üstel fonksiyon LN  n (ve böylece de permütasyon n ).

Eğer , 0 ile 1 arasında, işlevi altüssel LN  n (ve superpolynomial ). ${\ Displaystyle \ a}$

Örnekler

Birçok genel amaçlı tamsayı çarpanlara algoritmalar var altüssel zaman karmaşıklığını . En iyisi genel sayı alan elek beklenen işletim süresine sahip olması,

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

için . Numara alan elek öncesinde iyi böyle algoritma oldu kuadratik elek çalışan zamanı var ${\ Displaystyle c = (64/9) ^ {1/3} yaklaşık 1.923 \}$

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

İçin eliptik eğri kesikli logaritma problemi, en hızlı genel amaçlı algoritmasıdır bebek adımlı dev adımlı grubu sırası kare kökü sırasına üzerinde bir işletim süresinin sahip algoritması, n . In L -notation bu olurdu

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

Varlığı AKS asallık testi çalışır, polinom zamanda , zaman karmaşıklığı demektir primality test en olduğu bilinen

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

nerede c en fazla 6 olduğu kanıtlanmıştır.

Tarihçe

L-gösterimde literatürde boyunca çeşitli şekillerde tanımlanmıştır. Bunun ilk kullanımı geldi Carl Pomerance'nin onun kağıt "Analiz ve bazı tamsayı faktoring algoritmaların karşılaştırılması" in. Bu şekilde, sadece vardı parametresi: Formül olduğu o analiz edildi algoritmaları için. Pomerance mektubu kullanarak olmuştu (veya küçük harf birçok logaritma dahil formüller için bu ve daha önceki makalelerde). ${\ Displaystyle C}$${\ Displaystyle \ a}$${\ Displaystyle 1/2}$${\ Displaystyle L}$${\ Displaystyle il}$

İki parametreyi içeren yukarıdaki formül tarafından tanıtıldı Arjen Lenstra ve Hendrik Lenstra "Numara Kuramı Algoritmalar" konulu makalelerinde. Bu kendi analizi tanıtılan ayrık logaritma algoritması Bakırcı . Bu literatürde en çok kullanılan formu bugün.

Uygulamalı Kriptografi Handbook of büyük bir L-gösterimi tanımlayan bu yazıda formül çevresinde. Bu standart tanımlı değil. Büyük çalışan zaman bir üst sınırdır öneririm. Ancak L-gösterimde yaygın kullanılan tamsayı faktoring ve ayrık logaritma algoritmaları için, işletim süresi, bir üst sınır değildir, bu nedenle bu tanımlama tercih edilmez. ${\ Displaystyle O}$${\ Displaystyle O}$

Referanslar