[發明專利]一種基于多次平方運算的復合有限域求逆器及其求逆方法有效
| 申請號： | 201810698830.4 | 申請日： | 2018-06-29 |
| 公開（公告）號： | CN108897526B | 公開（公告）日： | 2022-10-21 |
| 發明（設計）人： | 易海博;聶哲 | 申請（專利權）人： | 深圳職業技術學院 |
| 主分類號： | G06F7/72 | 分類號： | G06F7/72 |
| 代理公司： | 廣州市華學知識產權代理有限公司 44245 | 代理人： | 陳文姬 |
| 地址： | 518055 廣東省深*** | 國省代碼： | 廣東;44 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 基于 多次 平方 運算 復合 有限 域求逆器 及其 方法 | ||
1.一種基于多次平方運算的復合有限域求逆器，其特征在于，包括：
運算控制器，用于控制輸入輸出和調用與其相連的部件計算有限域GF((2n)2)；
輸入端口，包括用于輸入復合有限域GF((2n)2)的求逆運算數a(x)的端口a、用于輸入時鐘信號t的端口clk、用于輸入復合有限域GF((2n)2)的不可約多項式q(x)的端口q和用于輸入子域GF(2n)的不可約多項式p(x)的端口p；
輸出端口，包括用于輸出復合有限域GF((2n)2)的求逆運算結果b(x)的端口b；
加法運算陣列模塊，用于計算多個子域GF(2n)加法；
乘法運算陣列模塊，用于計算多個子域GF(2n)乘法；
平方運算陣列模塊，用于計算多個子域GF(2n)平方；
所述運算控制器分別與輸入端口、輸出端口、加法運算陣列模塊、乘法運算陣列模塊和平方運算陣列模塊連接；
所述輸入端口的運算數a(x)由兩個n比特的數ah,al組成，表示成多項式的形式：
a(x)＝ahx+al，
ah,al是有限域GF(2n)的元素；
所述輸入端口的運算數a(x)表示成系數的形式：
a(x)＝a(ah,al)，
ah,al是有限域GF(2n)的元素；
所述輸入端口的時鐘信號t是單比特信號，取值是0或1，代表低電平或高電平；低電平轉向高電平代表一個時鐘周期的開始；
所述輸入端口的復合有限域GF((2n)2)的不可約多項式q(x)，表示成多項式的形式：
q(x)＝x2+x+e，
e是有限域GF(2n)的常數；
所述輸入端口的子域GF(2n)的不可約多項式p(x)，表示成多項式的形式：
p(x)＝xn+pn-1xn-1+pn-2xn-2+...+p1x+1，
pn-1,pn-2,...,p1是有限域GF(2)的元素，即二進制數(0)2和(1)2中的一個數；
所述輸入端口的子域GF(2n)的元素c(x)，表示成多項式的形式：
c(x)＝cn-1xn-1+cn-2xn-2+...+c0，
cn-1,cn-2,...,c0是有限域GF(2)的元素，即二進制數(0)2和(1)2中的一個數；
所述輸入端口的子域GF(2n)的元素c(x)，表示成系數的形式：
c(x)＝c(cn-1,cn-2,...,c0)，
cn-1,cn-2,...,c0是有限域GF(2)的元素，即二進制數(0)2和(1)2中的一個數；
所述輸出端口的運算數b(x)由兩個n比特的數bh,bl組成，表示成多項式的形式：
b(x)＝bhx+bl，
bh,bl是有限域GF(2n)的元素；
所述輸出端口的運算數b(x)表示成系數的形式：
b(x)＝b(bh,bl)，
bh,bl是有限域GF(2n)的元素；
所述加法運算陣列模塊包含多個加法查找樹結構，用于計算GF(2n)的兩個已知元素f(x),g(x)的加法h(x)＝f(x)+g(x)，其中，
f(x)＝fn-1xn-1+fn-2xn-2+...+f0，
g(x)＝gn-1xn-1+gn-2xn-2+...+g0，
h(x)＝hn-1xn-1+hn-2xn-2+...+h0，
fn-1,fn-2,...,f0,gn-1,gn-2,...,g0,hn-1,hn-2,...,h0是有限域GF(2)的元素；
計算h(x)＝f(x)+g(x)使用加法查找樹結構，描述如下：
查找樹結構包含兩顆查找樹，每顆樹包含n層，把最上面一層，即根節點所在的層稱為第0層，則最下面一層，即葉子節點所在的層是第n-1層，n≥1；
擴展層在查找樹的葉子節點下的一層，擴展層的每個節點與三個葉子節點相連；
所有樹節點除了葉子節點均有左孩子節點和右孩子節點；
左節點代表數值0，右節點代表數值1；
每一條從根節點到一個葉子節點的路徑分別代表一個GF(2n)的元素；
若GF(2n)的加法h(x)＝f(x)+g(x)，并且從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)，從第0層到第n-1層的節點ng的路徑代表GF(2n)的元素g(x)，則第n-1層的節點nf和ng與擴展層的節點ns相連；若從第0層到第n-1層的節點nh的路徑代表GF(2n)的元素h(x)，則第n-1層的節點nh與擴展層的節點ns相連；
所述加法運算陣列模塊計算h(x)＝f(x)+g(x)的步驟如下：
首先，對于f(x)＝fn-1xn-1+fn-2xn-2+...+f0，判斷從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)；
然后，對于g(x)＝gn-1xn-1+gn-2xn-2+...+g0，從第0層到第n-1層的節點ng的路徑代表GF(2n)的元素g(x)；
若第n-1層的節點nf和ng與擴展層的節點ns相連，并且第n-1層的節點nh與擴展層的節點ns相連，則從第0層到第n-1層的節點nh的路徑代表的GF(2n)的元素是h(x)＝f(x)+g(x)，即是h(x)＝f(x)+g(x)的運算結果；
所述乘法運算陣列模塊包含多個乘法查找樹結構，用于計算GF(2n)的兩個已知元素f(x),g(x)的乘法h(x)＝f(x)×g(x)，其中，
f(x)＝fn-1xn-1+fn-2xn-2+...+f0，
g(x)＝gn-1xn-1+gn-2xn-2+...+g0，
h(x)＝hn-1xn-1+hn-2xn-2+...+h0，
fn-1,fn-2,...,f0,gn-1,gn-2,...,g0,hn-1,hn-2,...,h0是有限域GF(2)的元素；
計算h(x)＝f(x)×g(x)使用乘法查找樹結構，描述如下：
查找樹結構包含兩顆查找樹，每顆樹包含n層，把最上面一層，即根節點所在的層稱為第0層，則最下面一層，即葉子節點所在的層是第n-1層；
擴展層在查找樹的葉子節點下的一層，擴展層的每個節點與三個葉子節點相連；
所有樹節點除了葉子節點均有左孩子節點和右孩子節點；
左節點代表數值0，右節點代表數值1；
每一條從根節點到一個葉子節點的路徑分別代表一個GF(2n)的元素；
若GF(2n)的乘法h(x)＝f(x)×g(x)，并且從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)，從第0層到第n-1層的節點ng的路徑代表GF(2n)的元素g(x)，則第n-1層的節點nf和ng與擴展層的節點ns相連；若從第0層到第n-1層的節點nh的路徑代表GF(2n)的元素h(x)，則第n-1層的節點nh與擴展層的節點ns相連；
所述乘法運算陣列模塊計算h(x)＝f(x)×g(x)的步驟如下：
首先，對于f(x)＝fn-1xn-1+fn-2xn-2+...+f0，查找從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)；
然后，對于g(x)＝gn-1xn-1+gn-2xn-2+...+g0，查找從第0層到第n-1層的節點ng的路徑代表GF(2n)的元素g(x)；
若第n-1層的節點nf和ng與擴展層的節點ns相連，并且第n-1層的節點nh與擴展層的節點ns相連，則從第0層到第n-1層的節點nh的路徑代表的GF(2n)的元素是h(x)＝f(x)×g(x)，即是h(x)＝f(x)×g(x)的運算結果；
所述平方運算陣列模塊，包含多個平方查找樹結構，用于計算GF(2n)的已知元素f(x)的乘法h(x)＝f(x)2，其中，
f(x)＝fn-1xn-1+fn-2xn-2+...+f0，
h(x)＝hn-1xn-1+hn-2xn-2+...+h0，
fn-1,fn-2,...,f0,hn-1,hn-2,...,h0是有限域GF(2)的元素；
計算h(x)＝f(x)2使用平方查找樹結構，描述如下：
查找樹結構包含兩顆查找樹，每顆樹包含n層，把最上面一層，即根節點所在的層稱為第0層，則最下面一層，即葉子節點所在的層是第n-1層；
所有樹節點除了葉子節點均有左孩子節點和右孩子節點；
左節點代表數值0，右節點代表數值1；
每一條從根節點到一個葉子節點的路徑分別代表一個GF(2n)的元素；例如，由左根節點開始，包括左根節點的左孩子節點、左根節點的左孩子節點的左孩子節點等節點，直到最左邊的葉子節點結束的路徑代表GF(2n)的元素(00...00)2；
若GF(2n)的平方h(x)＝f(x)2，并且從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)，從第0層到第n-1層的節點nh的路徑代表GF(2n)的元素h(x)，則第n-1層的節點nf與節點nh相連；
計算h(x)＝f(x)2的步驟如下：
首先，對于f(x)＝fn-1xn-1+fn-2xn-2+...+f0，判斷從第0層到第n-1層的節點nf的路徑代表GF(2n)的元素f(x)；
若第n-1層的節點nf與節點nh相連，則從第0層到第n-1層的節點nh的路徑代表的GF(2n)的元素是h(x)＝f(x)2，即是h(x)＝f(x)2的運算結果。
2.基于權利要求1所述基于多次平方運算的復合有限域求逆器的復合有限域求逆方法，其特征在于，計算GF((2n)2)的求逆b(x)＝a(x)-1的步驟如下：
等待時鐘信號t由低電平轉向高電平；第一步，計算a′(x)＝a(x)2；第二步，令b(x)＝a′(x)，計算a″(x)＝a′(x)2；第三步，計算b(x)＝b(x)a″(x)，并計算a″′(x)＝a″(x)2；第四步，計算b(x)＝b(x)a″′(x)，并計算a″″(x)＝a″′(x)2；直到第2n步完成計算b(x)；
計算GF((2n)2)的求逆b(x)＝a(x)-1完成后，將b(x)輸出至輸出端口b。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于深圳職業技術學院，未經深圳職業技術學院許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201810698830.4/1.html，轉載請聲明來源鉆瓜專利網。
