Введение
Алгоритм сведения базиса решетки Ленстра — Ленстра — Ловаса (LLL) — это алгоритм сведения решетки, работающий за полиномиальное время, изобретенный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году. Для решетки L (дискретная подгруппа Rn) с заданным базисом, состоящим из n-мерных целочисленных координат, и условием , алгоритм LLL вычисляет базис решетки, сведенный по LLL (короткий, почти ортогональный), за время , где — максимальная длина вектора в евклидовой норме, то есть, . Первоначальные применения были связаны с разработкой алгоритмов, работающих за полиномиальное время, для факторизации многочленов с рациональными коэффициентами, для нахождения одновременных рациональных приближений действительных чисел и для решения задачи целочисленного линейного программирования в фиксированной размерности.
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.
Приложения
Ранним успешным применением алгоритма LLL было его использование Эндрю Одлицко и Германом те Риле в опровержении гипотезы Мертенса. Алгоритм LLL нашёл множество других применений в алгоритмах обнаружения MIMO и криптоанализе схем шифрования с открытым ключом: криптосистемы «рюкзак», RSA с определёнными настройками, NTRUEncrypt и так далее. Алгоритм может быть использован для поиска целочисленных решений многих задач. В частности, алгоритм LLL составляет основу одного из алгоритмов поиска целочисленных соотношений. Например, если полагать, что r = 1.618034 является (слегка округлённым) корнем неизвестного квадратного уравнения с целочисленными коэффициентами, можно применить LLL-редукцию к решётке, порождённой векторами и . Первый вектор в редуцированном базисе будет целочисленной линейной комбинацией этих трёх, следовательно, обязательно будет иметь вид ; но такой вектор будет «коротким» только если a, b, c малы, а ещё меньше. Таким образом, первые три компоненты этого короткого вектора, вероятно, будут коэффициентами целочисленного квадратного многочлена, имеющего r в качестве корня. В этом примере алгоритм LLL находит кратчайший вектор [1, 1, 1, 0.00025], и действительно, многочлен имеет корень, равный золотому сечению, 1.6180339887.
Свойства основы с уменьшением LLL
Пусть $\mathbf{b}$ — LLL-приведенный базис решетки $\Lambda$. Из определения LLL-приведенного базиса можно вывести несколько других полезных свойств о $\Lambda$. Первый вектор в базисе не может быть значительно больше, чем кратчайший ненулевой вектор: в частности, для $n$-мерной решетки это дает $\| \mathbf{b}_1 \| \le 2^{n-1} \| \mathbf{v} \|$, где $\mathbf{v}$ — кратчайший ненулевой вектор. Первый вектор в базисе также ограничен определителем решетки: в частности, для $n$-мерной решетки это дает $\| \mathbf{b}_1 \| \le \sqrt{n} |\det(\Lambda)|^{1/n}$. Произведение норм векторов в базисе не может быть значительно больше, чем определитель решетки: пусть $N(\mathbf{b})$ — произведение норм векторов в базисе $\mathbf{b}$, тогда $N(\mathbf{b}) \le 2^{(n-1)n/2} |\det(\Lambda)|$.
The first vector in the basis cannot be much larger than the shortest non zero vector: In particular, for , this gives The first vector in the basis is also bounded by the determinant of the lattice: In particular, for , this gives The product of the norms of the vectors in the basis cannot be much larger than the determinant of the lattice: let , then .