說明：維數格的 NTRU 鍵ddd只有大小O(d日誌d)○(d日誌⁡d)O(dlog{d})

相關的 NTRU 格是維度的 $ d=2N $ . 公鑰和私鑰大小都是長度 $ O(N)=O(d/2)=O(d) $ .

那麼在哪裡 $ d\log(d) $ 出現？

提前致謝。

NTRU 公鑰是多項式 $ d-1 $ 其係數是元素 $ \mathbb{Z}_q $ . 所以你需要表示它的位數是 $ d\log{q} $ . 如果 q 與 d 的順序相同，那麼這給了你 $ d\log{d} $ . 另一方面，私鑰可以表示為 $ O(d) $ 位，因為係數都在集合中 $ {-1,0,1} $ .

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