Lattice-Crypto
驗證點是否在晶格內
我想知道是否有一個多項式時間算法，給定一個格子 $ \Lambda $ 有依據 $ \mathbf{B} $ 和一點 $ x $ 在太空中，它會告訴你是否 $ x $ 在 $ \Lambda $ 或不！
如果你計算一個對偶格子的底，然後檢查點和向量的內積，如果這個底都是整數：要計算這個底，它是 $ \mathbf{B}(\mathbf{B}^{T}\mathbf{B})^{-1} $ :
使用 Hermite Normal Form 計算有一個相對簡單的方法。本質上，如果 $ \mathbf{B} = [b_1,\dots, b_k] $ ，然後檢查是否： $$ \mathsf{HNF}([b_1,\dots,b_k]) = \mathsf{HNF}([b_1,\dots,b_k, x]) $$ 這推廣到檢查格子的情況 $ \mathcal{L}(A) $ 是一個子格子 $ \mathcal{L}(B) $ — 只需檢查是否 $ \mathsf{HNF}(B) = \mathsf{HNF}(B\cup A) $ ， 在哪裡 $ B \cup A $ 是所有基向量的“並集”。
HNF 可用於解決晶格上的各種“代數”問題，例如參見這些註釋的第 4 節。一般來說，格上的“代數”問題很容易（通常通過 HNF），而“幾何”問題則很難。Ajtai 實際上已經寫了一篇論文，通過一個明確的猜想來表述這一點（參見這篇論文，這是他最初猜想的擴展）。