[發明專利]蒙哥馬利算法的模乘器和電子設備

有效

• 申請號: 202011555981.8
• 申請日: 2020-12-25
• 公開（公告）號: CN112286496B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 郝志剛
• 申請（專利權）人: 九州華興集成電路設計（北京）有限公司
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 霍文娟

1.一種蒙哥馬利算法的模乘器，其特征在于，包括M個依次連接的處理單元，每個所述處理單元中包括至少一個加法器，所述模乘器中的所述加法器的總數為M+1個，多個所述處理單元由依次連接的一個第一處理單元和多個其他處理單元組成，其中，

所述第一處理單元的輸入包括第一輸入段、第二輸入段、第三輸入段和第四輸入段，所述第一處理單元的輸出為第一加和的進位、第一乘積的高K位和第二乘積的高K位，所述第一乘積為第一輸入段和第二輸入段的乘積，所述第一輸入段為所述模乘器的第一輸入數據的一段，所述第一輸入數據分為m段且每段為K位，所述第二輸入段為所述模乘器的第二輸入數據的第一段，所述第二輸入數據分為m段且每段為K位，所述第二乘積為所述第三輸入段和所述第四輸入段的乘積，所述第三輸入段為所述模乘器的第三輸入數據的第一段，所述第三輸入數據分為m段且每段為K位，所述第四輸入段為所述第二輸入段與第一預定值的比值，所述第一加和為所述第一乘積的低K位、所述第二乘積的低K位以及第二預定值的低K位的和，m和K均為正整數且均大于1；

所述其他處理單元的輸入包括所述第一輸入段、第一預定段、第二預定段、第四輸入段、第一初始加和的進位、第一初始乘積的高K位和第二初始乘積的高K位，所述第一預定段為輸入至前一個所述處理單元的所述第二輸入數據的下一段、所述第二預定段為輸入至前一個所述處理單元的所述第三輸入數據的下一段，所述其他處理單元的輸出為第一預定乘積的高K位、第二預定乘積的高K位、預定加和的低K位以及所述預定加和的進位，所述第一預定乘積為所述第一輸入段和所述第一預定段的乘積，所述第二預定乘積為所述第二預定段和所述第四輸入段的乘積，所述預定加和為所述第一預定乘積的低K位、所述第二預定乘積的低K位、所述第一初始加和的進位、所述第一初始乘積的高K位和所述第二初始乘積的高K位的和，在所述其他處理單元的前一個所述處理單元為所述第一處理單元時，所述第一初始加和為所述第一加和，在所述其他處理單元的前一個所述處理單元為所述其他處理單元時，所述第一初始加和為前一個所述其他處理單元對應的所述預定加和，所述第一初始乘積為前一個所述處理單元得到的所述第一預定乘積，所述第二初始乘積為前一個所述處理單元得到的所述第二預定乘積，最后一個所述處理單元的輸出還包括最后一個所述處理單元得到的所述第一預定乘積的高K位、所述第二預定乘積的高K位以及所述預定加和的進位的和。

2.根據權利要求1所述的模乘器，其特征在于，所述第一處理單元包括：

第一乘法器，用于計算所述第一輸入段和所述第二輸入段的乘積且得到所述第一乘積；

第二乘法器，用于計算所述第三輸入段和所述第四輸入段的乘積且得到所述第二乘積；

第一加法器，所述第一加法器的輸入端與所述第一乘法器的輸出端、所述第二乘法器的輸出端分別電連接，所述第一加法器用于計算所述第一乘積的低K位、所述第二乘積的低K位以及所述第二預定值的低K位的和且得到所述第一加和。

3.根據權利要求2所述的模乘器，其特征在于，所述第一加法器包括：

K個第一一位全加器，所述第一一位全加器的輸入端與所述第一乘法器的輸出端以及所述第二乘法器的輸出端分別連接，一個所述第一一位全加器用于計算所述第一乘積的低K位中的第Q位、所述第二乘積的低K位的第Q位以及所述第二預定值的低K位的第Q位的和，其中，1≤Q≤K，所述第一一位全加器的輸出為第一本位的和位和第一向前一級的進位；

第一K位全加器，所述第一K位全加器的輸入端與各所述第一一位全加器的輸出端分別電連接，所述第一K位全加器用于對K個所述第一一位全加器的輸出進行K位全加，得到所述第一加和。

4.根據權利要求1所述的模乘器，其特征在于，所述其他處理單元包括：

第三乘法器，用于計算所述第一輸入段和所述第一預定段的乘積，且得到所述第一預定乘積；

第四乘法器，用于計算所述第四輸入段和所述第二預定段的乘積，且得到所述第二預定乘積；

第二加法器，所述第二加法器的輸入端與所述第三乘法器、所述第四乘法器和前一個所述處理單元的輸出端分別連接，所述第二加法器用于計算所述第一預定乘積的低K位、所述第二預定乘積的低K位、所述第一初始加和的進位、所述第一初始乘積的高K位和所述第二初始乘積的高K位的和，并得到所述預定加和。