[發(fā)明專利]利用預處理機制以及改進NTT的高效多項式乘法運算方法

在審

• 申請?zhí)枺?/td>: 202310202074.2
• 申請日: 2023-03-03
• 公開（公告）號: CN116466912A
• 公開（公告）日: 2023-07-21
• 發(fā)明（設計）人: 程池;胡凱
• 申請（專利權(quán)）人: 中國地質(zhì)大學（武漢）
• 主分類號: G06F7/523
• 分類號: G06F7/523;G06F21/46;G06N10/20
• 代理公司: 武漢知產(chǎn)時代知識產(chǎn)權(quán)代理有限公司 42238
• 代理人: 孔燦

本發(fā)明公開了一種利用預處理機制以及改進NTT的高效多項式乘法運算方法，方法包括分別為：預處理多項式拆分階段、相乘階段和多項式合并階段；預處理多項式拆分階段：將兩個多項式a(x)、b(x)進行拆分，得到拆分項asubgt;even/subgt;、asubgt;odd/subgt;、bsubgt;even/subgt;、bsubgt;odd/subgt;；相乘階段：根據(jù)拆分項，將多項式a(x)、b(x)相乘，得到含拆分項的目標多項式c；多項式合并階段：對含拆分項的目標多項式c進行合并，得到合并后的目標多項式c。本發(fā)明有益效果是：大幅減少了乘法運算次數(shù)，實現(xiàn)高效的多項式乘法。

技術(shù)領域

本發(fā)明涉及抗量子密碼領域，尤其涉及一種利用預處理機制以及改進NTT的高效多項式乘法運算方法。

背景技術(shù)

隨著量子計算機的飛速發(fā)展，公鑰密碼體制正面臨著巨大的威脅。為了抵抗量子計算機的威脅，抗量子密碼學應運而生，受到了學術(shù)界和工業(yè)界廣泛的關注，而評價一個抗量子密碼方案，除了其安全性及其密鑰和消息的大小等因素之外，其執(zhí)行效率也是非常關鍵的指標。多項式乘法在各種抗量子密碼算法中廣泛使用，在某種程度上，多項式相乘的效率影響著整個密碼方案的效率，因而提高多項式乘法算法的效率是非常重要的事情。

在多項式環(huán)Z_q/(ⁿ+1)上，對多項式系數(shù)模q的兩個多項式a,b進行乘法運算，當a,b直接相乘c＝a·b時，將消耗²次乘法，(-1)²次加法。此時若n取的數(shù)較大，則意味著多項式之間的乘法運算開銷也是巨大的。

為了提高多項式乘法之間的效率，現(xiàn)廣泛使用快速數(shù)論變換算法(NTT，NumberTheoretic?Transform)來進行處理。NTT可看作是在有限環(huán)上的離散傅里葉變化，基本思想是將多項式系數(shù)轉(zhuǎn)換到NTT域，然后對應系數(shù)相乘，對相乘結(jié)果進行逆NTT操作即可。即c＝NTT^-1(()°NTT(b))，此過程涉及次乘法，nlogn次加減法。但現(xiàn)有的NTT算法仍然效率不高，有進一步的提升空間。

發(fā)明內(nèi)容

為了解決現(xiàn)有環(huán)多項式乘法運算中開銷過大的問題，本發(fā)明提出一種利用預處理機制以及改進NTT的高效多項式乘法運算方法，包括：

預處理多項式拆分階段、相乘階段和多項式合并階段；

預處理多項式拆分階段：將兩個多項式a(x)、b(x)進行拆分，得到拆分項a_even、a_odd、b_even、b_odd；

相乘階段：根據(jù)拆分項，將多項式a(x)、b(x)相乘，得到含拆分項的目標多項式c；

多項式合并階段：對含拆分項的目標多項式c進行合并，得到合并后的目標多項式c。

本發(fā)明提供的有益效果是：通過實現(xiàn)不完整的NTT以及逆NTT算法，大幅減少了乘法運算次數(shù)，雖然有加減法操作數(shù)的增加，但在現(xiàn)代x86架構(gòu)處理器中，乘法運算的消耗遠遠高于加減法，這使得在實際運算過程中，可以實現(xiàn)高效的多項式乘法。

附圖說明

圖1是本發(fā)明方法示意圖。

具體實施方式

為使本發(fā)明的目的、技術(shù)方案和優(yōu)點更加清楚，下面將結(jié)合附圖對本發(fā)明實施方式作進一步地描述。

請參考圖1，圖1是本發(fā)明方法示意圖。本發(fā)明提供了一種利用預處理機制以及改進NTT的高效多項式乘法運算方法，具體包括：

預處理多項式拆分階段、相乘階段和多項式合并階段；