Notation L
La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982[1] pour comparer différents algorithmes de factorisation et a été généralisée à deux paramètres par Arjen Lenstra et Hendrik Lenstra. Elle est principalement utilisée en théorie algorithmique des nombres, où elle permet de donner une échelle entre les différents algorithmes exponentiels. En effet représente les fonctions polynomiales de ln (n) de degré c, et les fonctions exponentielles en la taille de l’entrée (ici, la taille est prise comme étant , ce qui est le cas pour la représentation binaire des nombres), donc représente les fonctions polynomiales de n de degré c.
![{\displaystyle L_{n}[0,c]=\ln(n)^{c+o(1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cf5fe2a3f00e34fe973842016aac03ef1c37017)
![{\displaystyle L_{n}[1,c]=n^{c+o(1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fbad50952c1d53738fbfaf0384701e0b125c12fb)
![{\displaystyle L_{n}[1,c]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0d56db098fe988c09947d40bf0d798a972589bc)
Définition
La notation L est définie comme suit pour :
![{\displaystyle \alpha \in [0,1],c\in \mathbb {R} _{+}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af1fbce07c08f833f2c83973ae979b960e0731cc)
![{\displaystyle L_{n}[\alpha ,c]=\exp \left((c+o(1))\ln(n)^{\alpha }(\ln \ln(n))^{1-\alpha }\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66b8000d0791b6621625efc49d496752e2c741a4)
On peut remarquer que contrairement à la notation grand-O, la constante est ici importante puisqu’elle se retrouve dans l’exponentielle. Ce qui fait qu’un gain sur la constante peut réduire considérablement les temps de calcul.
Par exemple :
- .
- .
- .
![{\displaystyle L_{n}\left[0,c\right]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/720da30774706c99439df0b13f8e867863337488)
![{\displaystyle L_{n}\left[1,{\tfrac {1}{2}}\right]=e^{({\tfrac {1}{2}}+o(1))\ln n}=n^{1/2+o(1)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59594330f29a54800d448e61650219ab97f251a9)
![{\displaystyle L_{n}\left[{\tfrac {1}{2}},c\right]=e^{(c+o(1)){\sqrt {\ln(n)\ln(\ln(n))}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f47ffb6af223ad64db22ab8c3391de7c342e5dd)
Exemples
La complexité du crible algébrique pour la résolution de la factorisation est en notation L : .
![{\displaystyle L_{n}\left[{\tfrac {1}{3}},{\sqrt[{3}]{\tfrac {64}{9}}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3230dc4f7fe01d601671fd51f51a8b44eb8f7b22)
En comparaison, le précédent meilleur algorithme pour la factorisation, le crible quadratique fonctionnait en temps .
![{\displaystyle L_{n}\left[{\tfrac {1}{2}},1\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93a4da30364646bdfc2b64e89e1dddafc471475e)
De manière similaire, pour le problème du logarithme discret dans les sous-groupes d'ordre n d'une courbe elliptique sur un corps fini, les meilleurs algorithmes ne peuvent fonctionner en moins de [2], il s’agit d'algorithmes exponentiels comme l'algorithme baby-step giant-step.
![{\displaystyle L_{n}\left[1,{\tfrac {1}{2}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80151a11fab42dd03212999d927c5cce06549c4b)
Notes et références
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « L-notation » (voir la liste des auteurs).
Bibliographie
- [Pomerance 1982] (en) Carl Pomerance, « Analysis and comparison of some integer factoring algorithms », Mathematisch Centrum Computational Methods in Number Theory, , p. 89−139 (lire en ligne [PDF])
- [Shoup 1997] Victor Shoup, « Lower bounds for discrete logarithms and related problems », Eurocrypt, (lire en ligne [PDF])
Portail de l'informatique théorique 
Arithmétique et théorie des nombres
