s
19 708 Pages

la notation L Il est une notation asymptotique analogue à notation Big O, notée pour une variable dans la limite tendant vers l'infini. Comme la notation Big O est habituellement utilisé pour faire d'une manière grossière dans la complexité de calcul d'un particulier algorithme.

Elle est définie comme

c Il est une constante positive, et Il est une constante .

La notation L est utilisé principalement dans la théorie des nombres de calcul, pour exprimer la complexité des algorithmes pour des problèmes difficiles la théorie des nombres, par exemple. pour factorisation des entiers et des méthodes de résolution logarithmes discrets. L'avantage de cette notation est qu'elle simplifie l'analyse de ces logarithmes. la Elle exprime le terme dominant, et Il couvre tout ce qui est mineur.

quand Il est 0,

est un fonction polynomiale Dans n; quand Il est 1,

est un fonction exponentielle complètement Dans n (Et donc polynomiale n).

si est compris entre 0 et 1, la fonction est subesponenziale (et superpolinomiale).

Exemples

De nombreux algorithmes multi-usages factorisation des entiers Ils ont la complexité temporelle subesponenziali. Mieux la crible algébrique, dont il a un temps d'exécution estimé

pour . Le meilleur de ces algorithmes avant tamis des champs de numéro était tamis quadratique, que le temps d'exécution

Pour le problème de logarithme discret tout courbes elliptiques, le plus rapide algorithme polyvalent est l'algorithme baby-pas de géant étape. dont il a un temps d'exécution de l'ordre de la racine carrée de l'ordre du groupe n. Dans la notation L cela

L'existence de Test de primalité AKS, que les travaux polynomiale, signifie que l'on sait que la complexité du temps test de primalité Il est au plus

où il est prouvé que c Il est au plus 6.[1]

histoire

La notation L a été défini sous diverses formes dans la littérature. La première utilisation est venue de Carl Pomerance dans son article intitulé « Analyse et comparaison de certains algorithmes d'affacturage entier ».[2] Cette forme était que le paramètre : L ' la formule est pour les algorithmes qu'il analyse. Pomerance avait utilisé une lettre (Ou minuscules ) Dans les études et les précédents pour plusieurs formules impliquant logarithmes.

La formule ci-dessus impliquant deux paramètres a été introduit par Arjen Lenstra et Hendrik Lenstra dans leur article sur « les algorithmes dans la théorie des nombres ».[3] Il a été introduit dans leur analyse d'un algorithme logarithmes discrets de chaudronnier. C'est la forme utilisée le plus comuneme dans la littérature aujourd'hui.

la Manuel de Cryptographie appliquée Il définit la notation L avec un grand autour de la formule présentée dans cet article.[4] Ce n'est pas la définition normale. la Grande suggèrent que le temps d'exécution est une limite supérieure. Cependant, pour les algorithmes de factorisation des nombres entiers et logarithmes discrets pour qui utilise couramment la notation L, l'ime en cours d'exécution ne constitue pas une limite supérieure, de sorte que cette définition est l'option préférée.

notes

  1. ^ Hendirk W. Lenstra Jr. et Carl Pomerance, « Les tests de primalité avec des périodes gaussiennes », pré-presse, 2011.
  2. ^ Carl Pomerance, « L'analyse et la comparaison de certains algorithmes d'affacturage entier », en MATHEMATISCH Centrum Méthodes de calcul dans la théorie des nombres, Partie 1, pp. 89-139, 1982.
  3. ^ Arjen K. Lenstra et Hendrik W. Lenstra, Jr, "Algorithmes théorie des nombres", en Manuel de Theoretical Computer Science (vol d'A.): Algorithmes et complexité, 1991.
  4. ^ Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Manuel de Cryptographie appliquée, CRC Press, 1996. ISBN 0-8493-8523-7.

Articles connexes

  • estimé asymptotique

Activité wiki récente

Aidez-nous à améliorer BooWiki
Commencez