Sage 中的格：從基 S 生成矩陣 A，使得 AS = 0 (mod q)
在 Sage 中有一個函式：gen_lattice() 可以生成一個基$$ S \in \mathbb{Z}^{m \times m}_q $$格子的$$ \Lambda^\bot_q(A) $$， 在哪裡$$ A \in \mathbb{Z}^{n \times m}_q $$是隨機的。
所以，$$ AS = 0 \pmod q. $$
問題是：有沒有什麼方法可以進一步得到一個矩陣$$ A \in \mathbb{Z}^{n \times m}_q. $$
（即 AP09 中的 TrapGen 算法。）
是的，這相對簡單。首先，Sage 似乎內置了這個（請參閱dual flag，雖然我沒有測試它）。我將描述繼續的“數學”方式，因為我認為它在概念上更有用。
對於有基礎的格子 $ B $ ，眾所周知（見定理 2），對偶有基：
$$ D = B (B^t B)^{-1} $$
隨之而來的是以下程式碼片段：
S = sage.crypto.gen_lattice() D = S * (S.T * S).inverse()將產生所需的基礎。請注意，基通常不是整數矩陣 — 對於（隨機）矩陣 $ S $ 在 的執行中生成
sage.crypto.gen_lattice()，我知道雙重基礎是：[ 1/11 0 0 0 -4/11 -3/11 2/11 0] [ 0 1/11 0 0 -5/11 1/11 -3/11 0] [ 0 0 1/11 0 0 5/11 -4/11 -5/11] [ 0 0 0 1/11 -2/11 4/11 4/11 -5/11] [ 0 0 0 0 1 0 0 0] [ 0 0 0 0 0 1 0 0] [ 0 0 0 0 0 0 1 0] [ 0 0 0 0 0 0 0 1]（原始）基礎被選為 $ q $ -ary for $ q = 11 $ . 您可能會注意到，通過按比例放大 $ q = 11 $ ，我們得到一個整數矩陣。這通常成立，並且可以通過注意到 $ q $ 點陣 $ L $ 滿足：
$$ \begin{align*} q\mathbb{Z}^m&\subseteq L\subseteq \mathbb{Z}^m\ \iff (q\mathbb{Z}^m)^&\supseteq L^ \supseteq \mathbb{Z}^m\ \iff \frac{1}{q}\mathbb{Z}^m&\supseteq L^\supseteq \mathbb{Z}^m\ \iff \mathbb{Z}^m &\supseteq qL^\supseteq q\mathbb{Z}^m \end{align*} $$
這就是說，如果 $ q\mathbb{Z}^m\subseteq L\subseteq \mathbb{Z}^m $ , 那麼對偶格子 $ L^* $ 可能不包含在 $ q\mathbb{Z}^m $ 和 $ \mathbb{Z}^m $ ，縮放的對偶格子始終是。人們經常在論文中將其視為聲明：
$$ \Lambda_q(A)^* = \frac{1}{q}\Lambda_q^\perp(A) $$
事實上，在符號 $ \Lambda_q(A) $ 和 $ \Lambda_q^\perp(A) $ ，你只是在問，給定一個基礎 $ \Lambda_q(A) $ , 建構一個基礎 $ \Lambda_q^\perp(A) $ .