一種計算伽羅華域本原元正整數次冪的方法

2023-05-03 04:12:26 2

專利名稱：一種計算伽羅華域本原元正整數次冪的方法
技術領域：
本發明涉及信息安全技術中的代數編解碼領域，具體來說是一種計算伽羅華域本原元正整數次冪的方法。
背景技術：
有限域乘法是目前代數編解碼領域中應用到較多的運算，其中很多加密認證算法都要利用有限域乘法。伽羅華域就是廣泛應用於代數編解碼領域的一種重要有限域，伽羅華域的運算是主要指在特定規則下進行的兩類運算:加法和乘法。在伽羅華域中僅包含O和I兩個元素，其運算規則與有理數域不同，具體而言:加法是一種邏輯異或計算，可很容易利用一個異或門來實現；而乘法是一種邏輯與運算，利用一個與門也可以輕易實現。例如,對於一個伽羅華 域中ak(K為非負整數)的加法規則為:ak+ak = (ri)ak = 0，記為公式(一)；a k+0 = a k+0* a k = (Γ0) a k = a k, a k+0 = a k 記為公式(二)，其中 ~ 表示邏輯異或。例如a2+a2 = 0, a 2+0 = a 2，補充說明a°=l。對於一個伽羅華域GF (2m)，若a為伽羅華域GF (2m)的本原元，可將GF (2m)的本原多項式表示為 P(X) = Xm+b[m-l]Xm-Wb [m-2]Xm_2+b[m-3]Xm_3+...+b [l]X+b [O]，其中:m 是正整數，數組b[m]是本原多項式p(X)的O (m-1)次項的係數數組，b
b[m_l]是數組b[m]的m個元素，b[m]數組元素值為O或I。伽羅華域上元素的表示方法與域上運算算法關係密切，其域元素可用本原元素、剩餘類、多項式及矢量表示，其中最直接的表示方法是本原元素表示方法(又稱指數表示、冪次表示)。由生成GF(2m)域的本原多項式，可從本原元素表示法導出其他三種表示方法。根據伽羅華域原理，本原元a是方程P(X) =0的一個根，即 P ( Ct ) = O,可以得到 a m+b [m-1] a m_1+b [m_2] a m_2+b [m_3] a m'..+b [I] a +b
=0，再根據伽羅華域加法原理得到 a m = b [m-1] a ^+b [m_2] a m_2+b [m_3] a -3+...+b [I]a +b
,記為公式(三)。在代數編解碼過程中，經常需要把α的正整數次冪即an(n為正整數)變換成最高次冪小於m的多項式表達式(簡稱為一表達式)。根據公式(三)可知無論η為多大的正整數，αη都可表示為最高次冪小於m的形式。例如:p(X) = X14+X12+Xn+X+1，則a 14 = a12+an+a+l, a 16 = a 14* a 2 = ( a 12+a n+a+1) a2 = a 14+( a 13+a 3+a 2)=a 12+a n+a+1+( a 13+a 3+a 2) = a 13+a 12+a n+a 3+a 2+a+1，因此 an 可以表示為如下格式:ct n = c [m-1] a m:+c [m~2] a m 2+c [m-3] a m 3+...+c [I] a +c
，記為公式(四)，其中c [O] c [m-1]是a n對應多項式表達係數數組c [m]的m個元素，c[m]數組元素值為O或
1由公式(四)可知，若求得a11對應多項式表達係數數組c[m]的值，則可進一步求得a n的表達式。在已知本原多項式，即本原多項式最高冪次m值和本原多項式係數數組b[m]值已知的情況下，對於任意正整數n，都有唯一確定的a n對應多項式表達係數數組c[m]與之相對應。因此，計算本原元a的正整數次冪a "的關鍵在於獲取該數組c [m]的值。
現有技術中採用一種制表存儲方式來計算α η，即預先存儲與η對應的數組c[m]，之後查表獲取相應的數組元素c [O] c [m-Ι]，再根據公式(四)計算αη。通過存儲每個η對應的數組c [m]來提供α11表達式的值，其中η最多取值個數用N表示，則存儲每個η對應的數組c [m]共需要N*m個比特的存儲空間。當N比較大而且m值比較大時，則需要很大的存儲空間來存放每個η對應的數組c [m]。比如I彡η彡1024，m = 16，則需要16384比特的空間來存放每個η對應的數組c [m]。這無疑提高了處理器的存儲要求，因而有必要提出一種新的伽羅華域本原元正整數次冪的計算方法。

