Алгоритм базисного преобразования криптографической решётки

Алгоритм базисного преобразования криптографической решётки (LLL) — это алгоритм уменьшения решётки за полиномиальное время, изобретенный Арьеном Ленстра, Хендриком Ленстра и Ласлом Ловасом в 1982. Задан базис $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ с n-мерными натуральными координатами для рёшетки L, являющаяся дискретной подгруппой Rⁿ с $\ d\leq n$. Алгоритм LLL рассчитывает LLL-уменьшенный базис решётки за время

$O(d^{5}n\log ^{3}B)\,$

где$B$ является наибольшей длинной из $\mathbf {b} _{i}$ в соответствии с евклидовой нормой, то есть

$B=max\left(||\mathbf {b} _{1}||_{2},||\mathbf {b} _{2}||_{2},...,||\mathbf {b} _{d}||_{2}\right)$.

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

LLL reduction

Точное определение LLL-уменьшенного выглядят следующим образом : Учитывая базис

$\mathbf {B} =\{\mathbf {b} _{0},\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},$

определить его ортогональный базис процесса Грама – Шмидта

$\mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

и коэффициенты Грамма-Шмидта

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, for any $1\leq j<i\leq n$.

Тогда базис $B$ есть LLL-уменьшение, если существует параметр $\delta$ принадлежащий интервалу (0.25,1] такой, что имеют место следующий условия:

1. (уменьшенный размер) Для $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. По определению это свойство гарантирует уменьшение длины упорядоченного базиса.
2. (Условие Л. Ласло) k = 1,2,..,n $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$.

Здесь, оценивая величину параметра $\delta$,можно сделать вывод, насколько хорошо базис уменьшается. Большие значения параметра $\delta$ приводят к более сильным сокращениям основания. Первоначально А. Ленстра, Х. Ленстра и Л. Ловас продемонстрировали алгоритм LLL-уменьшения для $\delta ={\frac {3}{4}}$.Обратите внимание, что хотя LLL-уменьшение хорошо определено для $\delta =1$, сложность за полиномиальное время гарантируется только для параметра $\delta$ принадлежит $(0.25,1)$.

Алгоритм LLL вычисляет LLL-уменьшенные базисы. Не существует известного эффективного алгоритма для вычисления базиса, в котором векторы базисов настолько коротки, насколько это возможно, для решёток с размерами, превышающими 4. Однако базис с уменьшенной LLL является настолько коротким, насколько это возможно, в том смысле, что абсолютные границы $c_{i}>1$ таким образом, что первый базисный вектор не более чем в $c_{1}$ раз меньше самого короткого вектора в решётке, второй базисный вектор также находится в пределах $c_{2}$ второго последовательного минимума и так далее.

Алгоритм LLL

Описание данного алгоритма основано на( Hoffstein, Pipher & Silverman 2008 , теорема 6.68).

На вход:

$\triangleright$ базис решётки $b_{0},b_{1},\dots ,b_{n}\in Z^{m}$,

$\triangleright$ параметр $\delta$ , так что ${\frac {1}{4}}<\delta <1$, наиболее частая величина которого, есть $\delta ={\frac {3}{4}}$

Действия:

Выполните Грам-Шмидта, но не производите нормировку: $ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$ Определить $\scriptstyle \mu _{i,j}:={\frac {\langle b_{i},b_{j}^{*}\rangle }{\langle b_{j}^{*},b_{j}^{*}\rangle }}$, который всегда должен использовать самые актуальные значения $\scriptstyle b_{i},b_{j}^{*}$. Пусть $k=1$ пока $k\leq n$ делать для j от $k-1$ до 0 делать if $|\mu _{k,j}|>{\frac {1}{2}}$ do $b_{k}=b_{k}-\lfloor \mu _{k,j}\rceil b_{j}$ Обновить "орто" величины и и связанные с ними$\scriptstyle \mu _{i,j}$ по мере необходимости. (Собственный метод состоит в том, чтобы пересчитывать всегда $\scriptstyle ortho:=\mathrm {gramSchmidt} (\{b_{0},\dots ,b_{n}\})=\{b_{0}^{*},\dots ,b_{n}^{*}\}$ при любых изменениях $\scriptstyle b_{i}$ changes.) конец если конец для если $\langle b_{k}^{*},b_{k}^{*}\rangle \geq (\delta -(\mu _{k,k-1})^{2})\langle b_{k-1}^{*},b_{k-1}^{*}\rangle$ тогда $k=k+1$ иначе Поменять местами $\scriptstyle b_{k}$ и $\scriptstyle b_{k-1}$. Обновить "орто" величины и связанные с ними $\scriptstyle \mu _{i,j}$по мере необходимосит. $k=\max(k-1,1)$ конец если конец пока

На выход: LLL уменьшенный базис $b_{0},b_{1},\dots ,b_{n}$

