lll-rs功能尚不完善，应被视为实验性。愿意使用稳定且经过实战检验的库的用户应考虑使用fplll代替fplll。

格基约简

一个格Λ是某个向量空间E的离散子群。一个典型例子（例如，参见3）是E = ℝⁿ，

X ∊ Λ<=>X=l_1*b_1+ ... +l_n*b_n，其中(l_i) 属于ℤ，且(b_i) 属于属于ℝ。

格是数学上广泛研究的结构，我们可以在其上提出一些有用的问题4。其中一些问题在已知格的“良好基”时更容易解决。相反，如果只知道“不良基”，则很难解决这些问题。

简单来说，LLL算法提供了一种“良好的基础”；它通过在“不良基础”上执行（变体）圆整Gram-Schimdt正交化来实现这一点。令人惊讶的是，这个算法在多项式时间内运行，这使得它能够高效地解决多个格问题。

LLL的应用包括

• 基于格的密码分析（例如NTRU）
• 伪随机数生成器的密码分析（例如LCG和截断LCG）
• RSA的密码分析（例如Coppersmith攻击5）
• 基于背包的密码分析
• 寻找数学反例（例如Merten的猜想）
• 寻找有理系数多项式的根
• 寻找常数之间的整数关系
• 纠错码的解码

示例

// Init the matrix with Integer
let mut basis: Matrix<BigVector> = Matrix::init(3, 4);

// Populate the matix
basis[0] = BigVector::from_vector(vec![
    Integer::from(1) << 100000,
    Integer::from(0),
    Integer::from(0),
    Integer::from(1345),
]);
basis[1] = BigVector::from_vector(vec![
    Integer::from(0),
    Integer::from(1),
    Integer::from(0),
    Integer::from(35),
]);
basis[2] = BigVector::from_vector(vec![
    Integer::from(0),
    Integer::from(0),
    Integer::from(1),
    Integer::from(154),
]);

// Perfom the LLL basis reduction
biglll::lattice_reduce(&mut basis);

// OR
// Perfom the L2 basis reduction
// Specify the delta and eta coefficient for the reduction
bigl2::lattice_reduce(&mut basis, 0.5005, 0.999);

参考文献和文档

[LLL82] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz. 有理系数多项式的分解. Math. Ann., 261: 515–534 (1982)

• https://openaccess.leidenuniv.nl/bitstream/handle/1887/3810/346_050.pdf
• https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm
• https://perso.ens-lyon.fr/damien.stehle/downloads/LLL25.pdf
• https://en.wikipedia.org/wiki/Lattice_(group)
• https://en.wikipedia.org/wiki/Lattice_problem
• https://en.wikipedia.org/wiki/Coppersmith%27s_attack