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

Алгоритм Ленстры — Ленстры — Ловаса (ЛЛЛ-алгоритм, 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.  ,   и  
    3.  , поэтому   и  , тогда   и  
  2. При   имеем   и  , поэтому переходим к следующему шагу.
  3. При   имеем:
    1.  , значит  , теперь  
    2.  , значит  , теперь  
    3.  , поэтому   и   меняются местами.
  4. Теперь возвращаемся к шагу 1, при этом промежуточная матрица   имеет вид  

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

 

Применение править

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

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

В криптоанализе RSA c малой CRT-экспонентой[en] задача, так же как в случае с NTRU, сводится к поиску кратчайшего вектора базиса решётки, который находится за полиномиальное (от размерности базиса) время[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. Архивировано 20 сентября 2015 года.
  4. 1 2 Xinyue, Deng. An Introduction to LLL Algorithm (англ.) // Massachusetts Institute of Technology. — P. 9—10. Архивировано 8 декабря 2019 года.
  5. Чередник И. В. Неотрицательный базис решетки // 3-е изд. — Дискрет. матем., 2014. — Т. 26. — С. 127—135.
  6. 1 2 Regev, Oded. Lattices in Computer Science: LLL Algorithm // New York University. Архивировано 20 марта 2021 года.
  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. Архивировано 8 мая 2019 года.
  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. Архивировано 6 мая 2021 года.
  12. Abderrahmane, Nitaj. Cryptanalysis of NTRU with two public keys // International Association for Cryptologic Research. — Caen, France. Архивировано 21 декабря 2019 года.
  13. Bleichenbacher, Daniel and May, Alexander. New Attacks on RSA with Small Secret CRT-Exponents // International Association for Cryptologic Research. — Darmstadt, Germany. Архивировано 24 июня 2021 года.
  14. Liu, Jiayang, Bi, Jingguo and Xu, Songyan. An Improved Attack on the Basic Merkle–Hellman Knapsack Cryptosystems // IEEE. — Beijing 100084, China. Архивировано 17 июня 2021 года.
  15. The LLL Algorithm, 2010, 4 Progress on LLL and Lattice Reduction.
  16. The FPLLL development team. FPLLL, a lattice reduction library. — 2016. Архивировано 17 февраля 2020 года.
  17. Integral matrices and lattices. GAP. Дата обращения: 10 декабря 2019. Архивировано 19 декабря 2019 года.
  18. LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases). Macaulay2. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
  19. LLL Reduction. Magma. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
  20. IntegerRelations/LLL. Maple. Дата обращения: 10 декабря 2019. Архивировано 18 сентября 2020 года.
  21. LatticeReduce. Wolfram Language Documentation. Дата обращения: 10 декабря 2019. Архивировано 10 декабря 2019 года.
  22. MODULE:LLL. NTL. Дата обращения: 10 декабря 2019. Архивировано 17 августа 2018 года.
  23. Vectors, matrices, linear algebra and sets. PARI/GP. Дата обращения: 10 декабря 2019. Архивировано 18 декабря 2019 года.
  24. pymatgen.core.lattice module. pymatgen. Дата обращения: 27 декабря 2019. Архивировано 18 декабря 2019 года.
  25. Dense matrices over the integer ring. sage. Дата обращения: 18 декабря 2019. Архивировано 6 мая 2021 года.

Литература править