Свойства LLL-уменьшенного базиса

Пусть $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}$ является $\delta$-LLL-уменьшенным базисом в решётке ${\mathcal {L}}$.Из определения LLL-уменьшенного базиса мы можем получить несколько других полезных свойств о{\ displaystyle \ mathbf {B}} $\mathbf {B}$.

1. Первый вектор в базе не может быть намного больше самого короткого ненулевого вектора :{\ displaystyle || \ mathbf {b} _ {1} || \ leq (2 / ({\ sqrt {4 \ delta -1}})) ^ {n-1} \ cdot \ lambda _ {1} ( {\ mathcal {L}})}: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})$. В частности, для $\delta =3/4$, это даёт$||\mathbf {b} _{1}||\leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})$.
2. Первый вектор в базисе также ограничен определителем решётки: $||\mathbf {b} _{1}||\leq (2/({\sqrt {4\delta -1}}))^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$. In particular, for $\delta =3/4$, в частности для $||\mathbf {b} _{1}||\leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$.
3. Произведение норм векторов в базисе не может быть намного больше, чем определитель решетки: пусть$\delta =3/4$, тогда Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \prod_{i=1}^n ||\mathbf{b}_i || \le 2^{n(n-1)/4} \cdot \det(\mathcal L)} .

Пример

Ниже приведён пример из W. Bosma.

На вход:

Пусть дан базис решётки $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in Z^{3}$,с заданными столбцами

${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$

Тогда по алгоритму LLL получаем следующее:

1. $b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix}},B_{1}=\langle b_{1}^{*},b_{1}^{*}\rangle ={\begin{bmatrix}1\\1\\1\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}=3$
2. Для $i=2$ делать:
   1. Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle j=1} положить $\mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1}}}={\frac {{\begin{bmatrix}-1\\0\\2\end{bmatrix}}{\begin{bmatrix}1\\1\\1\end{bmatrix}}}{3}}={\frac {1}{3}}\left(<{\frac {1}{2}}\right)$ а так же Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{2}^{*}= b_{2}- \mu_{2,1}b_{1}^{*}= \begin{bmatrix}-1\\0\\2\end{bmatrix}- \frac{1}{3}\begin{bmatrix}1\\1\\1\end{bmatrix}=\begin{bmatrix}\frac{-4}{3}\\\frac{-1}{3}\\\frac{5}{3} \end{bmatrix}.}
   2. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle B_{2}= \langle b_{2}^{*}, b_{2}^{*} \rangle = \begin{bmatrix}\frac{-4}{3}\\\frac{-1}{3}\\\frac{5}{3}\end{bmatrix} \begin{bmatrix}\frac{-4}{3}\\\frac{-1}{3}\\\frac{5}{3}\end{bmatrix}= \frac{14}{3}.}
3. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{k}:=2}
4. Здесь шаг 4 алгоритма LLL пропускается, поскольку свойство уменьшенного размера выполняется для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{2,1}}
5. Пока Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k \leq 3} делать
   1. Уменьшить длину Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{3} } , не забывая корректировать при этом Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,1}} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,2}} согласно подпрограмме сокращения в шаге 4: для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mid \mu_{3,1}\mid >\frac{1}{2}} ВЫПОЛНИТЬ подпрограмму сокращения RED(3,1):
      1. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle r = \lfloor 0.5 + \mu_{3,l} \rfloor =5} а также Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{3} = b_{3}- 5b_{1}= \begin{bmatrix}3\\5\\6\end{bmatrix}- \begin{bmatrix}5\\5\\5\end{bmatrix} =\begin{bmatrix}-2\\0\\1\end{bmatrix} }
      2. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,1}= \mu_{3,l} - r\mu_{1,1} = \frac{-1}{3}\left(< \frac{1}{2}\right) }
      3. Положить Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,1}= \mu_{3,1} - r= \frac{14}{3}-5= \frac{-1}{3}}

      Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mid \mu_{3,2}\mid >\frac{1}{2}} ВЫПОЛНИТЬ подпрограмму сокращения RED(3,2):

      1. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle r = \lfloor 0.5 + \mu_{3,2} \rfloor =1} and Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{3} = b_{3}- b_{2}= \begin{bmatrix}3\\5\\6\end{bmatrix}- \begin{bmatrix}-1\\0\\2\end{bmatrix} =\begin{bmatrix}4\\5\\4\end{bmatrix} }
      2. Положить Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,2}= \mu_{3,2} - r\mu_{2,2} = \frac{13}{14}-1= \frac{-1}{14}}
      3. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{3,2}= \mu_{3,2} - 1 = \frac{-1}{14}\left(< \frac{1}{2}\right) }
   2. Если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle B_{3} < \left(\frac{3}{4}- \mu_{3,2}^2\right)B_{2} } , то
      1. Заменить Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{3}} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{2}}
      2. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k := 2}

