[發明專利]一種快速模乘和模平方電路及其實現方法

有效

• 申請號: 201710039195.4
• 申請日: 2017-01-19
• 公開（公告）號: CN106873941B
• 公開（公告）日: 2019-05-21
• 發明（設計）人: 李春泉;雷紹充;趙重陽;彭星宇;張云龍
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F7/523
• 分類號: G06F7/523;G06F7/552
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 張弘

1.一種快速模乘和模平方電路，其特征在于，包括：一組m位的左移三位移位寄存器QU，三組m位的二輸入與門陣列AND1、AND2、AND3，四組全加器陣列FA1、FA2、FA3、FA4，m+4位的結果寄存器Q和一個32×m位的ROM單元；其中，

m位的左移三位移位寄存器QU，用于存放乘數，并將其第m位命名為U2，第m-1位命名成U1，第m-2位命名成U0；

二輸入與門陣AND1輸入端為U2與被乘數N左移2位的結果；二輸入與門陣AND2輸入端為U1與被乘數N左移1位的結果；二輸入與門陣AND3輸入端為U0與被乘數N；

ROM單元，用于存放素數P的補碼Pb的特定倍數，其輸出端口設為X；ROM單元的4位地址線Adder從高到低為{Q[m+4],Q[m+3],Q[m+2],Q[m+1]}，特定倍數是指4位地址線Adder與素數P的補碼Pb的乘積；

全加器陣列，用于產生部分積，其中全加器陣列FA1的兩個輸入分別為與門陣列AND1的輸出端和與門陣列AND2的輸出端，全加器陣列FA2的輸入端分別為與門陣列AND3的輸出端和ROM的輸出端X，全加器陣列FA3的輸入端分別為全加器陣列FA1和FA2的和端口，全加器陣列FA4的輸入端為結果寄存器Q左移三位的結果與全加器陣列FA3的和端口；

m+4位的結果寄存器Q，用于存放運算過程中的部分積和最終的結果，其輸入與全加器陣列FA4的和端口相連，其高四位輸出連接到ROM的地址位，低m位通過左移三位連接到全加器陣列FA4的加數端口。

2.根據權利要求1所述的快速模乘和模平方電路，其特征在于：四組全加器陣列的最低位進位端連接到0，同時針對電路第m位加法陣列的進位再用五個全加器單元處理，并將其每一級電路運算的結果鎖存到結果寄存器Q中。

3.一種基于權利要求1所述的快速模乘和模平方電路的實現方法，其特征在于，包括以下步驟：

首先需要初始化輸出寄存器Q，將RS＝0，寄存器全部復位為0；工作中RS＝1，電路運行m/3個clk后，被乘數的所有位均已經參與了運算，這時左移三位寄存器N全部為0，下一步只需約減掉Q[m+4]、Q[m+3]、Q[m+2]、Q[m+1]這四位即可；電路繼續運行2個clk，Qm的高四位被成功約減掉；乘法和平方的運算結果被約減到m位。

4.根據權利要求3所述的快速模乘和模平方電路的實現方法，其特征在于，在每一個時鐘周期內處理3位，經過m/3+2個時鐘周期得到模乘和模平方的結果，若m不是3的倍數則通過對其高位補0直至其為3的倍數。