Lenstra–Lenstra–Lovász lattice basis reduction algorithm (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | http://pymatgen.org/ http://www.arageli.org/ https://github.com/fplll/fplll https://github.com/libntl/ntl http://www.numdam.org/item%3Fid=JTNB_1996__8_2_387_0 |
| dbo:wikiPageID | 1735228 (xsd:integer) |
| dbo:wikiPageLength | 15569 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1098053686 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quadratic_equation dbr:Basis_(linear_algebra) dbr:Algorithm dbr:Integer_relation_algorithm dbr:GAP_computer_algebra_system dbr:Public-key_encryption dbr:Mathematica dbr:SageMath dbr:Orthogonal dbr:Golden_ratio dbc:Lattice_points dbr:Coppersmith_method dbr:Andrew_Odlyzko dbr:László_Lovász dbr:Macaulay2 dbr:Lattice_(group) dbr:Lattice_problem dbr:Lattice_reduction dbr:Linear_combination dbr:Linear_programming dbr:Fast_Library_for_Number_Theory dbr:PARI/GP dbr:Dirichlet's_approximation_theorem dbr:Gram–Schmidt_process dbr:Hendrik_Lenstra dbr:Arjen_Lenstra dbc:Computational_number_theory dbc:Theory_of_cryptography dbr:Herman_te_Riele dbr:Polynomial dbr:Polynomial_time dbr:Mertens_conjecture dbr:RSA_(algorithm) dbr:MIMO dbr:Root_of_a_function dbr:Naccache-Stern_knapsack_cryptosystem dbr:NTRUEncrypt dbr:Magma_computer_algebra_system dbr:Polynomial_factorization dbr:Maple_computer_algebra_system dbr:Isabelle/HOL |
| dbp:wikiPageUsesTemplate | dbt:Open-closed dbt:Number-theoretic_algorithms dbt:Cite_book dbt:Cite_journal dbt:Harv dbt:Reflist dbt:Short_description dbt:Use_dmy_dates |
| dct:subject | dbc:Lattice_points dbc:Computational_number_theory dbc:Theory_of_cryptography |
| rdf:type | yago:WikicatAsymmetric-keyAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| 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 | freebase:Lenstra–Lenstra–Lovász lattice basis reduction algorithm wikidata:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-cs:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-de:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-el:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-es:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-fr:Lenstra–Lenstra–Lovász lattice basis reduction algorithm dbpedia-ru:Lenstra–Lenstra–Lovász lattice basis reduction algorithm https://global.dbpedia.org/id/eryP |
| prov:wasDerivedFrom | wikipedia-en:Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm?oldid=1098053686&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm |
| is dbo:knownFor of | dbr:Hendrik_Lenstra |
| is dbo:wikiPageDisambiguates of | dbr:Lovász |
| is dbo:wikiPageRedirects of | dbr:Lenstra-Lenstra-Lovász_lattice_basis_reduction_algorithm dbr:Lenstra–Lenstra–Lovasz_lattice_basis_reduction_algorithm dbr:LLL-reduced dbr:LLL_algorithm dbr:LLL_basis_reduction_method dbr:Lenstra-Lenstra-Lovasz_algorithm dbr:Lenstra-Lenstra-Lovasz_lattice_basis_reduction_algorithm dbr:Lenstra-Lenstra-Lovasz_lattice_reduction_algorithm dbr:Lenstra-Lenstra-Lovász_lattice_reduction_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Integer_relation_algorithm dbr:List_of_polynomial_topics dbr:Minkowski's_theorem dbr:Coppersmith_method dbr:András_Frank dbr:László_Lovász dbr:Machin-like_formula dbr:Lattice_(group) dbr:Lattice_problem dbr:Lattice_reduction dbr:Euclidean_algorithm dbr:Brigitte_Vallée dbr:Korkine–Zolotarev_lattice_basis_reduction_algorithm dbr:Hendrik_Lenstra dbr:Arjen_Lenstra dbr:Hermite_normal_form dbr:Mertens_conjecture dbr:Factorization_of_polynomials dbr:LLL dbr:Lovász dbr:Lenstra-Lenstra-Lovász_lattice_basis_reduction_algorithm dbr:Lenstra–Lenstra–Lovasz_lattice_basis_reduction_algorithm dbr:LLL-reduced dbr:LLL_algorithm dbr:LLL_basis_reduction_method dbr:Lenstra-Lenstra-Lovasz_algorithm dbr:Lenstra-Lenstra-Lovasz_lattice_basis_reduction_algorithm dbr:Lenstra-Lenstra-Lovasz_lattice_reduction_algorithm dbr:Lenstra-Lenstra-Lovász_lattice_reduction_algorithm |
| is dbp:knownFor of | dbr:Hendrik_Lenstra dbr:Arjen_Lenstra |
| is foaf:primaryTopic of | wikipedia-en:Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm |