繁體中文
選單

什麼是數論轉換

把快速傅立葉轉換的想法，應用在以質數為模的整數世界中的轉換。把多項式乘法換成轉換、逐係數相乘與逆轉換，使次數為n時約需n²次的乘法減少到約n log n次。只需不產生誤差的整數運算。是ML-KEM與ML-DSA等以格為基礎之後量子密碼運算的核心，以專用電路加速的研究也正在進行。

日文名稱: 数論変換

「數論轉換」出現在1領域的1道練習題中（硬體安全的進階主題與趨勢等）。

這個名詞所屬的領域: 硬體安全的進階主題與趨勢

練習數論轉換的題目

以格為基礎的後量子密碼，會反覆進行次數 n = 256 的多項式乘法。若把所有係數兩兩相乘的單純方法約需 n² 次乘法，使用數論轉換（NTT）的方法約需 n log₂ n 次，則使用NTT後乘法次數約減為幾分之一，最接近的是下列何者？

  1. A約8分之1
  2. B約32分之1
  3. 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），因此其加速器也很有效。

解析中的「數論轉換」

出現「數論轉換」的題目（1題）

  1. 以格為基礎的後量子密碼，會反覆進行次數 n = 256 的多項式乘法。若把所有係數兩兩相乘的單純方法約需 n² 次乘法，使用數論轉換（NTT）的方法約需 n log₂ n 次，則使用NTT後乘法次數約減為幾分之一，最接近的是下列何者？

相關名詞

後量子密碼 快速傅立葉轉換（FFT） ML-KEM 目標列刷新（TRR） 指標驗證（PAC） 控制流程完整性 硬體物料清單（HBOM） 雷射故障注入 影子堆疊 暫態執行攻擊

前往名詞解釋列表