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

有效

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

本發明公開了一種快速模乘和模平方電路及其實現方法，該電路由一組m位的左移三位移位寄存器QU，三組m位的二輸入與門陣列AND1、AND2、AND3，四組全加器陣列FA1、FA2、FA3、FA4，m+4位的結果寄存器Q和一個32×m位的ROM單元組成，能對夠對m位的二進制大數進行乘法或平方的同時對大素數P進行模約減，在每一個時鐘周期內處理3位，經過m/3+2個時鐘周期就能得到模乘和模平方的結果，若m不是3的倍數可以通過對其高位補0直至其為3的倍數。

技術領域

本發明涉及集成電路設計領域，涉及一種用于大數模乘和模平方的快速模約減電路，特別涉及一種快速模乘和模平方電路及其實現方法。

背景技術

目前對于大數模乘和模平方的模約減過程，通常采用的方案是先計算出乘法和平方的結果再對大素數P進行取模操作，這個過程中就需要專門的取模電路，而一般乘法或平方的結果的數據位寬是P的2倍，因此對大數來說其乘法或平方的取模模塊需要的電路面積很大，運算速度慢，電路功耗還很大。

發明內容

本發明提供了一種快速模乘和模平方電路及其實現方法，該電路能對夠對m位的二進制大數進行乘法或平方的同時對大素數P進行模約減，在每一個時鐘周期內處理3位，經過m/3+2個時鐘周期就能得到模乘和模平方的結果，若m不是3的倍數可以通過對其高位補0直至其為3的倍數。

為實現上述目的，本發明采用以下技術方案：

一種快速模乘和模平方電路，包括：一組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，

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

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

四組全加器陣列的最低位進位端連接到0，同時針對電路第m位加法陣列的進位再用五個全加器單元處理，并將其每一級電路運算的結果鎖存到結果寄存器Q中。

ROM單元的4位地址線Adder從高到低為{Q[m+4],Q[m+3],Q[m+2],Q[m+1]}。

ROM單元為32×m位的ROM單元。

一種基于快速模乘和模平方電路的實現方法，其特征在于，包括以下步驟：

首先需要初始化輸出寄存器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位。