發明內容
有鑑於此，本發明的目的在於提供一種計算伽羅華域本原元正整數次冪的方法，用以解決存儲本原元α η表達式所對應數組c [m]，在η範圍比較大而且m值比較大情況下佔用存儲空間大的問題。為解決以上技術問題，本發明提供的技術方案是，一種計算伽羅華域本原元正整數次冪的方法，包括:預先構造遞歸函數update_c (X),該遞歸函數update_c (X)用以根據本原多項式中最高次冪m和係數數組b[m]的值計算與本原元正整數次冪α11對應^"對應多項式表達係數數組c [m]的值；以η為參數,執行該遞歸函數update_c(x),用以獲取數組c[m]的值；根據表達式 a n = c [m-1] a m:+c [m-2] a m 2+c [m-3] a m 3+...+c [I] a +c
進打計算，用以獲取本原元正整數次冪a n的計算結果。其中:該 遞歸函數update_C(X)中，輸入參數x為正整數，遞歸規則如下:如果X小於m，則將數組c[m]中的元素c[x]更新為c[x]與I的異或值；函數update_c(x)更新數組c[m]結束。如果X等於m,則將數組c[m]更新為數組c[m]與數組b[m]的按位異或值；函數update_c(x)更新數組c[m]結束。如果X大於m,從步驟s[m-l]_0開始執行以下操作:步驟s[m-l]_0:判斷b[m_l]是否為I,若b[m_l]為I則執行步驟s,否則執行步驟s [m-2] _0 ；步驟s[m-l]_l:比較χ-l值與m值,若χ-l小於m,則執行步驟s[m_l]_2 ;若x_l等於m,則執行步驟s[m-l]_3 ;若χ-l大於m,則執行步驟s[m_l]_4 ；步驟s [m-1]_2:執行 c[x_l] = c [x_l] ~b [m_l],然後執行步驟 s [m_2]_0 ；步驟s[m_l]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_2]_0 ；步驟s[m_l]_4:執行 update_c (x_l),然後執行步驟 s[m_2]_0 ；步驟s[m-2]_0:判斷b[m_2]是否為1，若b[m_2]為I則執行步驟s [m_2]_l，否則執行步驟s [m-3] _0 ；步驟s [m-2]_1:比較x_2值與m值，若x_2小於m，則執行步驟s [m_2]_2 』若x_2等於m,則執行步驟s [m-2]_3 ;若χ-2大於m,則執行步驟s [m_2]_4 ；步驟s[m_2]_2:執行 c[x_2] = c[x_2] ~b[m_2],然後執行步驟 s[m_3]_0 ；
步驟s[m_2]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_3]_0 ；步驟s [m-2]_4:執行 update_c (x_2),然後執行步驟 s [m_3]_0 ；步驟s [m-3]_0:判斷b [m-3]是否為1，若b [m-3]為I則執行步驟s [m_3]_l，否則執行步驟s [m-4] _0 ；步驟s[m_3]_l:比較x_3值與m值,若x_3小於m,則執行步驟s[m_3]_2 ;若x_3等於m,則執行步驟s [m-3]_3 ;若χ-3大於m,則執行步驟s [m_3]_4 ；步驟s[m_3]_2:執行 c[x_3] = c[x_3] ~b[m_3],然後執行步驟 s[m_4]_0 ；步驟s[m_3]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_4]_0 ；步驟s [m-3]_4:執行 update_c (χ-3),然後執行步驟 s [m_4]_0 ；步驟s[l]_0:判斷b[l]是否為1，若b[l]為I則執行步驟s[l]_l，否則執行步驟s
_0 ；步驟s[l]_l:比較χ-m+l值與m值,若χ-m+l小於m,則執行步驟s[l]_2 ;若x-m+1等於m,則執行步驟s[l]_3 ;若χ-m+l大於m,則執行步驟s[l]_4 ；步驟s[l]_2:執行 c [χ-m+l] = c [x-m+l] ~b [I],然後執行步驟 s
_0 ；步驟s[l]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c[m_2] = c [m_2] ~b [m_2]、c [m-3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[l]_0 ；步驟s[l]_4:執行 update_c (χ-m+l),然後執行步驟 s
_0 ；步驟s
_0:判斷b
是否為1，若b
為I則執行步驟s
_l，否則函數update_c (x)結束；步驟s
_l:比較x-m值與m值,若χ-m小於m,則執行步驟s
_2 ;若χ-m等於m,則執行步驟s
_3 ;若x-m大於m,則執行步驟s
_4 ；步驟s
_2:執行 c [x-m] = c [x_m] ~b [O],然後函數 update_c (x)結束；步驟s
_3:執行 c [m-1] = c [m_l] ~b [m_l]、c[m_2] = c [m_2] ~b [m_2]、c [m-3]=c[m-3] ~b[m-3]...c[l] = c[l]~b[l]、c
= c
~b
操作，然後函數 update_c (x)結束；步驟s
_4:執行 update_c (χ-m),函數 update_c (x)更新數組 c [m]結束。其中調用函數update_c (X)前預先將數組c[m]初始化為O。可選地，採用通用處理器，以計算伽羅華域本原元正整數次冪。或者，通過與門、異或門來實現硬體構建，以計算伽羅華域本原元正整數次冪。與現有技術相比，本發明計算伽羅華域本原元正整數次冪的方法無需存儲η個數組c [m],假定η最多取值個數用N表示,貝U本發明可節省N*m個比特的存儲空間。例如N =1024，m = 16時可節省16384比特的存儲空間，特別適用於存儲空間較為緊張的場合。


圖1表示本發明計算伽羅華域本原元正整數次冪的方法的基本流程；圖2表示圖1中遞歸計算步驟的基本過程。
具體實施例方式本發明的核心思想是，根據公式(一)、(二)、(三)、(四)的特點，預先構造根據m和數組b[m]的值計算數組c [m]值的遞歸函數update_c(x);之後將數組c[m]初始化為O,然後執行函數update_c (x)，即可得到數組c [m]的值；最後根據an=c [m-1] a 「+c [m-2]a m_2+c[m-3] a m_3+...+c[l] a +c
的表達式計算，得到伽羅華域本原元正整數次冪a '本發明實施例計算伽羅華域本原元正整數次冪an時，函數update_c(x)例化為update_c (η),則update_c (η)算法的基本原理是:(I)若η小於m則只需把c [η]更新為c [η] ~I,即c [n] = c [η] ~I,就計算完畢；(2)若η等於m,則數組c [m]更新為數組c[m]與b[m]的按位異或值，即c[m_l]=c [m-1] 'b [m-1] > c [m-2] = c [m-2] 'b [m-2] > c [m-3] = c [m-3] 'b [m-3]...c [I]=c [l]~b [I]、c
= c
~b
，就計算完畢。(3)如果 n 大於 m，由算法原理可知 αη = a n_m* a m = a n_m* (b [m-1] a 「+b [m-2]a m_2+b[m-3] a『3+...+b[I] a +b
) = b[m-1]* a n_1+b[m-2]* a n_2+b[m-3]* a n_3+...+b[I]*an_m+1+b
*an_m。則從步驟s[m-l]_0開始執行以下操作:步驟s[m-l]_0:判斷b[m_l]是否為I,若b[m_l]為I則執行步驟s,否則執行步驟s [m-2] _0。步驟s[m-l]_l:比較n_l值與m值,若n_l小於m,則執行步驟s[m_l]_2 ;若n_l等於m,則執行步驟s[m-l]_3 ;若n_l大於m,則執行步驟s[m_l]_4。步驟s [m-1]_2:執行 c[n_l] = c [n_l] ~b [m_l],然後執行步驟 s [m_2]_0。步驟s[m_l]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_2]_0。步驟s[m_l]_4:執行 update_c (n_l)，然後執行步驟 s[m_2]_0。步驟s [m-2]_0:判斷b [m-2]是否為1，若b [m-2]為I則執行步驟s [m_2]_l，否則執行步驟s [m-3] _0。步驟s [m-2]_1:比較n_2值與m值，若n_2小於m，則執行步驟s [m_2]_2 ;若n_2等於m,則執行步驟s[m-2]_3 ;若n~2大於m,則執行步驟s[m_2]_4。步驟s[m_2]_2:執行 c[n_2] = c[n_2] ~b[m_2],然後執行步驟 s[m_3]_0。步驟s[m_2]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_3]_0。步驟s[m_2]_4:執行 update_c (n_2),然後執行步驟 s[m_3]_0。步驟s [m-3]_0:判斷b [m-3]是否為1，若b [m-3]為I則執行步驟s [m_3]_l，否則執行步驟s [m-4] _0。

