| dbo:abstract
|
- Algoritmus LLL (také L3), rozepsaně Lenstrův-Lenstrův-Lovászův algoritmus pro redukci báze mříže je polynomický algoritmus publikovaný v roce 1982 , a László Lovászem a sloužící k nalezení redukované báze dané bodové mříže. Pro bodové mříže v prostoru o pěti a více rozměrech není znám žádný efektivní algoritmus pro nalezení nejkratší báze dané mříže, ale v řadě aplikací je postačující najít jeho aproximaci, kterou je možné efektivně najít právě algoritmem LLL. Původní aplikací metody bylo hledání rozkladu polynomů s racionálními koeficienty, ale později našla daleko rozmanitější uplatnění při řešení rozmanitých . Patřičné problémy se objevují například v kryptoanalýze některých asymetrických šifer (například RSA a NTRUEncrypt) nebo v rámci lineárního programování. (cs)
- Der LLL-Algorithmus ist ein nach Arjen Lenstra, Hendrik Lenstra und László Lovász benannter, 1982 veröffentlichter Algorithmus, der für ein Gitter eine Basis aus möglichst kurzen Vektoren berechnet. Diese Vektoren sind Approximationen für die kürzesten voneinander linear unabhängigen Vektoren des Gitters. Bei seiner Entdeckung war der LLL-Algorithmus der erste effiziente Gitterreduktionsalgorithmus. (de)
- Η αναγωγή βάσης ενός πλέγματος κατά Lenstra–Lenstra–Lovasz (LLL) είναι ένας αλγόριθμος που επινοήθηκε από τους , και Λάσλο Λοβάς το 1982. Αν μας δοθεί μία με ενός , ο LLL αλγόριθμος υπολογίζει μία δ-ΛΛΛ-ανηγμένη βάση (μικρά μήκη διανυσμάτων, σχεδόν ορθογώνια) σε πολυωνυμικό χρόνο. (el)
- L’algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau qui s'exécute en temps polynomial. (fr)
- The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis with n-dimensional integer coordinates, for a lattice L (a discrete subgroup of Rn) with , the LLL algorithm calculates an LLL-reduced (short, nearly orthogonal) lattice basis in time where is the largest length of under the Euclidean norm, that is, . The original applications were to give polynomial-time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions. (en)
- El algoritmo de simplificación de bases de retículos de Lenstra–Lenstra–Lovász (LLL) es un algoritmo de simplificación de retículos de complejidad polinomial inventado por , Hendrik Lenstra y László Lovász en 1982. Dada una base con coordenadas enteras n-dimensionales , de un retículo L en Rn con , el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo donde B es la longitud más larga de los bajo la norma euclídea. Las aplicaciones originales eran dar algoritmos de complejidad polinomial para factorizar polinomios que coeficientes racionales, para encontrar aproximaciones racionales simultáneas a los números reales, y para resolver el problema de la programación lineal entera en dimensiones fijadas. (es)
- Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, LLL-алгоритм) — алгоритм , разработанный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году. За полиномиальное время алгоритм преобразует базис на решётке (подгруппе ) в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей. Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки. (ru)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15569 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Der LLL-Algorithmus ist ein nach Arjen Lenstra, Hendrik Lenstra und László Lovász benannter, 1982 veröffentlichter Algorithmus, der für ein Gitter eine Basis aus möglichst kurzen Vektoren berechnet. Diese Vektoren sind Approximationen für die kürzesten voneinander linear unabhängigen Vektoren des Gitters. Bei seiner Entdeckung war der LLL-Algorithmus der erste effiziente Gitterreduktionsalgorithmus. (de)
- Η αναγωγή βάσης ενός πλέγματος κατά Lenstra–Lenstra–Lovasz (LLL) είναι ένας αλγόριθμος που επινοήθηκε από τους , και Λάσλο Λοβάς το 1982. Αν μας δοθεί μία με ενός , ο LLL αλγόριθμος υπολογίζει μία δ-ΛΛΛ-ανηγμένη βάση (μικρά μήκη διανυσμάτων, σχεδόν ορθογώνια) σε πολυωνυμικό χρόνο. (el)
- L’algorithme LLL, des initiales de A. Lenstra, H. Lenstra et L. Lovász, est un algorithme de réduction de réseau qui s'exécute en temps polynomial. (fr)
- Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, LLL-алгоритм) — алгоритм , разработанный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году. За полиномиальное время алгоритм преобразует базис на решётке (подгруппе ) в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей. Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки. (ru)
- Algoritmus LLL (také L3), rozepsaně Lenstrův-Lenstrův-Lovászův algoritmus pro redukci báze mříže je polynomický algoritmus publikovaný v roce 1982 , a László Lovászem a sloužící k nalezení redukované báze dané bodové mříže. Pro bodové mříže v prostoru o pěti a více rozměrech není znám žádný efektivní algoritmus pro nalezení nejkratší báze dané mříže, ale v řadě aplikací je postačující najít jeho aproximaci, kterou je možné efektivně najít právě algoritmem LLL. (cs)
- El algoritmo de simplificación de bases de retículos de Lenstra–Lenstra–Lovász (LLL) es un algoritmo de simplificación de retículos de complejidad polinomial inventado por , Hendrik Lenstra y László Lovász en 1982. Dada una base con coordenadas enteras n-dimensionales , de un retículo L en Rn con , el algoritmo LLL devuelve una base del retículo LLL-reducida (pequeña, casi ortogonal) en tiempo donde B es la longitud más larga de los bajo la norma euclídea. (es)
- The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis with n-dimensional integer coordinates, for a lattice L (a discrete subgroup of Rn) with , the LLL algorithm calculates an LLL-reduced (short, nearly orthogonal) lattice basis in time where is the largest length of under the Euclidean norm, that is, . (en)
|
| rdfs:label
|
- Algoritmus LLL (cs)
- LLL-Algorithmus (de)
- Αναγωγή Λένστρα–Λένστρα–Λοβάς (el)
- Algoritmo LLL (es)
- Algorithme LLL (fr)
- Lenstra–Lenstra–Lovász lattice basis reduction algorithm (en)
- Алгоритм Ленстры — Ленстры — Ловаса (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
