Lattice

給定一組向量，作為座標軸，嘗試畫出座標格線。整數倍位置，稱作「晶格」。

N個向量必須產生N維空間！向量不得共點、共線、共面、……，以免空間萎縮。

大家習慣令向量數值是整數，增進討論意義。

http://cseweb.ucsd.edu/classes/wi12/cse206A-a/
http://cseweb.ucsd.edu/classes/wi10/cse206a/
http://people.csail.mit.edu/vinodv/CS294/

Lattice Basis Reduction

https://en.wikipedia.org/wiki/Lattice_reduction

正交化。找到一組晶格向量，盡量互相垂直。

演算法（Lagrange's Algorithm）

兩個向量的演算法。教科書以此作為引言。

長向量投影到短向量。短向量乘上（四捨五入的）伸縮倍率，得到（偏移的）投影向量。長向量減去（偏移的）投影向量，變得（更加的）垂直。

不斷相互投影，直到投影之後長度大小關係不變。

可以視作輾轉相除法。

while (true)
{
    if (‖b₁‖ > ‖b₂‖) swap(b₁, b₂);  // b₂ is longer
    s = dot(b₁, b₂) / ‖b₁‖²;
    s = round(s);
    b₂ = b₂ - (s * b₁);             // b₂ project to b₁
    if (‖b₁‖ ≤ ‖b₂‖) break;         // b₂ is still longer
}

演算法（Hermite's Algorithm）

https://cs.uwaterloo.ca/~cbright/reports/latticealgs.pdf

演算法（Lenstra–Lenstra–Lovasz Algorithm）

https://math.pro/db/thread-1876-1-1.html

https://zhuanlan.zhihu.com/p/336840687

Shortest Vector Problem

https://en.wikipedia.org/wiki/Lattice_problem

找到長度最短的晶格向量。NP-hard。

利用Lattice Basis Reduction快速找到近似解。

Closest Vector Problem

針對一個非晶格向量，找到距離最近的晶格向量。NP-hard。

利用Shortest Vector Problem快速找到近似解。

Integer Relation

《Computational excursions in analysis and number theory》

演算法（Lenstra–Lenstra–Lovasz Algorithm）

演算法（HJLS Algorithm）

演算法（PSLQ Algorithm）

計算半平面交內部格點數目（Barvinok's Algorithm）

整數一次不等式組的解數量。

https://en.wikipedia.org/wiki/Minkowski's_theorem