Ленстр-Ленстр-Ловас (LLL) алгоритм редукции решетка основы является многочленом времени сокращения решетки алгоритма изобретен Арьны Ленстрами , Хендрик Ленстрами и Ловасом в 1982 г. [1] Учитывая базис с n -мерными целочисленными координатами для решетки L (дискретной подгруппы в R n ) с, алгоритм LLL вычисляет LLL-редуцированный (короткий, почти ортогональный ) базис решетки за время
где самая большая длина по евклидовой норме, т. е. . [2] [3]
Первоначальные приложения должны были дать алгоритмы полиномиального времени для факторизации многочленов с рациональными коэффициентами , для поиска одновременных рациональных приближений к действительным числам и для решения задачи целочисленного линейного программирования в фиксированных размерах.
Снижение LLL
Точное определение LLL-редукции выглядит следующим образом: Учитывая базис
определить его ортогональный базис процесса Грама – Шмидта
и коэффициенты Грама-Шмидта
- , для любой .
Тогда основа LLL-редуцируется, если существует параметр в (0.25,1] такая, что выполняется следующее:
- (размер уменьшен) Для . По определению, это свойство гарантирует сокращение длины упорядоченного базиса.
- (Условие Ловаса) Для k = 2,3, .., n .
Здесь, оценивая значение по параметру, можно сделать вывод, насколько хорошо редуцируется базис. Высшие ценностиприводят к более сильным сокращениям основания. Первоначально А. Ленстра, Х. Ленстра и Л. Ловас продемонстрировали алгоритм LLL-редукции для. Обратите внимание, что хотя LLL-редукция хорошо определена для, полиномиальная сложность гарантируется только для в .
Алгоритм LLL вычисляет LLL-сокращенные базы. Не существует известного эффективного алгоритма для вычисления базиса, в котором базисные векторы были бы как можно короче для решеток размерностей больше 4. [4] Однако LLL-редуцированный базис почти как можно короче в том смысле, что существует абсолютные границы такой, что первый базисный вектор не превышает раз длиннее кратчайшего вектора в решетке, второй базисный вектор также находится в пределах второго последующего минимума и т. д.
Приложения
Первым успешным применением алгоритма LLL было его использование Эндрю Одлыжко и Германом те Риле для опровержения гипотезы Мертенса . [5]
Алгоритм LLL нашел множество других приложений в алгоритмах обнаружения MIMO [6] и криптоанализе схем шифрования с открытым ключом : ранцевых криптосистемах , RSA с определенными настройками, NTRUEncrypt и т. Д. Алгоритм можно использовать для поиска целочисленных решений многих задач. [7]
В частности, алгоритм LLL составляет ядро одного из алгоритмов целочисленных отношений . Например, если предполагается, что r = 1.618034 является (слегка округленным) корнем неизвестного квадратного уравнения с целыми коэффициентами, можно применить LLL-редукцию к решетке в охватывает а также . Первый вектор в приведенном базисе будет целочисленной линейной комбинацией этих трех, таким образом обязательно имеющей форму; но такой вектор будет «коротким», только если a , b , c малы иеще меньше. Таким образом, первые три элемента этого короткого вектора, вероятно, будут коэффициентами целочисленного квадратичного многочлена, имеющего r в качестве корня. В этом примере алгоритм LLL находит самый короткий вектор как [1, -1, -1, 0,00025] и действительноимеет корень, равный золотому сечению , 1.6180339887 ....
Свойства LLL-редуцированного базиса
Позволять быть -LLL-приведенный базис решетки . Из определения LLL-редуцированного базиса мы можем вывести несколько других полезных свойств, касающихся.
- Первый вектор в базисе не может быть намного больше кратчайшего ненулевого вектора :. В частности, для, это дает . [8]
- Первый вектор в базисе также ограничен определителем решетки: . В частности, для, это дает .
- Произведение норм векторов в базисе не может быть намного больше определителя решетки: пусть , тогда .
Псевдокод алгоритма LLL
Следующее описание основано на ( Hoffstein, Pipher & Silverman 2008 , теорема 6.68) с исправлениями , внесенными в список опечаток. [9]
ВВЕДИТЕ основание решетки параметр с участием , чаще всего ПРОЦЕДУРА и не нормализовать используя самые актуальные значения а также пока делать для из к делать если тогда Обновлять и связанные по мере необходимости. (Наивный метод - пересчитать в любое время изменения: ) конец, если конец, если тогда еще поменять а также Обновлять и связанные по мере необходимости. конец, если конец, пока возврат LLL сокращает базу ВЫВОД сокращенной базы
Примеры
Пример из
Пусть базис решетки , задаваемые столбцами
то приведенный базис
- ,
который уменьшен в размере, удовлетворяет условию Ловаса и, следовательно, является LLL-уменьшенным, как описано выше. См. W. Bosma. [10] для получения подробной информации о процессе восстановления.
Пример из
Аналогичным образом, для базиса комплексных целых чисел, заданных столбцами матрицы ниже,
- ,
тогда столбцы матрицы ниже дают LLL-сокращенный базис.
- .
Реализации
LLL реализован в
- Арагели как функция
lll_reduction_int
- fpLLL как отдельная реализация
- GAP как функция
LLLReducedBasis
- Macaulay2 как функция
LLL
в пакетеLLLBases
- Магма как функции
LLL
иLLLGram
(взяв матрицу грамма) - Клен как функция
IntegerRelations[LLL]
- Mathematica как функция
LatticeReduce
- Библиотека теории чисел (NTL) как функция
LLL
- PARI / GP как функция
qflll
- Пиматген как функция
analysis.get_lll_reduced_lattice
- SageMath как метод,
LLL
управляемый fpLLL и NTL - Изабель / ХОЛ в записи «Архив официальных доказательств»
LLL_Basis_Reduction
. Этот код экспортируется в эффективно исполняемый Haskell. [11]
Смотрите также
- Метод медника
Заметки
- ^ Ленстра, AK ; Ленстра, Х.В., младший ; Ловас, Л. (1982). «Факторинг многочленов с рациональными коэффициентами». Mathematische Annalen . 261 (4): 515–534. CiteSeerX 10.1.1.310.318 . DOI : 10.1007 / BF01457454 . hdl : 1887/3810 . Руководство по ремонту 0682664 . S2CID 5701340 .
- ^ Гэлбрейт, Стивен (2012). «глава 17» . Математика криптографии с открытым ключом .
- ^ Nguyen, Phong Q .; Стеле, Дэмиен (сентябрь 2009 г.). «Алгоритм LLL с квадратичной сложностью» . SIAM J. Comput . 39 (3): 874–903. DOI : 10.1137 / 070705702 . Дата обращения 3 июня 2019 .
- ^ Nguyen, Phong Q .; Стеле, Дамьен (1 октября 2009 г.). "Возвращение к низкоразмерной редукции базиса решетки". ACM-транзакции по алгоритмам . 5 (4): 1–48. DOI : 10.1145 / 1597036.1597050 . S2CID 10583820 .
- ^ Одлызко, Андрей; te Reile, Герман Дж. Дж. «Опровержение гипотезы Мертенса» (PDF) . Journal für die reine und angewandte Mathematik . 357 : 138–160. DOI : 10,1515 / crll.1985.357.138 . S2CID 13016831 . Проверено 27 января 2020 года .
- ^ Шахабуддин, Шахриар и др., «Настраиваемый мультипроцессор с уменьшением решетки для обнаружения MIMO», в препринте Arxiv, январь 2015 г.
- ^ Д. Саймон (2007). «Избранные приложения LLL в теории чисел» (PDF) . Конференция LLL + 25 . Кан, Франция.
- ^ Регев, Одед. "Решетки в информатике: алгоритм LLL" (PDF) . Нью-Йоркский университет . Дата обращения 1 февраля 2019 .
- ^ Сильверман, Джозеф. «Введение в исправления математической криптографии» (PDF) . Кафедра математики Университета Брауна . Дата обращения 5 мая 2015 .
- ^ Босма, Виб. «4. LLL» (PDF) . Конспект лекций . Проверено 28 февраля 2010 года .
- ^ Дивасон, Хосе (2018). «Формализация алгоритма редукции базиса LLL» . Документ конференции . Конспект лекций по информатике. 10895 : 160–177. DOI : 10.1007 / 978-3-319-94821-8_10 . ISBN 978-3-319-94820-1. Дата обращения 3 мая 2020 .
Рекомендации
- Напиас, Хугетт (1996). «Обобщение алгоритма LLL над евклидовыми кольцами или порядками» . Журнал де Теори де Номбр де Бордо . 8 (2): 387–396. DOI : 10,5802 / jtnb.176 .
- Коэн, Анри (2000). Курс вычислительной алгебраической теории чисел . GTM. 138 . Springer. ISBN 3-540-55640-0.
- Борвейн, Питер (2002). Вычислительные экскурсии по анализу и теории чисел . ISBN 0-387-95444-9.
- Luk, Франклин Т .; Цяо, Саньчжэн (2011). «Поворотный алгоритм LLL» . Линейная алгебра и ее приложения . 434 (11): 2296–2307. DOI : 10.1016 / j.laa.2010.04.003 .
- Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, JH (2008). Введение в математическую криптографию . Springer. ISBN 978-0-387-77993-5.