減少具有太多基向量的格基
假設我有一個基礎 $ B $ 一個 $ n $ 維晶格 $ L\subseteq\mathbb{Z}^n $ 和 $ B $ 有 $ n $ 向量。現在我再拿一個 $ v\in \mathbb{Z}^n\setminus L $ 我定義了一個新的格子 $ L’=L+\mathbb{Z}v $ . 向量集 $ B’:=B\cup{v} $ 生成 $ L’ $ ， 但是由於 $ L’ $ 是 $ n $ 維度，它的等級最多 $ n $ ， 所以 $ B’ $ 太大了。所以一定有其他的基礎產生 $ L’ $ . 我們如何從 $ B’ $ ?
我隱約記得讀過 LLL 可以做到這一點，但我不知道怎麼做。任何人都可以指出參考或提供快速論證/證明嗎？
儘管在評論中提到了 HNF，但寫下一個答案，所以這不是沒有答案的。
Hermite 範式是將發電機組簡化為基的標準方法。這意味著它是在格上計算多個操作的標準方法（很容易用基向量表示），例如
- $ L+L’ $ （你的例子是一個特例），或者
- $ L\cap L’ $ （這不太明顯，並且需要對偶性）。
請參閱這些筆記的簡單格子問題。
你評論了
看起來有效地計算 Hermite 範式並非易事……
這（有點）是真的，但重要的是遠非“難”。我從筆記中引用
想出一個算法來計算矩陣的 HNF 並不難，它只執行多項式運算。然而，這個問題的簡單解決方案可能會導致超多項式執行時間，因為中間計算中的數字很容易變得非常大。
連結的註釋包括多項式執行時間的 HNF 實現的虛擬碼（通過確保中間值保持有界）。它可能比 LLL 稍微複雜一些，但實際上並不復雜——這兩種算法都是我希望初級/高級本科生能夠在不費太多力氣的情況下實現的算法。
當然，您可以花費更多的精力來獲得更實際有效的東西。請參閱Pernet 和 Stein的這篇論文。由於 Stein 是 Sage CAS 的創始人，我想這與 Sage 實現的非常接近，至少在 2011 年左右。這種算法可能是您想到的那種“非平凡”算法。但另一方面，LLL 的有效實現同樣不平凡（幾年前我聽說 LLL 同時是多項式時間，並且可能很難在大格上實際執行，比如維度 1k+）。
值得一提的是，似乎確實有一些工作使用 LLL 作為子程序來計算 HNF，例如，參見this。