[發(fā)明專利]用于大數乘法的方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 200880102372.8
• 申請日: 2008-08-08
• 公開（公告）號: CN101790718A
• 公開（公告）日: 2010-07-28
• 發(fā)明（設計）人: 文森特·杜帕丘斯;拉塞爾·霍布森
• 申請（專利權）人: 愛特梅爾公司
• 主分類號: G06F7/00
• 分類號: G06F7/00
• 代理公司: 北京律盟知識產權代理有限責任公司 11287
• 代理人: 孟銳

技術領域

本發(fā)明涉及信息管理。

背景技術

(例如)固態(tài)裝置中的常規(guī)乘法硬件可具有大小限制，例如，可由所述硬件同時 處置的規(guī)定數目的位。通常，乘法硬件被定義為具有一對單字操作數輸入及雙字結果 輸出。為實施相乘-累加運算，乘法器輸出可連接到累加器，所述累加器通常為至少雙 字加一位寬。在運算的累加部分中，補充位可為結果的一部分，或僅作為進位信息而 存在，所述進位信息指示加法情況中的溢出或減法情況中的下溢。

在密碼及其它應用中，需要將包含大量字的極大整數相乘。為使用比乘法硬件寬 得多的操作數執(zhí)行這些運算，可將所述操作數分成單字寬的段并以某一規(guī)定序列饋送 到所述硬件中。對所述段進行運算并累加中間結果，使得將最終乘積作為各個權數的 叉積的和來計算。字寬操作數段以及部分結果存儲于由乘法器硬件的操作定序器尋址 的存儲器中。舉例來說，序列可保持第一操作數的段恒定，同時一次一個字地將所述 操作數的段掃描到乘法器中，接著所述第一操作數遞增到下一字寬段且重復對第二操 作數的掃描。

發(fā)明內容

本發(fā)明涉及大數乘法。一般來說，在一個方面中，本發(fā)明的特色在于一種用于操 作乘法電路來計算兩個操作數(A與B)的乘積的計算機實施的方法、系統(tǒng)及計算機 程序產品，所述兩個操作數中的至少一者寬于與所述乘法電路相關聯(lián)的寬度。所述操 作數中的每一者包括以特定權數j及i為特征的一個或一個以上相連的有序字寬操作數 段(A_j及B_i)，其中j是從0到k的整數，其中i是從0到m的整數，且字是規(guī)定數 目的位(n)。所述乘法電路執(zhí)行字寬操作數段對乘法運算矩陣，所述矩陣包含m+1 個行及k+m+2個列，每一行具有權數x且每一列具有權數y。所述乘法電路可存取存 儲器。同時對一對行執(zhí)行乘法運算。對于每一對行，從所述存儲器讀取一對對應B_i字寬操作數段且針對k+2個列中的每一者反復地執(zhí)行字寬操作數段對乘法運算 (A_j*B_i)，使得對于所述矩陣中的每一列，需要最多兩個額外存儲器讀取操作及一個 存儲器寫入操作揭示其它實施方案。

本發(fā)明的實施方案可實現以下優(yōu)點中的一者或一者以上。本文中所描述的乘法電 路可同時計算一對行同時每列僅需要三個存儲器存取(2個讀取與1個寫入)(除了 對應于每一行的字寬操作數段的初始讀取以外)，從而使得將更高效的存儲器接口設 計為單個雙端口RAM或兩個單端口RAM成為可能。另一優(yōu)點是可不按序列地計算若 干對行。隨機化行計算的次序可提供對所述計算中所正使用的敏感數據的經改進的保 護。由于減少的存儲器存取，所述乘法電路的功率消耗可低于其它常規(guī)電路。

將在附圖及以下說明中闡述本發(fā)明的一個或一個以上實施例的細節(jié)。依據說明、 圖式并依據權利要求書將明了本發(fā)明的其它特征、目的及優(yōu)點。

附圖說明

圖1是顯示乘法電路的實例的框圖。

圖2是第一實例性乘法矩陣的示意性表示。

圖3是顯示用于根據圖2的乘法矩陣計算兩個操作數的乘積的實例性過程的流程 圖。

圖4是第二實例性乘法矩陣的示意性表示。

在各圖式中，相同的參考符號指示相同的元件。

具體實施方式

某些應用需要將大于用于計算結果的硬件的機器大小的數相乘在一起。舉說明性 實例來說，可需要具有32個位的機器大小的微處理器計算具有128位輸入操作數的乘 法的結果。由于輸入數據大于所述微處理器的機器大小，因此所述輸入數據可存儲于 RAM或另一類似臨時存儲存儲器中或者可駐留于在所述微處理器內部的高速緩沖存 儲器或寄存器中。假定兩個128位輸入操作數A及B，其存儲于RAM中且將由32位 微處理器對其進行運算，其中：

A＝0x11111111222222223333333344444444；且

B＝0x55555555666666667777777788888888；

其中0x表示十六進制數；

可將計算分解成機器大小字，在此實例中，為32位字寬操作數段，如下：

A＝A₀+A₁*2³²+A₂*2⁶⁴+A₃*2⁹⁶；且