[發(fā)明專利]用于提高在一個2的指數(shù)的有限主體上的乘法運算性能的方法

無效

• 申請?zhí)枺?/td>: 00812574.0
• 申請日: 2000-07-12
• 公開（公告）號: CN1373868A
• 公開（公告）日: 2002-10-09
• 發(fā)明（設(shè)計）人: J·S·科倫;Y·F·韓;J·張
• 申請（專利權(quán)）人: 格姆普拉斯公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 中國專利代理(香港)有限公司
• 代理人: 王勇,張志醒

1.一種用來在一個手持式或便攜式電子設(shè)備中實現(xiàn)的多項式乘法的改進方法，所述方法把兩個表示一個GF(2＾n)類型有限主體的一個元素的多項式a和b作為輸入，其中：

a＝a(n-1)^*t＾n(n-1)+...+a(1)^*t+a(0)，且

b＝b(n-1)^*t＾(n-2)+...+b(1)^*t+b(0)，

系數(shù)a(i)和b(i)對i從0到n-1的范圍來說等于0或1，所述方法使用一個多項式c作為計算變量a，多項式c和a的表示的寄存器對寄存器編號j來說分別用C[j]和A[j]表示，在每個寄存器中的位數(shù)用w表示，表示一個多項式所需要的寄存器數(shù)目用s表示，所述方法的特征在于：它包含以下六個步驟：

1)將多項式c初始化為0；

2)對j從w-1到0的范圍，執(zhí)行以下步驟：

2)a)對k從1到s的范圍，執(zhí)行運算2)b)；

2)b)如果b(k^*w-1)＝1，則執(zhí)行以下子步驟：

就i從s-1+k-1到k-1的范圍，用寄存器C[i]和寄存器A[i-k+1]之間異或運算的結(jié)果代替寄存器C[i]；

3)將表示多項式c的寄存器向左移一位；

4)將表示多項式b的寄存器向左移一位；

5)返回到步驟(2)；

6)將多項式c返回作為輸出。

2.一種用來在一個手持式或便攜式電子設(shè)備中實現(xiàn)的改進的模數(shù)簡化方法，所述方法把一個次數(shù)小于或等于2^*n-1的多項式a作為輸入，其中a＝a(2^*n-1)^*t＾(2^*n-1)+...+a(1)^*t+a(0)，并返回該有限主體GF(2ⁿ)的一個元素c作為輸出，其中c＝c(n-1)^*t＾n(n-2)+...+c(1)^*t+c(0)，系數(shù)a(i)和c(i)對i從0到n-1的范圍來說等于0或1，多項式c和a的表示的寄存器對寄存器編號j來說分別用C[j]和A[j]表示，在每個寄存器中的位數(shù)用w表示，表示一個多項式所需要的寄存器數(shù)目用s表示，在模數(shù)簡化期間使用的多項式具有t＾n+t＾k+1的形式，其中k是一個整數(shù)參數(shù)，表示一個多項式所必需的寄存器數(shù)目用s表示，所述方法的特征在于：它包含以下十八個步驟：

1)計算p＝n-k對w求模；

2)計算q＝(n-k)/w；

3)將變量temp1和temp2初始化為0；

4)將寄存器A[2^*s-1]向右移p位得到A[2^*s-1-s/2]；

5)將變量temp1向右移一位；

6)對j從2^*s-1到2^*s-1-s/2的范圍，用A[j-q]XOR?A[j]代替A[j-q]；

7)用A[2^*s-1-s/2-q-1]XOR?temp1代替A[2^*s-1-s/2-q-1]；

8)將寄存器A[2^*s-1]向右移p位得到A[2^*s-1-s/2]；

9)將變量temp1向右移一位；

10)對j從s-1+s/2到s的范圍，用A[j-q]XOR?A[j]代替A[j-q]；

11)用A[s-q-1]XOR?temp1代替A[s-q-1]；

12)將變量mask初始化為(-1)＜＜(n?mod?w)，其中運算＜＜(n?modw)表示向左循環(huán)移n?mod?w位；

13)用A[s-1]?AND?mask代替temp1；

14)對i從p到1的范圍：

14)a)將多項式temp1向右移1位；

14)b)將多項式temp2向右移1位；

15)用A[(s-1)-q-1]XOR?temp1代替A[(s-1)-q]；

16)用A[(s-1)-q-1]XOR?temp2代替A[(s-1)-q-1]；

17)對i從0到s-1的范圍用A[i]代替C[i]；

18)將多項式c返回作為輸出。