[發(fā)明專利]利用預(yù)處理機(jī)制以及改進(jìn)NTT的高效多項(xiàng)式乘法運(yùn)算方法

在審

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

1.一種利用預(yù)處理機(jī)制以及改進(jìn)NTT的高效多項(xiàng)式乘法運(yùn)算方法，其特征在于：包括以下三個階段，分別為：預(yù)處理多項(xiàng)式拆分階段、相乘階段和多項(xiàng)式合并階段；

預(yù)處理多項(xiàng)式拆分階段：將兩個多項(xiàng)式a(x)、b(x)進(jìn)行拆分，得到拆分項(xiàng)a_even、a_odd、b_even、b_odd；

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

多項(xiàng)式合并階段：對含拆分項(xiàng)的目標(biāo)多項(xiàng)式c進(jìn)行合并，得到合并后的目標(biāo)多項(xiàng)式c。

2.如權(quán)利要求1所述的一種利用預(yù)處理機(jī)制以及改進(jìn)NTT的高效多項(xiàng)式乘法運(yùn)算方法，其特征在于：所述多項(xiàng)式a(x)、b(x)的表達(dá)式如下：

a(x)＝a₀+a₁x+...+a_n-1x^n-1∈Z_q/(xⁿ+1)

b(x)＝b₀+b₁x+...+b_n-1x^n-1∈Z_q/(xⁿ+1)

其中Z_q表示包含元素{0，…，q-1}的整數(shù)環(huán)；Z[x]表示系數(shù)為整數(shù)，變量為x的多項(xiàng)式環(huán)，Z_q[x]表示系數(shù)在Z_q上的多項(xiàng)式環(huán)；環(huán)Z_q[x]/(xⁿ+1)表示此環(huán)上所有的操作都需要模xⁿ+1和q；多項(xiàng)式a(x)、b(x)為在環(huán)Z_q[x]/(xⁿ+1)上的多項(xiàng)式，為抗量子密鑰交換方案中的密文和私鑰。

3.如權(quán)利要求2所述的一種利用預(yù)處理機(jī)制以及改進(jìn)NTT的高效多項(xiàng)式乘法運(yùn)算方法，其特征在于：預(yù)處理多項(xiàng)式拆分階段，多項(xiàng)式a(x)、b(x)被拆分為：

a(x)＝a_even(x²)+x·a_odd(x²)

b(x)＝b_even(x²)+x·b_odd(x²)

其中，a_even、b_even分別表示原多項(xiàng)式a(x)、b(x)的偶數(shù)項(xiàng)；a_odd，b_odd分別表示原多項(xiàng)式a(x)、b(x)的奇數(shù)項(xiàng)。