L-notation is an asymptotic notation analogous to big-O notation, denoted as for a bound variable tending to infinity. Like big-O notation, it is usually used to roughly convey the rate of growth of a function, such as the computational complexity of a particular algorithm.
It is defined as
where c is a positive constant, and is a constant .
L-notation is used mostly in computational number theory, to express the complexity of algorithms for difficult number theory problems, e.g. sieves for integer factorization and methods for solving discrete logarithms. The benefit of this notation is that it simplifies the analysis of these algorithms. The expresses the dominant term, and the takes care of everything smaller.
When is 0, then
is a polylogarithmic function (a polynomial function of ln n);
When is 1 then
is a fully exponential function of ln n (and thereby polynomial in n).
If is between 0 and 1, the function is subexponential of ln n (and superpolynomial).
Many general-purpose integer factorization algorithms have subexponential time complexities. The best is the general number field sieve, which has an expected running time of
for . The best such algorithm prior to the number field sieve was the quadratic sieve which has running time
For the elliptic curve discrete logarithm problem, the fastest general purpose algorithm is the baby-step giant-step algorithm, which has a running time on the order of the square-root of the group order n. In L-notation this would be
The existence of the AKS primality test, which runs in polynomial time, means that the time complexity for primality testing is known to be at most
where c has been proven to be at most 6.
L-notation has been defined in various forms throughout the literature. The first use of it came from Carl Pomerance in his paper "Analysis and comparison of some integer factoring algorithms". This form had only the parameter: the in the formula was for the algorithms he was analyzing. Pomerance had been using the letter (or lower case ) in this and previous papers for formulae that involved many logarithms.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science,
as well as on real-world secure systems. They underlie delegation of computation protocols a
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
En théorie des nombres, l'algorithme du crible du corps de nombres généralisé (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10100, et ne possède pas de structure remarquable. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses).
La notation L est un analogue aux notations de Landau en notation asymptotique. Cette notation a été introduite par Carl Pomerance en 1982 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.
L'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
Couvre le théorème de la valeur moyenne dans le calcul différentiel, en se concentrant sur les points critiques et les extrema globaux dans les intervalles.
Couvre la méthode Quadratic Sieve pour la factorisation entière, soulignant l'importance de choisir les bons paramètres pour la factorisation efficace.