什麼是最有效的格問題求解算法？

我最近對後量子密碼學非常感興趣，特別是基於格的密碼學。在這篇文章中，沒有任何量子算法可以比傳統電腦更好地解決晶格問題。

然而，存在理論上可以解決晶格問題的算法，儘管速度很慢。

我想自己研究這些算法中的一種或多種，以幫助我更好地理解格密碼學和一般格。

那麼，什麼是最有效的格問題求解算法，為什麼它如此高效？

你想要的可能是一個格子縮減算法。

格密碼學通常依賴於最近向量問題 (CVP) 或最短向量問題 (SVP)。解決這些問題涉及到Lenstra–Lenstra–Lovász 格基縮減算法，或 LLL。該算法是典型的晶格縮減算法，可能是您正在尋找的。該算法在內部被其他算法使用，例如Babai 的CVP 最近平面算法。

請注意，LLL 算法無法減少更高維度的格，這是實際格密碼學的情況。相反，需要不同的算法，例如 NTRU 的BKZ 2.0。然而，為了了解晶格約簡，了解 LLL 就足夠了。

引用自：https://crypto.stackexchange.com/questions/71492