[發明專利]一種基于改進的Montgomery模乘算法的可擴展模乘器電路

有效

• 申請號: 201410145671.7
• 申請日: 2014-04-14
• 公開（公告）號: CN103914277B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 韓軍;竇仁峰;曾凌云;曾曉洋
• 申請（專利權）人: 復旦大學
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 上海正旦專利代理有限公司31200
• 代理人: 陸飛,王潔平

1.一種基于改進的Montgomery模乘算法的可擴展模乘器電路，其特征在于：

其主要由部分積產生電路、第一級PCSA壓縮樹、第二級PCSA壓縮樹、部分積反饋電路、模乘器擴展相關電路和時序控制器構成；其中：

所述部分積產生電路由若干個單個部分積產生電路構成，其在時序控制器的控制信號下，根據寄存器B、寄存器B+M₂、寄存器M₂、寄存器M₁、以及寄存器A和寄存器Q的輸出，產生相應的操作數高半部分或者低半部分的的部分積并送給第一級PCSA壓縮樹的輸入端；??

所述第一級PCSA壓縮樹在時序控制器產生的控制信號控制下對部分積產生電路所產生的部分積進行壓縮，并將壓縮后的結果送到流水線寄存器進行寄存；

所述第二級PCSA壓縮樹在時序控制器產生的控制信號控制下，對寄存后的部分積、部分積反饋電路產生的部分積、以及加法器產生的進位信號進行壓縮，并把壓縮后的結果送到相應的結果寄存器進行保存；

所述部分積反饋電路根據結果寄存器以及擴展信號中的?S值輸入在時序控制器的控制下產生用于反饋的部分積，并把其送到第二級PCSA壓縮樹的輸入端；

所述模乘器擴展相關電路包括引出的數據線接口、部分積反饋電路中的部分邏輯、以及加法器和復用器；用于擴展的S值輸入直接接入到部分積反饋電路模塊，經過寄存器寄存后送給復用器；加法器對結果寄存器中的低部分比特進行累加實現Q值的計算，其進位值送給第二級PCSA壓縮樹，其輸出直接引出作為用于擴展的S值輸出信號；加法器的輸出經過寄存器Q’寄存后作為用于擴展的Q值輸出；外部輸入的用于擴展的Q值和寄存器Q’的值通過復用器進行選擇并送給寄存器Q進行寄存；作為部分積產生電路的輸入信號。

2.根據權利要求1所述的基于改進的Montgomery模乘算法的可擴展模乘器電路，其特征在于：所述第一級和第二級PCSA壓縮樹由若干個流水線進位保存加法器經過一定的樹狀連接構成；流水線進位保存加法器主要由[N/2]+1比特的進位保存加法器和一個進位寄存器構成；[N/2]+1比特的進位保存加法器的輸入為三個操作數的高半部分或者低半部分數據；[N/2]+1比特的進位保存加法器的進位輸出C_H/C_L的最高位，C_MSB經過一個一比特的寄存器進行寄存；寄存后的C_MSB拼接到C_H/C_L-信號的最低位用作PCSA的C_H/C_L輸出，對于進位保存加法器的S_H/S_L的輸出直接作為PCSA的C_H/C_L輸出。

3.根據權利要求1或2所述的基于改進的Montgomery模乘算法的可擴展模乘器電路，其特征在于，所述改進的Montgomery模乘算法基于原始商流水Montgomery模乘算法增加了一個用于運算的參數????????????????????????????????????????????????，該參數通過下面方法獲得：

新增的參數用于

其中，M為模乘中的模數，k為模乘的基；改進算法中的與原始算法中的相同；S_n+1與S_n+2為迭代運算中的運算結果，Q_n為第n次迭代的Q值。