步驟s[m-3]_l:比較n_3值與m值，若n_3小於m,則執行步驟s[m_3]_2 ;若n_3等於m,則執行步驟s[m-3]_3 ;若n_3大於m,則執行步驟s[m_3]_4。步驟s[m_3]_2:執行 c[n_3] = c[n_3] ~b[m_3],然後執行步驟 s[m_4]_0。步驟s[m_3]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_4]_0。步驟s[m_3]_4:執行 update_c (n_3)，然後執行步驟 s[m_4]_0。
...
步驟s[l]_0:判斷b[l]是否為1，若b[l]為I則執行步驟s [1]_1，否則執行步驟s
_0。步驟s[l]_l:比較η-m+l值與m值,若η-m+l小於m,則執行步驟s[l]_2 ；^f n-m+1等於m,則執行步驟s[l]_3 ;若η-m+l大於m,則執行步驟s[l]_4。步驟s[l]_2:執行 c[η-m+l] = c[n_m+l] ~b[I],然後執行步驟 s
_0。步驟s[l]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c[m_2] = c [m_2] ~b [m_2]、c [m-3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[l]_0。步驟s[l]_4:執行 update_c (η-m+l),然後執行步驟 s
_0。步驟s
_0:判斷b
是否為1，若b
為I則執行步驟s
_l，否則函數update_c (η)結束。步驟s
_l:比n-m值與m值,若n-m小於m,則執行步驟s
_2 ;若n-m等於m,則執行步驟s
_3 ;若n-m大於m，則執行步驟s
_4。步驟s
_2:執行 c [n-m] = c [n_m] ~b [O],然後函數 update_c (η)結束。步驟s
_3:執行 c [m-1] = c [m_l] ~b [m_l]、c[m_2] = c [m_2] ~b [m_2]、c [m-3]=c[m-3] ~b[m-3]...c[l] = c[l]~b[l]、c
= c
~b
操作，然後函數 update_c (n)結束。步驟s
_4:執行 update_c (n-m),函數 update_c (η)更新數組 c [m]結束。本發明計算伽羅華域本原元正整數次冪的方法可根據上述遞歸函數計算數組c[m],因而無需存儲數組c [m],從而節省存儲空間,其關鍵在於遞歸函數update_c(x)的構建，即遞歸函數update_C(x)的算法實現。為了使本領域的技術人員更好地理解本發明的技術方案，下面結合附圖和具體實施例對本發明作進一步的詳細說明。參見圖1，表示本發明計算伽羅華域本原元正整數次冪的方法的基本過程。具體的說，本發明執行以下完整過程:(I)預先構造遞歸函數update_c (X),該遞歸函數update_c (X)用以根據本原多項式中最高次冪m和係數數組b[m]的值計算與本原元正整數次冪αη對應多項式表達係數數組c[m]的值；(2)以η為參數,執行該遞歸函數update_c (x),用以獲取數組c [m]的值；(3)根據表達式 ct n = c [m_l] a m:+c [m_2] a m 2+c [m_3] ct m 3+...+c [I] a +c
進行計算，用以獲取本原元正整數次冪的計算結果。具體地,該利用函數update_c (x)計算α η值的算法如下:SlOl、初始化步驟-將本原元正整數次冪α η對應多項式表達係數數組c [m]中
的每個元素都初始化為O。S102、遞歸計算步驟-執行根據m和數組b[m]的值而構造的遞歸函數update—
C (X),計算數組C [m]的值。

S103、計算本原元正整數次冪步驟-依據公式=
m 2+c [m-3] a m 3+...+c [I] α +c [O]，計算本原兀正整數次幕 α η。上述算法可採用通用處理器計算伽羅華域本原元正整數次冪，也可以通過與門、異或門來實現硬體構建，以計算伽羅華域本原元正整數次冪。
參見圖2，表示表示圖1中遞歸計算步驟的基本過程。該遞歸算法實現為:令函數update_c(x)為更新數組c[m]的遞歸函數,其中x是其輸入參數,要求x為正整數,遞歸規則如下:S201、比較X與m，根據比較結果分別選擇相應操作:如果X小於m，那麼執行步驟S202 ；如果X等於m,那麼執行步驟S203 ；如果X大於m，那麼執行步驟S204 ；S202、將數組c[m]中的元素c[x]更新為c[x]與I的異或值，即執行c[x]=c[x]~l操作，然後退出函數。S203、將數組c[m]更新為數組c[m]與數組b[m]的按位異或值，即執行c[m_l]=c [m-1] 'b [m-1] > c [m-2] = c [m-2] 'b [m-2] > c [m-3] = c [m-3] 'b [m-3]...c [I]=c[l]~b[l]、c
= c
~b
操作,然後退出函數。S204、從步驟s[m-l]_0開始執行，更新數組c[m]。由算法原理可知，執行α x =a x--* am= a x_m* (b [m-1] a -^+b [m-2] a m_2+b [m-3] a m_3+...+b [I] a +b
) = b [m-1]* a x_J+b [m-2]* a x_2+b [m-3]* a x_3+...+b [I]* a x-m+1+b
*x_m 操作即可得到 a x，因而只需要從步驟s[m-l]_0開始執行更新數組c[m]。其中具體計算步驟如下，即從步驟s[m-l]_0開始執行以下操作:步驟s[m-l]_0:判斷b[m_l]是否為I,若b[m_l]為I則執行步驟s,否則執行步驟s [m-2] _0。步驟s[m-l]_l:比較χ-l值與m值,若χ-l小於m,則執行步驟s[m_l]_2 ;若χ-l等於m,則執行步驟s[m-l]_3 ;若χ-l大於m,則執行步驟s[m_l]_4。步驟s [m-1]_2:執行 c [χ-l] = c [x_l] ~b [m_l],然後執行步驟 s [m_2]_0。步驟s[m_l]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_2]_0。步驟S[m-1]_4:執行 update_c (X-1),然後執行步驟 s[m_2]_0。步驟s[m-2]_0:判斷b[m_2]是否為1，若b[m_2]為I則執行步驟s [m_2]_l，否則執行步驟s [m-3] _0。步驟s [m-2]_1:比較x_2值與m值，若x_2小於m，則執行步驟s [m_2]_2 』若χ-2等於m,則執行步驟s[m-2]_3 ;若χ-2大於m,則執行步驟s[m_2]_4。步驟s[m_2]_2:執行 c[x_2] = c[x_2] ~b[m_2],然後執行步驟 s[m_3]_0。步驟s[m_2]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_3]_0。步驟s[m_2]_4:執行 update_c (x_2),然後執行步驟 s[m_3]_0。步驟s[m-3]_0:判斷b[m_3]是否為1，若b[m_3]為I則執行步驟s [m_3]_l，否則執行步驟s [m-4] _0。步驟s[m-3]_l:比較χ-3值與m值，若χ-3小於m,則執行步驟s[m_3]_2 ;若χ-3等於m,則執行步驟s[m-3]_ 3 ;若χ-3大於m,則執行步驟s[m_3]_4。步驟s[m_3]_2:執行 c[x_3] = c[x_3] ~b[m_3],然後執行步驟 s[m_4]_0。步驟s[m_3]_3:執行 c[m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=C[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作,然後執行步驟 s[m_4]_0。步驟s[m_3]_4:執行 update_c (x_3)，然後執行步驟 s[m_4]_0。步驟s[l]_0:判斷b[l]是否為1，若b[l]為I則執行步驟s [1]_1，否則執行步驟s
_0。步驟s[l]_l:比較χ-m+l值與m值,若χ-m+l小於m,則執行步驟s[l]_2 ;若χ-m+l等於m,則執行步驟s[l]_3 ;若χ-m+l大於m,則執行步驟s[l]_4。步驟s[l]_2:執行 c[χ-m+l] = c[x-m+l] ~b[I],然後執行步驟 s
_0。步驟s [1]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[l]_0。步驟s[l ]_4:執行 update_c(x_m+l),然後執行步驟 s
_0。步驟s
_0:判斷b
是否為1，若b
為I則執行步驟s
_l，否則函數update_c (X)結束。步驟s
_l:比較x-m值與m值,若χ-m小於m,則執行步驟s
_2 ;若χ-m等於m,則執行步驟s
_3 ;若x-m大於m,則執行步驟s
_4。步驟s
_2:執行 c [x-m] = c [x_m] ~b [O],然後函數 update_c (x)結束。步驟s
_3:執行 c [m_l] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l]~b[l]、c
= c
~b
操作，然後函數 update_c (x)結束。步驟s
_4:執行 update_c(x_m),然後函數 update_c(x)結束。應用實例:本原多項式最高冪次m = 14，本原多項式p(X) = X14+X12+Xn+X+1，即數組b[m]=[O,O,I,I,O,O,O,O,O,O,O,O,O,I,l]o 若 α 為伽羅華域 GF(214)的本原元，則 α 14 =
α 12+ α η+ a +10其中，利用函數update_c(x)計算αη值的算法如下:(I)將數組c[14]中每個元素都初始化為O。(2)執行函數 update_c(n),計算數組 c[14]的值，即得到 an= c[13] a 13+c[12]ct 12+c [11] a n+...+c [I] a +c
o具體地,更新數組c [m]的遞歸函數update_c (X)的計算規則如下:如果X小於14,那麼執行c [X] = c [X] ~ I操作,然後退出函數；如果X 等於 14,那麼執行 c [12] =c[12]~l、c[ll] =c[ll]~l、c[l] = c[l] ~1、c[O] = c
~I操作,然後退出函數。如果X大於14,從步驟example_s[12]_l開始執行,其中:步驟example_s [12]_1:比較x_2與14,如果x_2小於14則執行步驟examp I e_s[12]_2,如果x-2等於14則執行步驟example_s[12]_3，如果x_2大於14則執行步驟example_s[12]_4。步驟example_s[12]_2:執行 c[x_2] = c[x_2] ~1 操作,然後執行步驟 example_s[ll]_l。步驟example_s [12]_3:執行 c [12] = c[12]~l、c[ll] = c[ll]~l、c[l] = c[l] >c [O] = c
~1 操作,然後執行步驟 example_s[ll]_l。步驟example_s [12]_4:執行 update_c (x_2)操作，然後執行步驟 examp I e_s[ll]_l。步驟example_s [11]_1:比較χ-3與14,如果χ-3小於14則執行步驟examp I e_s[ll]_2,如果χ-3等於14則執行步驟example_s[ll]_3,如果χ-3大於14則執行步驟exampIe_s[11]_4。步驟example_s[11]_2:執行 c[x_3] = c[x_3] ~1 操作,然後執行步驟 example_s[l]_l。步驟example_s[ll]_3:執行 c [12] = c[12]~l、c[ll] = c[ll]~l、c[l] = c[l] >c
= c
~1 操作,然後執行步驟 example_s[l]_l。步驟example_s [11]_4:執行 update_c (χ-3)操作，然後執行步驟 examp I e_s[l]_l。步驟example_s [1]_1:比較x_13與14,如果x_13小於14則執行步驟example_s[l]_2,如果χ-13等於14則執行步驟example_s[l]_3,如果x_13大於14則執行步驟example_s[1]_4。步驟example_s[1]_2:執行 c[x_13] = c[x_13]~l 操作，然後執行步驟 example_s
_l。步驟example_s [1]_3:執行 c [12] =c[12]~l、c[ll] =c[ll]~l、c[l] = c[l] >c [O] = c [O] ~ I 操作,然後執行步驟 examp I e_s [O] _1。步驟example_s [1]_4:執行 update_c (χ-13)操作，然後執行步驟 example_s
_l。步驟example_s
_1:比較x_14與14,如果x_14小於14則執行步驟example_s
_2,如果χ-14等於14則執行步驟example_s
_3,如果x_14大於14則執行步驟example_s
_4。步驟example_s
_2:執行 c[x_14] = c [x_14] ~ I 操作,然後函數 update_c (x)結束。步驟example_s
_3:執行 c [12] =c[12]~l、c[ll] =c[ll]~l、c[l] = c[l] >c [O] = c
~1操作，然後函數update_c(x)結束。步驟example_s
_4:執行 update_c (χ-14)操作,然後函數 update_c (χ)結束。

以上實施例所述計算伽羅華域本原元正整數次冪的方法無需存儲數組c [m]，因而可節省存儲空間，特別適用於存儲空間較為緊張的場合。

以上僅是本發明的優選實施方式，應當指出的是，上述優選實施方式不應視為對本發明的限制，本發明的保護範圍應當以權利要求所限定的範圍為準。對於本技術領域的普通技術人員來說，在不脫離本發明的精神和範圍內，還可以做出若干改進和潤飾，這些改進和潤飾也應視為本發明的保護範圍。
權利要求
1.一種計算伽羅華域本原元正整數次冪的方法，其特徵在於，包括: 預先構造遞歸函數update_c (x),該遞歸函數update_c (x)用以根據本原多項式中最高次冪m和係數數組b[m]的值計算與本原元正整數次冪α11對應多項式表達係數數組c[m]的值； 以η為參數，執行該遞歸函數update_c (x),用以獲取數組c [m]的值； 根據表達式 a n = c [m-1] a [m_2] α m-2+c [m_3] a -3+...+c[l] α+c
進行計算，用以獲取本原元正整數次冪的計算結果。
2.如權利要求1所述的計算伽羅華域本原元正整數次冪的方法，其特徵在於，該遞歸函數update_C (X)中，輸入參數X為正整數，遞歸規則如下: 如果X小於m,則將數組c [m]中的元素c [X]更新為c[x]與I的異或值；函數update_c(x)更新數組c [m]結束； 如果X等於m，則將數組c[m]更新為數組c[m]與數組b[m]的按位異或值；函數update_c(x)更新數組c[m]結束； 如果X大於m，從步驟s[m-l]_0開始執行以下操作: 步驟s[m-l]_0:判斷b[m-l]是否為1，若b[m_l]為I則執行步驟s[m_l]_l，否則執行步驟 s [m-2]_0 ； 步驟s[m-l]_l:比較x-Ι值與m值,若x_l小於m,則執行步驟s[m_l]_2 ;若x_l等於m，則執行步驟s[m-l]_3 ;若χ-l大於m,則執行步驟s[m_l]_4 ； 步驟 s [m-1]_2:執行 c[x-l] = c[x-l] ~b[m-l],然後執行步驟 s[m-2]_0 ；`步驟 s[m_l]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[m_2]_0步驟 s[m-l]_4:執行 update_c (x-1),然後執行步驟 s[m_2]_0 ； 步驟s[m-2]_0:判斷b[m-2]是否為1，若b[m_2]為I則執行步驟s [m_2]_l，否則執行步驟 s [m-3]_0 ； 步驟s[m-2]_l:比較χ-2值與m值,若x_2小於m,則執行步驟s[m_2]_2 ;若x_2等於m,則執行步驟s [m-2]_3 ;若x_2大於m,則執行步驟s [m_2]_4 ；步驟 s[m-2]_2:執行 c [x-2] = c [x_2] ~b [m_2],然後執行步驟 s[m_3]_0 ；步驟 s[m_2]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[m_3]_0 ；步驟 s[m-2]_4:執行 update_c (x-2),然後執行步驟 s[m_3]_0 ； 步驟s[m-3]_0:判斷b[m-3]是否為1，若b[m_3]為I則執行步驟s [m_3]_l，否則執行步驟 s [m-4] _0 ； 步驟s[m-3]_l:比較χ-3值與m值,若x_3小於m,則執行步驟s[m_3]_2 ;若x_3等於m,則執行步驟s [m-3]_3 ;若x_3大於m,則執行步驟s [m_3]_4 ；步驟 s[m-3]_2:執行 c [x-3] = c [x_3] ~b [m_3],然後執行步驟 s[m_4]_0 ；步驟 s[m_3]_3:執行 c [m-1] = c [m_l] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[m_4]_0 ；步驟 s[m-3]_4:執行 update_c (x-3),然後執行步驟 s[m_4]_0 ；步驟s[l]_0:判斷b[l]是否為1，若b[l]為I則執行步驟s[l]_l，否則執行步驟S
_0 ； 步驟s[l]_l:比較x-m+1值與m值,若χ-m+l小於m,則執行步驟s[l]_2 ;若χ-m+l等於m,則執行步驟s[l]_3 ;若χ-m+l大於m,則執行步驟s[l]_4 ； 步驟 s[l]_2:執行 c [χ-m+l] = c[x-m+l] ~b[l],然後執行步驟 s
_0 ;步驟 s [1]_3:執行 c [m_l] = c [m—1] ~b [m_l]、c [m_2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l] ~b[l]、c
= c
~b
操作，然後執行步驟 s[l]_0 ；步驟s[l]_4:執行update_c (χ-m+l),然後執行步驟s
_0 ； 步驟s
_0:判斷b
是否為1，若b
為I則執行步驟s
_l，否則函數update_C(X)結束； 步驟s
_l:比x-m值與m值,若χ-m小於m,則執行步驟s
_2 ;若χ-m等於m,則執行步驟s
_3 ;若x-m大於m ,則執行步驟s
_4 ； 步驟 s
_2:執行 c [x-m] = c[x_m] ~b
,然後函數 update_c(x)結束；步驟 s
_3:執行 c [m_l] = c [m-1] 'b [m-1] > c [m-2] = c [m_2] ~b [m_2]、c [m_3]=c[m-3] ~b[m-3]...c[l] = c[l]~b[l]、c
= c
~b
操作，然後函數 update_c (x)結束； 步驟 s
_4:執行 update_c (χ-m),函數 update_c (x)更新數組 c [m]結束。
3.如權利要求1所述的計算伽羅華域本原元正整數次冪的方法，其特徵在於，調用函數update_c(x)前預先將數組c[m]初始化為O。
4.如權利要求1所述的計算伽羅華域本原元正整數次冪的方法，其特徵在於，採用通用處理器，以計算伽羅華域本原元正整數次冪。
5.如權利要求1所述的計算伽羅華域本原元正整數次冪的方法，其特徵在於，通過與門、異或門來實現硬體構建，以計算伽羅華域本原元正整數次冪。
全文摘要
本發明涉及信息安全技術中的代數編解碼領域，具體公開一種計算伽羅華域本原元正整數次冪的方法，包括預先構造遞歸函數update_c(x)，該遞歸函數update_c(x)用以根據本原多項式中最高次冪m和係數數組b[m]的值計算與本原元正整數次冪αn對應多項式表達係數數組c[m]的值；以n為參數，執行該遞歸函數update_c(x)，用以獲取數組c[m]的值；根據表達式αn＝c[m-1]αm-1+c[m-2]αm-2+c[m-3]αm-3+...+c[1]α+c
進行計算，用以獲取本原元正整數次冪αn的計算結果。本發明無需存儲數組c[m]元素，有利於節省存儲空間。
文檔編號G06F17/15GK103186504SQ20111046032
公開日2013年7月3日 申請日期2011年12月30日 優先權日2011年12月30日
發明者冷永春, 胡勝發 申請人:安凱(廣州)微電子技術有限公司