EN | ZH

# 格基规约算法¶

## Lenstra–Lenstra–Lovasz¶

### 基本介绍¶

LLL 算法就是在格上找到一组基，满足如下效果

### 简单应用¶

A = \left[ \begin{matrix} 1 & 0 & 0 & \cdots & 0 & ca_1 \\ 0 & 1 & 0 & \cdots & 0 & c a_2 \\ 0 & 0 & 1 & \cdots & 0 & c a_3 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots & 1 & c a_n \\ \end{matrix} \right]

$det(L)=\sqrt{AA^T}$

A = \left[ \begin{matrix} 1 & 0 & 0 & \cdots & 0 & a_1 \\ 0 & 1 & 0 & \cdots & 0 & a_2 \\ 0 & 0 & 1 & \cdots & 0 & a_3 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots & 1 & a_n \\ \end{matrix} \right]

AA^T = \left[ \begin{matrix} 1+a_1^2 & a_1a_2 & a_1a_3 & \cdots & a_1a_n \\ a_2a_1 & 1+a_2^2 & a_2a_3 & \cdots & a_2a_n \\ a_3a_1 & a_3a_2 & 1+a_3^2 & \cdots & a_3a_n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_na_1 & a_na_2 &a_na_3 & \cdots & 1+a_n^2 \\ \end{matrix} \right]

$\sqrt{1+\sum\limits_{i=1}^n\alpha_i^2}$

$||b_1|| \leq 2^{\frac{n-1}{4}} (1+\sum\limits_{i=1}^n\alpha_i^2)^{\frac{1}{2(n+1)}}$

$||b_1|| \leq 2^{\frac{n-1}{4}}*k$

k 比较小。此外，$b_1$ 又是原向量的线性组合，那么

$b_1[n]=\sum\limits_{i=1}^{n}m_ic*a_i=c\sum\limits_{i=1}^{n}m_i*a_i$

## 参考¶

• Survey: Lattice Reduction Attacks on RSA