Алгоритм Ленстры — Ленстры — Ловаса

Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, LLL-алгоритм) — алгоритм , разработанный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году. За полиномиальное время алгоритм преобразует базис на решётке (подгруппе ) в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей. Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки.

История Алгоритм был разработан голландскими математиками Арьеном Ленстрой и Хендриком Ленстрой совместно с венгерским математиком Ласло Ловасом в 1982 году.

Основной предпосылкой для создания ЛЛЛ-алгоритма послужило то, что процесс Грама ― Шмидта работает только с векторами, компоненты которых являются вещественными числами. Для векторного пространства процесс Грама ― Шмидта позволяет преобразовать произвольный базис в ортонормированный («идеал», к которому стремится ЛЛЛ-алгоритм). Но процесс Грама ― Шмидта не гарантирует того, что на выходе каждый из векторов будет целочисленной линейной комбинацией исходного базиса. Таким образом, полученный в результате набор векторов может и не являться базисом исходной решётки. Это привело к необходимости создания специального алгоритма для работы с решётками.

Изначально алгоритм использовался для факторизации многочленов с целыми коэффициентами, вычисления диофантовых приближений вещественных чисел и для решения задач линейного программирования в пространствах фиксированной размерности, а впоследствии и для криптоанализа.

Редукция базиса Решётка в евклидовом пространстве — это подгруппа группы , порожденная линейно независимыми векторами из , называемыми базисом решётки. Любой вектор решётки может быть представлен целочисленной линейной комбинацией базисных векторов. Базис решётки определяется неоднозначно: на рисунке изображены два различных базиса одной и той же решётки.

Редукция базиса заключается в приведении базиса решётки к особому виду, удовлетворяющему некоторым свойствам. Редуцированный базис должен быть, по возможности, наиболее коротким среди всех базисов решётки и близким к ортогональному (что выражается в том, что итоговые коэффициенты Грама — Шмидта должны быть не больше ).

Пусть в результате преобразования базиса с помощью процесса Грама ― Шмидта получен базис , с коэффициентами Грама — Шмидта, определяемыми следующим образом:

, для всех таких, что .

Тогда (упорядоченный) базис называется -ЛЛЛ-редуцированным базисом (где параметр находится в промежутке ), если он удовлетворяет следующим свойствам:

Для всех таких, что . (условие уменьшения размера) Для имеет место: . (условие Ловаса)

Здесь — норма вектора, — cкалярное произведение векторов.

Изначально Ленстра, Ленстра и Ловас в своей статье продемонстрировали работу алгоритма для параметра . Несмотря на то что алгоритм остаётся корректным и для , его работа за полиномиальное время гарантируется только для в промежутке .

Свойства редуцированного базиса Пусть  — сокращённый алгоритмом ЛЛЛ с параметром базис на решётке . Из определения такого базиса можно получить несколько свойств . Пусть  — норма кратчайшего вектора решётки, тогда:

Первый вектор базиса не может быть значительно длиннее кратчайшего ненулевого вектора:. В частности, для получается . Первый вектор базиса ограничен определителем решётки:. В частности, для получается . Произведение норм векторов не может быть сильно больше определителя решётки:. В частности, для .

Базис, преобразованный методом ЛЛЛ, почти самый короткий из всех возможных, в том смысле, что существуют абсолютные границы такие, что первый базисный вектор не более чем в раз длиннее самого короткого вектора решётки, аналогично, второй вектор базиса не более чем в раз превосходит второй кратчайший вектор решётки и так далее (что прямо следует из свойства 1).

Алгоритм Входные данные: базис решётки (состоит из линейно независимых векторов), параметр c , чаще всего (выбор параметра зависит от конкретной задачи). Последовательность действий:

В алгоритме  — округление по правилам математики. Процесс алгоритма, описанный на псевдокоде:

(выполнить процесс Грама — Шмидта без нормировки); всегда подразумевая

для если , то:

Обновить значения для ; конец условия; конец цикла;

иначе:

Обновить значения для ; для ;

конец условия; конец цикла.

Выходные данные: редуцированный базис: .

Вычислительная сложность На входе имеется базис -мерных векторов с .

Если вектора базиса состоят из целочисленных компонент, алгоритм приближает кратчайший почти ортогональный базис за полиномиальное время , где  — максимальная длина по евклидовой норме, то есть . Основной цикл алгоритма ЛЛЛ требует итераций и работает с числами длины . Так как на каждой итерации происходит обработка векторов длины , в итоге алгоритм требует арифметических операций. Применение наивных алгоритмов сложения и умножения целых чисел даёт в итоге битовых операций.

В случае, когда у решётки задан базис с рациональными компонентами, эти рациональные числа сначала необходимо преобразовать в целые путем умножения базисных векторов на знаменатели их компонент (множество знаменателей ограничено некоторым целым числом ). Но тогда операции будут производиться уже над целыми числами, не превышающими . В итоге будет максимум битовых операций. Для случая, когда решётка задана в , сложность алгоритма остается такой же, но увеличивается количество битовых операций. Так как в компьютерном представлении любое вещественное число заменяется рациональным в силу ограниченности битового представления, полученная оценка верна и для вещественных решёток.

В то же время для размерностей меньше чем 4 задача редукции базиса более эффективно решается алгоритмом Лагранжа.

Пример Пример, приводимый Вибом Босмой.

Пусть базис решётки (как подгруппа ), задан столбцами матрицы:

По ходу алгоритма получается следующее:

Выходные данные: базис, редуцированный методом Ленстры — Ленстры — Ловаса:

Применение Алгоритм часто применяется в рамках метода MIMO (пространственное кодирования сигнала) для декодирования сигналов, полученных несколькими антеннами, и в криптосистемах с открытым ключом: , RSA с конкретными настройками, NTRUEncrypt и так далее. Алгоритм может быть использован для нахождения целых решений в разных задачах теории чисел, в частности для поиска корней многочлена в целых числах.

В процессе атак на криптосистемы с открытым ключом (NTRU) алгоритм используется для поиска кратчайшего вектора решётки, так как алгоритм в результате находит целый набор кратчайших векторов.

В криптоанализе задача, так же как в случае с NTRU, сводится к поиску кратчайшего вектора базиса решётки, который находится за полиномиальное (от размерности базиса) время.

В задачах о ранце, в частности, для атаки на криптосистемe Меркла — Хеллмана алгоритм ЛЛЛ ищет редуцированный базис решётки.

Вариации и обобщения

Использование арифметики на числах с плавающей запятой вместо точного представления рациональных чисел может значительно ускорить работу ЛЛЛ-алгоритма ценой совсем небольших численных ошибок.

Реализации алгоритма Программно алгоритм реализован в следующем программном обеспечении: В fpLLL как автономная реализация; В GAP как функция LLLReducedBasis ; В как функция LLL в библиотеке LLLBases ; В как функции LLL и LLLGram ; В Maple как функция IntegerRelations[LLL] ; В Mathematica как функция LatticeReduce ; В Number Theory Library (NTL) как модуль LLL ; В как функция qflll ; В Pymatgen как функция analysis.get_lll_reduced_lattice ; В SageMath как метод LLL, реализованный в fpLLL и NTL.

Примечания

Литература

Категория:Криптография Категория:Теоретико-числовые алгоритмы Категория:Криптография на решётках