Применить SWAP, продолжить алгоритм с базой решетки, которая задается столбцами

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{bmatrix} 1 & 4& -1\\ 1 & 5 & 0\\ 1 & 4 & 2 \end{bmatrix} }

Реализовать алгоритм шагов снова.

1. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{1}^{*}= b_{1}= \begin{bmatrix}1\\1\\1\end{bmatrix}, B_{1}= 3}
2. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{2,1}= \frac{\langle b_{2}, b_{1}^{*} \rangle}{B_{1}}= \frac{\begin{bmatrix}4\\5\\4\end{bmatrix} \begin{bmatrix}1\\1\\1\end{bmatrix}}{3} =\frac{13}{3}\left(>\frac{1}{2}\right)}
3. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{2}^{*}= b_{2}- \mu_{2,1}b_{1}^{*}= \begin{bmatrix}4\\5\\4\end{bmatrix}- \frac{13}{3}\begin{bmatrix}1\\1\\1\end{bmatrix} =\begin{bmatrix}\frac{-1}{3}\\\frac{2}{3}\\\frac{-1}{3}\end{bmatrix}} .
4. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle B_{2}= \langle b_{2}^{*}, b_{2}^{*} \rangle = \frac{2}{3}} .
5. Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mid \mu_{2,1}\mid >\frac{1}{2}} ВЫПОЛНИТЬ подпрограмму сокращения RED(2,1):
   1. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle r = \lfloor 0.5 + \mu_{2,l} \rfloor =4} and Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{2} = b_{2}- 4b_{1}= \begin{bmatrix}4\\5\\4\end{bmatrix}- \begin{bmatrix}4\\4\\4\end{bmatrix}=\begin{bmatrix}0\\1\\0\end{bmatrix} }
   2. Положить Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mu_{2,1}= \mu_{2,1} - 4\mu_{1,1}= \frac{13}{3}- 4= \frac{1}{3}\left(< \frac{1}{2}\right)}
6. Если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle B_{2} < \left(\frac{3}{4}- \mu_{2,1}^2\right)B_{1} } , то
7. Заменить Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{2}} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_{1}}

ВЫХОД: LLL уменьшенный базис

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{bmatrix} 0 & 1& -1\\ 1 & 0 & 0\\ 0 & 1 & 2 \end{bmatrix} }

Использование алгоритма LLL

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

В частности, алгоритм LLL образует ядро одного из алгоритмов целочисленных отношений . Например, если считается, что r = 1.618034 является (слегка округленным) корнем неизвестного квадратного уравнения с целыми коэффициентами, можно применить LLL-сокращение к решетке в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle R^4} натянутый на Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [1,0,0,10000r^2], [0,1,0,10000r],} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [0,0,1,10000]} . Первый вектор в сокращенном базисе будет представлять собой целочисленную линейную комбинацию этих трех, поэтому обязательно имеет вид Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [a,b,c,10000(ar^2+br+c)]} ; но такой вектор «короткий», только если a, b, c малы и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle ar^2+br+c} ещё меньше. Таким образом, первые три записи этого короткого вектора, вероятно, будут коэффициентами целочисленного квадратичного полинома, у которого r является корнем. В этом примере алгоритм LLL находит самый короткий вектор как [1, -1, -1, 0.00025], действительно Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle x^2-x-1} имеет корень, равный золотому сечению , 1.6180339887....

Другие области применения алгоритма LLL

LLL применятеся в

• Arageli как функция lll_reduction_int
• fpLLL как отдельная реализация
• GAP как функция LLLReducedBasis
• Macaulay2 как функция LLL в пакете LLLBases
• Magma как функции LLL and LLLGram (используя грамм-матрицу)
• Maple как функция IntegerRelations[LLL]
• Mathematicaкак функция LatticeReduce
• Number Theory Library (NTL) как функцияLLL
• PARI/GP как функцияqflll
• Pymatgen как функция analysis.get_lll_reduced_lattice
• SageMath как метод LLL driven by fpLLL and NTL

См. также

• Coppersmith method

Ссылки

• Napias, Huguette A generalization of the LLL algorithm over euclidean rings or ordersангл. // J. The. Nombr. Bordeaux : journal. — 1996. — том 8. — С. 387—396. — DOI:10.5802/jtnb.176
• Cohen, Henri A course in computational algebraic number theory. — Springer, 2000. — Т. 138. — (GTM). — ISBN 3-540-55640-0.
• Borwein, Peter^[en] Computational Excursions in Analysis and Number Theory. — 2002. — ISBN 0-387-95444-9.
• Luk, Franklin T.; Qiao, Sanzheng A pivoted LLL algorithmнеопр. // Lin. Alg. Appl.. — 2011. — том 434. — № 11. — С. 2296—2307. — DOI:10.1016/j.laa.2010.04.003
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. An Introduction to Mathematical Cryptography. — Springer, 2008. — ISBN 978-0-387-77993-5.