了解 Unique-SVP 和 Kannan 的嵌入
我正在嘗試了解 Kannan 嵌入技術。但我對**B’**的形成以及在該基礎內找到短向量感到困惑。算法中的這個基矩陣是怎麼產生格子的呢？或者更具體地說，為什麼 uSVP 實例由向量（e ^T）和整數（M）組成？
謝謝。
矩陣的列 $ B’ $ 生成格子 $ \Lambda’={\mathbf v’\in\mathbb Z^{n+1}} $ 第一個在哪裡 $ n $ 條目形成一個向量，該向量不同於 $ \Lambda $ 通過一些倍數 $ \mathbf e $ 最後一個條目是相同的倍數 $ M $ . 我們還需要一些保證 $ \mathbf e $ 比最短向量短 $ \Lambda $ 一定數量，那 $ \mathbf {As} $ 是最接近的向量 $ \mathbf b $ .
$ M $ 不一定是整數，而是某個值，例如 $ M=||\mathbf e|| $ 當我們知道 $ ||\mathbf e||<\lambda_1/2 $ 在哪裡 $ \lambda_1 $ 是最短向量的長度 $ \Lambda $ . 由此可知，向量 $ (\mathbf e, M)^T $ 最多有長度 $ \sqrt 2M<\lambda_1/\sqrt 2 $ . 這比任何形式的向量都短 $ (\mathbf x, 0)^T $ 對應於一個向量 $ \mathbf x $ 的 $ \Lambda $ 至少長度也是如此 $ \lambda_1 $ . 它比任何其他形式的向量都短 $ (\mathbf y, M)^T $ 通過最近向量的定義。它也比任何形式的向量短 $ (\mathbf z, kM)^T $ 對於任何 $ |k|\ge 2 $ 因為這樣的向量至少有長度 $ |k|M>\sqrt 2 M $ 基於最終組件。它遵循 $ (\mathbf e, M) $ 是唯一的最短向量 $ \Lambda’ $ .