硬體安全的進階主題與趨勢
以格為基礎的後量子密碼，會反覆進行次數 n = 256 的多項式乘法。若把所有係數兩兩相乘的單純方法約需 n² 次乘法，使用數論轉換（NTT）的方法約需 n log₂ n 次，則使用NTT後乘法次數約減為幾分之一，最接近的是下列何者？
- A約8分之1
- B約32分之1
- C約256分之1
查看答案與解析
正確答案：B. 約32分之1
單純方法需要 n² = 256² = 65,536 次，使用NTT的方法需要 n log₂ n = 256 × 8 = 2,048 次，因此 65,536 ÷ 2,048 = 32，約減為32分之1。數論轉換是把快速傅立葉轉換的想法應用在以質數為模的整數世界中的轉換，轉換後只需逐係數相乘。ML-KEM以 q = 3329 為模處理係數，並以使用NTT計算為前提設計，因此NTT電路是後量子密碼加速器的核心元件。此外，ML-KEM與ML-DSA在產生矩陣與亂數時大量使用SHA-3家族的函數（SHAKE），因此其加速器也很有效。
- A. 這只回答了 log₂ n = log₂ 256 = 8。比值是 n² ÷ (n log₂ n) = n ÷ log₂ n。
- B. 正確。256 ÷ 8 = 32。
- C. 這是 n² ÷ n = n，忘了除以 log₂ n 的值。