Оглавление
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
-
История и определение LLL-алгоритма
- LLL-алгоритм был предложен Арженом Ленстра, Хендриком Ленстра и Ласло Ловасом в 1982 году.
- Алгоритм вычисляет LLL-сокращенный базис решетки за полиномиальное время.
- Базис определяется как набор векторов, удовлетворяющих определенным условиям.
-
Основные свойства LLL-алгоритма
- Алгоритм вычисляет LLL-сокращенный базис, удовлетворяющий определенным условиям.
- Условия включают ограничение на длину векторов и условие Ловаса.
- Алгоритм гарантирует, что первый вектор в базисе не может быть намного больше самого короткого ненулевого вектора.
-
Применение LLL-алгоритма
- Алгоритм используется для факторизации многочленов с рациональными коэффициентами.
- Применяется для нахождения рациональных приближений к действительным числам.
- Используется для решения задач целочисленного линейного программирования.
-
Примеры и реализации
- Примеры включают использование алгоритма для доказательства гипотезы Мертенса и в криптоанализе.
- Алгоритм реализован в различных программных пакетах, таких как Arageli, fpLLL, FLINT, GAP, Macaulay2, Magma, Maple, Mathematica, NTL, PARI/GP, Pymatgen, SageMath и Isabelle/HOL.