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

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

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

История[править | править код]

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

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

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

Редукция базиса[править | править код]

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

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

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

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

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

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

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

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


Свойства редуцированного базиса[править | править код]

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

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

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

Алгоритм[править | править код]

Входные данные[7]:

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

Последовательность действий[4]:

  1. Сначала создается копия исходного базиса, которая ортогонализуется для того, чтобы по ходу алгоритма текущий базис сравнивался с полученной копией на предмет ортогональности ().
  2. Если какой-либо коэффициент Грама — Шмидта ) по модулю больше , то проекция одного из векторов текущего базиса на вектор ортогонализованного базиса с другим номером составляет больше половины . Это говорит о том, что необходимо вычесть из вектора вектор , домноженный на округленный (округление нужно, так как вектор решётки остается вектором этой же решётки только при умножении на целое число, что следует из её определения). Тогда станет меньше , так как теперь проекция на будет меньше половины . Таким образом производится проверка соответствию 1-му условию из определения ЛЛЛ-редуцированного базиса.
  3. Пересчитывается для .
  4. Для проверяется 2-е условие, введенное авторами алгоритма как определение ЛЛЛ-редуцированного базиса[1]. Если условие не выполнено, то индексы проверяемых векторов меняются местами. И условие проверяется снова для того же вектора (уже с новым индексом).
  5. Пересчитываются для и для
  6. Если остался какой-либо , по модулю превышающий (уже с другим ), то надо вернуться к пункту 2.
  7. Когда все условия проверены и сделаны изменения, алгоритм завершает работу.

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

  ortho  
  (выполнить процесс Грама — Шмидта без нормировки);
  определить , всегда подразумевая наиболее актуальные значения 
  присвоить 
  пока :
    для j от  до 0:
       если , то:
          ;
          Обновить значения  для ;
       конец условия;
    конец цикла;
    если , то:
       
    иначе:
       поменять  и  местами;
       Обновить значения  для ;  для ;
       ;
    конец условия;
  конец цикла.

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

Вычислительная сложность[править | править код]

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

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

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

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

Пример[править | править код]

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

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

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

  1. Процесс ортогонализации Грама-Шмидта
    1. , и
    2. , поэтому и , тогда и
  2. При имеем и , поэтому переходим к следующему шагу.
  3. При имеем:
    1. , значит , теперь
    2. , значит , теперь
    3. , поэтому и меняются местами.
  4. Теперь возвращаемся к шагу 1, при этом промежуточная матрица имеет вид

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

Применение[править | править код]

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

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

В криптоанализе RSA c малой CRT-экспонентой[en] задача, так же как в случае с NRTU, сводится к поиску кратчайшего вектора базиса решётки, который находится за полиномиальное (от размерности базиса) время[13].

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

Вариации и обобщения[править | править код]

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

Реализации алгоритма[править | править код]

Программно алгоритм реализован в следующем программном обеспечении:

Примечания[править | править код]

  1. 1 2 3 4 A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Factoring polynomials with rational coefficients // Mathematische Annalen. — 1982. — С. 515—534. — ISSN 4. — doi:10.1007/BF01457454.
  2. 1 2 The LLL Algorithm, 2010, 1 The History of the LLL-Algorithm.
  3. 1 2 3 4 5 6 7 Galbraith, Steven. 17. Lattice Reduction // Mathematics of Public Key Cryptography (англ.). — 2012.
  4. 1 2 Xinyue, Deng. An Introduction to LLL Algorithm (англ.) // Massachusetts Institute of Technology. — P. 9—10.
  5. Чередник И. В. Неотрицательный базис решетки (рус.) // 3-е изд. — Дискрет. матем., 2014. — Т. 26. — С. 127—135.
  6. 1 2 Regev, Oded. Lattices in Computer Science: LLL Algorithm // New York University.
  7. 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography (англ.). — Springer (англ.), 2008. — P. 411. — ISBN 978-0-387-77993-5.
  8. Nguyen, Phong Q., Stehlé, Damien. Low-dimensional lattice basis reduction revisited (англ.) // ACM Transactions on Algorithms. — P. 1–48. — doi:10.1145/1597036.1597050.
  9. Bosma, Wieb. 4. LLL // Computer Algebra. — 2007.
  10. Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. A customized lattice reduction multiprocessor for MIMO detection // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). — 2015. — arXiv:1501.04860. — doi:10.1109/ISCAS.2015.7169312.
  11. D. Simon. Selected applications of LLL in number theory // LLL+25 Conference. — Caen, France.
  12. Abderrahmane, Nitaj. Cryptanalysis of NTRU with two public keys // International Association for Cryptologic Research. — Caen, France.
  13. Bleichenbacher, Daniel and May, Alexander. New Attacks on RSA with Small Secret CRT-Exponents // International Association for Cryptologic Research. — Darmstadt, Germany.
  14. Liu, Jiayang, Bi, Jingguo and Xu, Songyan. An Improved Attack on the Basic Merkle–Hellman Knapsack Cryptosystems // IEEE. — Beijing 100084, China.
  15. The LLL Algorithm, 2010, 4 Progress on LLL and Lattice Reduction.
  16. The FPLLL development team. FPLLL, a lattice reduction library. — 2016.
  17. Integral matrices and lattices. GAP.
  18. LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases). Macaulay2.
  19. LLL Reduction. Magma.
  20. IntegerRelations/LLL. Maple.
  21. LatticeReduce. Wolfram Language Documentation.
  22. MODULE:LLL. NTL.
  23. Vectors, matrices, linear algebra and sets. PARI/GP.
  24. pymatgen.core.lattice module. pymatgen.
  25. Dense matrices over the integer ring. sage.

Литература[править | править код]