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

Алгоритм базисного преобразования криптографической решётки (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-уменьшение хорошо определено для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \delta = 1} , сложность за полиномиальное время гарантируется только для параметра Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \delta} принадлежит $(0.25,1)$.

Алгоритм LLL вычисляет LLL-уменьшенные базисы. Не существует известного эффективного алгоритма для вычисления базиса, в котором векторы базисов настолько коротки, насколько это возможно, для решёток с размерами, превышающими 4. Однако базис с уменьшенной LLL является настолько коротким, насколько это возможно, в том смысле, что абсолютные границы Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle c_i > 1} таким образом, что первый базисный вектор не более чем в Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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 Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_k = b_k - \lfloor \mu_{k,j} \rceil b_{j}} Обновить "орто" величины и и связанные с нимиНевозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle \mu_{i,j}} по мере необходимости. (Собственный метод состоит в том, чтобы пересчитывать всегда Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle ortho := \mathrm{gramSchmidt}(\{b_0, \dots, b_n\}) = \{ b_0^*, \dots, b_n^* \}} при любых изменениях Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle b_i} changes.) конец если конец для если Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \langle b_k^*, b_k^*\rangle \ge (\delta - (\mu_{k,k-1})^2)\langle b_{k-1}^*, b_{k-1}^*\rangle} тогда Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k = k + 1} иначе Поменять местами Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle b_k} и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle b_{k-1}} . Обновить "орто" величины и связанные с ними Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \scriptstyle \mu_{i,j}} по мере необходимосит. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k = \max(k-1,1)} конец если конец пока

На выход: LLL уменьшенный базис Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle b_0, b_1, \dots, b_n }

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

Пусть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \}} является Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \delta} -LLL-уменьшенным базисом в решётке Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathcal L} .Из определения LLL-уменьшенного базиса мы можем получить несколько других полезных свойств о{\ displaystyle \ mathbf {B}} Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{B}} .

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

На вход:

Пусть дан базис решётки Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in Z^{3}} ,с заданными столбцами

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

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

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}= \langle b_{1}^{*}, b_{1}^{*} \rangle = \begin{bmatrix}1\\1\\1\end{bmatrix} \begin{bmatrix}1\\1\\1\end{bmatrix} = 3}
2. Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle i=2} делать:
   1. Для Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle j=1} положить Невозможно разобрать выражение (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}-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.