蒙哥馬利模數乘法器及其方法
2023-04-23 21:53:46
專利名稱：蒙哥馬利模數乘法器及其方法
技術領域：
本發明涉及密碼系統的領域，尤其涉及蒙哥馬利模數乘法器。
背景技術：
由於網絡系統使用的增長，所以網絡通信的保護變得更為重要。對數據的整體性和保密性的保護成為一個問題。
代碼傳送和對消息進行解碼的基本過程包括獲得消息(明碼文本)、調整(加密)該明碼文本為(密文)、向接收器發送密文、以及解調(解密)該密文以恢復原始的消息。
在密碼系統中，使用加密匙來對明碼文本進行加密。將所述密文發送到接收器，並且接收器使用解密匙對密文進行解密，然後回到原始的明碼文本。所述加密匙和解密匙經常稱作密匙對。
例如，公共和私有密匙對可以是兩個或多個大的質數的函數。每個函數(加密和解密)依賴於大的質數，並且被稱作密匙對。對於整個系統(加密和解密)存在兩個密匙對(P，Q)。為了加強安全性，可以選擇相等的P和Q字長，以便根據比特長度不能夠區別它們，接著計算乘積MM＝P*Q (1)隨機地選擇加密匙KE，以便KE和(P-1)(Q-1)是互質數。所以，能夠使用滿足下列等式的擴展的歐幾裡得算法來計算解密匙KDKD=KE-1mod((P-1)(Q-1))---(2)]]>數字KD和M也可以是互質數。這些數字(KE和M)可以是用來對數據加密的加密匙(或公共密匙)，以及數字(KD和M)是用來對數據解密的解密匙。在生成密匙後，通過執行下列計算對原始消息進行加密。
C=TKEmodM---(3)]]>
其中T是原始消息(明碼文本)，C是加密的消息(密文)。為了對加密的數據進行解密，進行下列計算T=CKDmodM---(4)]]>其中T′是解密的消息。T′應該與原始消息T相同。如所能夠知道的，執行幾個模數乘法。
在一些加密系統中，通常，多於512比特的長的字長常用來滿足安全的需要。然而，長的字長限止了快速執行，要求增加計算速度。為了計算的速度，快指數計算變得愈加重要。存在幾種方法，例如，H-算法、L-算法等，這些方法能夠用來加速指數計算。一種這樣的算法是蒙哥馬利模數乘法算法，其能夠在高執行指數計算算法中用作核心運算。蒙哥馬利模數乘法算法也提高了加密和解密運算的效率。
提供蒙哥馬利模數乘法算法來計算結果的n位數R＝A*B*r-1modM， (其中，基數r＝2n) (5)在模數指數算法中要求，其中A、B和M分別是被乘數、乘數以及模數，並且每個具有n位。示例的基數2蒙哥馬利迭代模數乘法算法是S0＝0；for(I＝0；I＜N；I++){qI＝(SI+bIA)mod2；SI+1＝(SI+bIA+qIM)/2；}if(SN＞＝M)SN＝SN-M；其中bIA(＝PPI)是部分乘積；qIM(＝MMI)是模數倍數，其使(SI+PPI)的一個最低位(LSB)成為零(0)值；N是模數M的位長；SI是先前周期的部分累加結果；SI+1是具有N位的當前周期的部分累加結果；以及SN是最終計算結果。示例的基數4蒙哥馬利迭代模數乘法算法是S0＝0；for(I＝0；I＜N；I++){qI＝(((SI+bIA)mod4)*M′)mod4；SI+1＝(SI+bIA+qIM)/4；}if(SN＞＝M)SN＝SN-M；其中N＝n/2。基數2和基數4的過程是生成迭代數據的迭代過程；該數據的值隨著在I＝0；I＜N；I++循環內的迭代而變化。模數的運算速度影響系統性能。所以，如果位長非常長，則系統性能下降。為了計算MMI(＝qIM)，首先計算PPI＝(bIA)，然後相加所計算的PPI和SI。所以，由於累加器執行兩次邏輯計算，因此增加了功耗。
圖1示出了傳統的蒙哥馬利模數乘法算法的硬體實現，其利用兩個進位傳送加法器91和92(其後縮寫為CPA)。第一個CPA 91用作乘法運算，其接收先前的計算結果和從與邏輯電路93輸出的ai和B進行與運算的結果，該與邏輯電路93接收ai和B。第二個CPA 92用於模數運算，其接收第一個CPA 91的輸出結果和來自與邏輯電路94的qi和N與運算的結果。使用移位器95使CPA 92的輸出向右移1位，以便將輸出結果除2，從而生成一次迭代的計算結果。
為了完成512位蒙哥馬利模數乘法，要進行512次迭代，則花費高的時間代價。結果，512位RSA加密/解密的速度仍然低於當前網絡傳輸帶寬的速度。
蒙哥馬利模數乘法可能是耗時的並影響在包括密碼計算器件的數字設備中的運算。為了生產高性能的數字設備，提高模數運算的速度通常是必要的。
除了速度，另外所關注的是功耗。期望較低的功耗，例如，在智慧卡和移動產品中，低功耗尤為重要。智慧卡和移動產品使用密碼計算器件來使數據安全，並且提高器件的效率能夠改善這些器件的功耗特性。附加計算的器件消耗許多功率，並且大部分功率是由模數乘法消耗的。尤其，當位長增加時，模數運算中要求更多的功率。
發明內容
本發明的示例性實施例提供了通過使用流水線型寄存器和/或處理數據到達累加器的時間來加速蒙哥馬利模數乘法的速度和/或減小了功耗的方法。
在本發明的實施例中，流水線型方法能夠用在蒙哥馬利乘法器的布期重編碼器中來加快蒙哥馬利模數乘法的速度。
在本發明的實施例中，在累加器上第I次迭代的部分乘積(PPI)的到達和第I次迭代的模數倍數(MMI)幾乎同時到達，蒙哥馬利模數乘法中有助於減小功耗，從而，減少了加法器的計算運算。
在本發明的實施例中，反饋寄存器的使用減少了多路復用運算的數量。如果選擇當前迭代的部分乘積PPI或模數倍數MMI值為「0」，其中「0」意味著該值不必進行相加，在沒有多路復用運算的情況下使用先前迭代的值。從而，沒有必要進行多路復用運算(其中多路復用運算數量是大於「n」)。
在本發明的實施例中，減小了平均漢明間距，其中漢明間距是相同的位位置的不同值的數量。從而，較少的位變化能夠導致減少輸出端的加載。
其後所提供的詳細說明將使本發明的實施例的進一步可應用的範圍變得明顯。應該理解詳細的說明和特定的示例，同時表示本發明的示例性實施例僅確定為說明的目的並不意味著限制本發明的範圍。
根據詳細的說明和附圖，本發明的實施例將變得完全可理解。
圖1是蒙哥馬利模數乘法算法的背景技術硬體實現的圖解；圖2是本發明的示例性實施例的模數乘法器的圖解；圖3是本發明的示例性實施例中說明模數MMI的倍數的選擇標準的表格；圖4是本發明的示例性實施例中說明部分乘積PPI的選擇標準的表格；圖5是本發明的示例性實施例中基數2模數乘法器的圖解。
具體實施例方式
下列示例性實施例的說明實際上僅僅是說明性的，並不意味著限制本發明、它的應用或使用。
圖2是本發明示例性實施例的模數乘法器1000的圖解。乘法器1000能夠包括存儲在寄存器1中的模數(M)、存儲在寄存器3中的被乘數(A)、存儲在寄存器7中的乘數(B)、布期處理器301、模數處理器300、輔助模數倍數MMI計算的多路復用器(MUX)10、輔助部分乘積PPI計算的MUX 20、以及輔助模數乘法計算的累加器100。累加器100輸入部分乘積值PPI和模數倍數值MMI，並且產生用於蒙哥馬利乘法器的結果。在本發明的示例性實施例中，正值M能夠有n位(M[n-1:0])。正或負值A能夠有n+1位(A[n:0])，一位用於符號位。結果，B能夠是正或負。因此，如果n是偶數，則B具有n+2位，兩位是符號位，或者，如果n是奇數，則B具有n+1位，一位是符號位。
在本發明的實施例中，寄存器1提供模數M和M，其中M是M的補碼。同樣，寄存器3提供被乘數A和A，其中A是A的補碼。
如等式(5)所示，乘法器1000在迭代過程中對模數乘法求解。模數處理器300和多路復用器10用來選擇模數倍數(MMI)值。為了選擇MMI值，模數處理器300從累加器100接收迭代數據。迭代數據SPPI[1:0]是累加器的總記錄中的值的兩個LSB(SI[1:0])和部分乘積值的兩個LSB(PPI[1:0])的組合。SI[1:0]和PPI[1:0]在2位加法器40中進行組合以形成SPPI[1:0]。除了SPPI[1:0]，模數處理器300輸入模數的第二個有效位M[1]。模數處理器300使用SPPI[1:0]和M[1]來產生輸出信號，該輸出信號確定模數倍數MMI值的選擇。在本發明的另一示例性實施例中，SPPI值能夠是多於兩個值和/或位數的倍數的組合，此處所給的示例應當不限制本發明的範圍。
模數處理器300能夠輸出倍數信號(例如，模數倍數選擇信號SEL_MM[1:0]、模數倍數使能信號EN_MM、非模數倍數信號NEG_MM，...)。在本發明的示例性實施例中，模數處理器300向多路復用器10輸出SEL_MM[1:0]，該多路復用器10使用SEL_MM[1:0]的值來選擇MMI的值(例如，2M、M、0、-M，...)。多路復用器(MUX)10輸入模數M和模數倍數選擇信號的兩個LSB_SEL_MM[1:0]，並且輸出MMI值。非模數倍數信號NEG_MM和MMI在累加器100組合，其中NEG_MM用來表示位倒置，獲得-M的MMI值。
每個MUX運算消耗功率和能量，因此，當使用新的SEL_MM[1:0]值時，執行MUX運算以改變設置並選擇MMI值。在不改變設置中使用先前的SEL_MM[1:0]結果值，因此不進行MUX運算。在MMI的選擇中減少必要的MUX運算的數量將降低乘法器1000的整個功耗。
在本發明的示例性實施例中，模數處理器300還包括模數倍數反饋寄存器61和模數重編碼器70。反饋寄存器61存儲先前迭代的SEL_MM[1:0]值作為SEL_MM_D[1:0]值。當期望值MMI＝0的時，模數處理器300輸出值為0的模數倍數使能信號EN_MM。該信號EN_MM輸入到與門31。與門31輸入多路復用器10的輸出，該多路復用器10使用模數倍數選擇信號SEL_MM[1:0]的先前值，從而不使用MUX運算，並且與門31輸出MMI＝0的值。沒有MUX運算的MMI＝0的安排降低了乘法器1000的功耗。在圖3中示出了類似於上述的編碼方案。
圖3圖解說明了根據本發明的示例性實施例的編碼方案。儘管圖3示出了到模數重編碼器70的三個輸入，本發明根據設計標準存在多種輸入和輸出，例如，圖2示出附加的輸入SEL_MM_D[1:0]。圖3中的編碼方案圖解說明了對於EN_MM＝0的值，所選擇的MMI值是0，並且SEL_MM[1:0]的值＝SEL_MM_D[1:0]。
在本發明的另一示例性實施例中，能夠使用具有布期處理器301的降低功率的類似方法。如以上提到的，乘法器1000在迭代過程中對模數乘法求解，該求解包括向累加器100提供MMI和部分乘積值(PPI)。布期處理器301和多路復用器20被用來選擇部分乘積(PPI)值(例如，0、A、2A、-2A、-A...)以提供給累加器100。布期處理器301輸入兩個被乘數(A[1:0])的LSB、兩個乘數(B[1]和B
)以及B[r]的LSB，B[1]的先前迭代值。
為了選擇PPI值，布期處理器301向多路復用器20輸出部分乘積選擇信號SEL_PP[1:0]。多路復用器20接收被乘數(A)的值和SEL_PP[1:0]，並且向與門32輸出值。與門32接收來自復用器20的輸入和來自布期處理器301的部分乘積使能信號EN_PP。然後，與門32輸出所選擇的部分乘積值(PPI)，將該PPI提供給累加器100。
類似於以上討論的過程，布期處理器301可以包括布期重編碼器80和部分乘積反饋寄存器64。PPI的0值能夠在部分乘積反饋寄存器64中通過存儲SEL_PP_D[1:0](先前的SEL_PP[1:0]的值)來選擇。當期望PPI＝0的值，布期處理器301輸出具有0值的的部分乘積使能信號EN_PP。該信號EN_PP輸入到與門32。與門32將多路復用器20的輸出作為輸入，多路復用器20使用模數倍數選擇信號SEL_PP_D[1:0]的先前值，此處，不使用MUX運算，以及與門32輸出PPI＝0的值。沒有MUX運算的PPI＝0的安排降低了乘法器1000的功耗。圖4中示出了類似於上述的編碼方案。
圖4圖解說明了根據本發明的示例性實施例的編碼方案。儘管圖4中示出了對布期重編碼器70的三個輸入，本發明能根據涉及標準而有各種輸入和輸出，例如圖2示出的附加輸入SEL_PP_D[1:0]和A[1:0]。圖4中的編碼方案圖解說明了對於EN_PP＝0的值，所選擇的PPI的值是0，以及SEL_PP[1:0]＝SEL_PP_D[1:0]的值。
此外，在本發明的示例性實施例中，在圖4中圖解說明的編碼方案的示例減少了平均漢明間距。漢明間距是相同位的位置的不同值的數量。例如，如果在第(I-1)次迭代中SEL_PP[1:0]對應於PPI的「A」值具有值「00」，則在第I次迭代中SEL_PP[1:0]對應於PPI的「2A」值具有值「11」，導致二(2)的漢明間距。減少兩個值間的漢明間距是所期望的，從而降低了位倒置的數量和計算功率的使用。通過選擇編碼方案，其中如果先前的迭代PPI值是A或2A，則隨後的迭代PPI值受限制，並不可能是2A；如果先前的迭代PPI值是-A或-2A，則隨後的迭代PPI值受限制，不不可能是-2A。圖4圖解說明了不同的編碼方案的位值，然而，本發明的示例性實施例的編碼方案應該不限於圖4中所示的位模式。例如，對於「A」的PPI的值能夠對應於SEL_PP[1:0]的值10，而不是所示的00。
如上討論的PPI值的選擇，類似的漢明間距編碼方案能夠應用於MMI值的選擇。
儘管圖2圖解說明了4∶1多路復用器的使用，本發明的示例性實施例不限於特定的多路復用器的比率值。
在傳統迭代中，模數處理器300和布期處理器301依次運行。然而，布期處理器301獨立於多路復用器1000的求解的迭代特性。在本發明的示例性實施例中，布期處理器301提供部分乘積的兩個LSB(PPI[1:0])，將該兩個LSB加到由累加器100提供的先前迭代的累加的結果(SI[1:0])，產生SPPI[1:0]。在其他示例性實施例中，能夠使用不同的位和位數來產生SPPI。由模數處理器使用值SPPI[1:0]，同時寄存器7(存儲B的值)向右移兩位。在對寄存器7移位後，不依賴於模數處理器300的活動，將B[1]、B
和B[r]的新值輸入到布期處理器301。從而，能夠運算布期處理器301的同時運算模數處理器300。流水線型寄存器210將布期處理器(301)輸出的SEL_PP[1:0]、EN_PP、NEG_PP和PPI[1:0]分別存儲在子寄存器64-67中。流水線型寄存器通過減少關鍵路徑的長度來提高乘法器的硬體性能。可以重複上述步驟，直到B[1]是乘數B的最高位。布期處理器301和模數處理器300的同時運算增加了整個乘法器1000的計算速度。
如上面所討論的，乘法器1000輸入模數倍數MMI和部分乘積PPI。通常，首先將PPI輸入到累加器100，然後將MMI輸入到累加器100。為了計算MMI，首先進行計算PPI的第一邏輯運算，然後進行組合PPI和SI的第二邏輯運算，接著由模數處理器計算SEL_MM[1:0]和EN_MM的如上所述的第三邏輯運算。不在相同的時間輸入兩個值MMI和PPPI，這是由於每個值行進於不同的路徑。所以，由於累加器執行邏輯運算兩次，因而增加了功耗。如果兩個值MMI和PPI同時或幾乎同時到達累加器100，則功耗能夠減少。
在本發明的示例性實施例中，可以提供同步寄存器，用來對到累加器的PPI和MMI的到達時間進行同步。如上所述，布期處理器301分布向多路復用器20和與門32提供SEL_PP[1:0]和EN_PP，以便選擇部分乘積PPI。同樣的，模數處理器300分布向多路復用器10和與門31提供SEL_MM[1:0]和EN_MM，以便選擇模數倍數值MMI。在同步寄存器中保存值SEL_PP[1:0]、EN_PP和/或SEL_MM[1:0]和EN_MM允許MMI和PPI的同步。
在本發明的示例性實施例中，提供模數倍數同步寄存器240和/或部分乘積同步寄存器220。對於乘法器1000中的其他寄存器的時鐘相位，同步寄存器220和240使用反向時鐘相位。模數倍數同步寄存器240能夠在子寄存器62和63中分別存儲SEL_MM[1:0]和EN_MM的值。如果使用部分乘積同步寄存器220，則它能夠在子寄存器68和69中分別存儲SEL_PP[1:0]和EN_PP的值。能夠使用一個或兩個寄存器，並且此處的討論不限於針對一個同步寄存器的本發明的示例性實施例。在示例性實施例中，在使用兩個同步寄存器時，在子寄存器62和68中分別存儲SEL_MM[1:0]和SEL_PP[1:0]，同時在子寄存器63和69中分別存儲EN_MM[1:0]和EN_PP[1:0]。響應時鐘信號CK，分別將SEL_MM[1:0]和SEL_PP[1:0]幾乎同時輸入到多路復用器10和多路復用器20，同時分別將EN_MM和EN_PP幾乎同時輸入到與門31和與門32。從而，MMI和PPI同步並被提供到累加器100。因此每個數據集MMI和PPI能夠執行一個邏輯運算，正好相反於傳統的兩個邏輯運算，這樣明顯地減少了乘法器1000的功耗。
從而，所討論的本發明的示例性實施例的變化和組合確定是在本發明的範圍之內。
本發明的示例性實施例不被蒙哥馬利乘法的基數所限制；本發明的示例性實施例能夠在基於乘法器的各種基數中應用。例如，圖5圖解說明了具有模數倍數同步寄存器36和/或另一個同步寄存器37的基數2的系統，用於存儲乘法器的值(B)。如上面所討論的，同步寄存器36和37能夠幾乎同時用來向累加器200提供減小乘法器2000的功耗和提高乘法器2000的速度的MMI和PPI的值。本發明的其他示例性實施例能夠使用一個或兩個同步寄存器。
本發明的說明實際上僅僅是示例性的，從而，不偏離本發明的要點的變化確定是在本發明的實施例的範圍之內。這樣的變化不認為是偏離了本發明的精神和範圍。例如，多路復用器10和20能夠具有各種比率值。模數倍數同步子寄存器62能夠起到作為模數倍數反饋寄存器而不具有附加的獨立的模數倍數反饋寄存器230的雙重目的的作用。同樣地，部分乘積反饋寄存器64能夠起到作為部分乘積同步寄存器220的子寄存器從而不需要子寄存器68和反饋寄存器64的雙重作用。在其他變化中，能夠不使用諸如流水線型寄存器和/或反饋寄存器的其他寄存器而使用同步寄存器220和240。
權利要求
1.一種布期處理器，包括布期重編碼器；以及布期寄存器，其中對布期寄存器的輸入是來自所述布期重編碼器的至少一個輸出。
2.根據權利要求1所述的布期處理器，其中所述布期寄存器是反饋寄存器，該反饋寄存器存儲將反饋回所述布期重編碼器的布期重編碼器的至少一個輸出值。
3.根據權利要求2所述的布期處理器，其中所述輸出值是部分乘積選擇信號，該部分乘積選擇信號用來選擇部分乘積值。
4.根據權利要求1所述的布期處理器，其中所述布期寄存器是流水線型寄存器，所述流水線型寄存器存儲所述布期重編碼器的輸出值。
5.一種模數處理器，包括模數重編碼器；以及模數反饋寄存器，其中對反饋寄存器的輸入是來自所述模數重編碼器的至少一個輸出。
6.根據權利要求5所述的模數處理器，其中所述模數反饋寄存器存儲將反饋回所述模數重編碼器的模數重編碼器的至少一個輸出值。
7.根據權利要求5所述的模數處理器，其中輸出值是模數倍數選擇信號，該模數倍數選擇信號用來選擇模數倍數值。
8.一種乘法器，包括布期重編碼器；部分乘積同步寄存器，其中對所述部分乘積同步寄存器的輸入是來自所述布期重編碼器的至少一個輸出；模數重編碼器；以及模數倍數同步寄存器，其中對所述模數倍數同步寄存器的輸入是來自所述布期重編碼器的至少一個輸出，使用該部分乘積同步寄存器和模數倍數同步寄存器以同步來自所述布期重編碼器和所述模數重編碼器的輸出。
9.根據權利要求8所述的乘法器，還包括布期與門，其中將來自所述部分乘積同步寄存器的至少一個值輸入到布期與門。
10.根據權利要求8所述的乘法器，還包括模數與門，其中將來自所述模數倍數同步寄存器的至少一個值輸入到模數與門。
11.一種乘法器，包括模數重編碼器；模數反饋寄存器，其中對所述模數反饋寄存器的輸入是來自所述模數重編碼器的至少一個輸出；布期重編碼器；以及布期寄存器，其中對所述布期寄存器的輸入是來自所述布期重編碼器的至少一個輸出，該模數反饋寄存器和布期寄存器保存使乘法器中能夠減少計算功率的使用的值。
12.根據權利要求11所述的乘法器，其中所述布期寄存器是反饋寄存器，該反饋寄存器存儲將反饋回所述布期重編碼器的所述布期重編碼器的至少一個輸出值。
13.根據權利要求12所述的乘法器，其中所述輸出值是部分乘積選擇信號，該部分乘積選擇信號用來選擇部分乘積值。
14.根據權利要求11所述的乘法器，其中所述布期寄存器是流水線型寄存器，該流水線型寄存器存儲布期重編碼器的輸出值。
15.根據權利要求11所述的乘法器，其中模數反饋寄存器存儲將反饋回所述模數重編碼器的所述模數重編碼器的至少一個輸出值。
16.根據權利要求15所述的乘法器，其中所述輸出值是模數倍數選擇信號，該模數倍數選擇信號用來選擇模數倍數值。
17.根據權利要求11所述的乘法器，還包括布期與門，其中將來自所述布期寄存器的至少一個值輸入到該布期與門。
18.根據權利要求11所述的乘法器，還包括模數與門，其中將來自所述模數反饋寄存器的至少一個值輸入到該模數與門。
19.一種部分乘積產生器，包括布期重編碼器；以及多路復用器，其中該多路復用器輸入來自所述布期重編碼器的至少一個輸出，該布期重編碼器和多路復用器用來獲得部分乘積。
20.根據權利要求19所述的部分乘積產生器，還包括布期與門，其中將來自所述多路復用器的至少一個值輸入到該布期與門。
21.根據權利要求19所述的部分乘積產生器，其中所述布期重編碼器產生部分乘積選擇信號，以及根據所述部分乘積選擇信號的先前值將位模式分配給禁止的部分乘積選擇信號的任何值。
22.根據權利要求21所述的部分乘積產生器，其中選擇所述位模式，以便減少在部分乘積選擇信號的當前值和部分乘積選擇信號對應的先前值之間的漢明間距。
23.根據權利要求21所述的部分乘積產生器，其中選擇所述位模式，以便減少在部分乘積選擇信號的當前值和部分乘積選擇信號對應的先前值之間的平均時間的漢明間距。
24.根據權利要求21所述的部分乘積產生器，其中所述布期重編碼器還包括第一多路復用器，其中該第一多路復用器輸入先前部分乘積選擇信號的值的第一部分，以及輸出當前部分乘積選擇信號的第一部分；以及第二多路復用器，其中該第二多路復用器輸入先前部分乘積選擇信號的值的第二部分，以及輸出當前部分乘積選擇信號的第二部分。
25.根據權利要求24所述的部分乘積產生器，其中所述第一多路復用器和所述第二多路復用器是8∶1多路復用器。
26.一種模數倍數產生器，包括模數重編碼器；以及多路復用器，其中如果使能信號沒有預定的值，則所述模數重編碼器產生當前模數倍數選擇信號，如果使能信號有預定的值，則不產生模數倍數選擇信號而使用選擇信號的先前值，該選擇信號用來選擇模數倍數值。
27.根據權利要求26所述的模數倍數產生器，還包括模數與門，其中將來自多路復用器的至少一個值輸入到模數與門。
28.根據權利要求26所述的模數倍數產生器，其中所述模數重編碼器還包括第一多路復用器，其中該第一多路復用器輸入先前選擇信號的值的第一部分，以及輸出當前模數倍數選擇信號的第一部分；以及第二多路復用器，其中該第二多路復用器輸入先前選擇信號的值的第二部分，以及輸出當前模數倍數選擇信號的第二部分。
29.根據權利要求28所述的模數倍數產生器，其中所述第一多路復用器和所述第二多路復用器是8∶1多路復用器。
30.一種乘法器，包括模數重編碼器；模數反饋寄存器，其中對該模數反饋寄存器的輸入是來自所述模數重編碼器的至少一個輸出；模數同步寄存器，其中對該模數同步寄存器的輸入是來自所述模數重編碼器的至少一個輸出；布期重編碼器；布期同步寄存器，其中對該布期同步寄存器的輸入是來自所述布期重編碼器的至少一個輸出；以及布期寄存器，其中對該布期寄存器的輸入是來自所述布期重編碼器的至少一個輸出，所述模數反饋寄存器和該布期寄存器保存使在乘法器中能夠減少計算功率使用的值，以及所述布期同步寄存器和所述模數同步寄存器用來同步來自所述布期重編碼器和所述模數重編碼器的輸出以減少故障。
31.根據權利要求30所述的乘法器，其中所述布期寄存器是反饋寄存器，該反饋寄存器存儲將反饋回所述布期重編碼器的所述布期重編碼器的至少一個輸出值。
32.根據權利要求31所述的乘法器，其中所述輸出值是部分乘積選擇信號，該部分乘積選擇信號用來選擇部分乘積值。
33.根據權利要求30所述的乘法器，其中所述布期寄存器是流水線型寄存器，該流水線型寄存器存儲所述布期重編碼器的輸出值。
34.根據權利要求30所述的乘法器，其中所述模數反饋寄存器存儲將反饋回所述模數重編碼器的所述模數重編碼器的至少一個輸出值。
35.根據權利要求34所述的乘法器，其中所述輸出值是模數倍數選擇信號，該模數倍數選擇信號用來選擇模數倍數值。
36.根據權利要求30所述的乘法器，還包括布期與門，其中將來自所述布期同步寄存器的至少一個值輸入到所述布期與門。
37.根據權利要求30所述的乘法器，還包括模數與門，其中將來自所述模數同步寄存器的至少一個值輸入到所述模數與門。
38.根據權利要求30所述的乘法器，其中通過使用來自所述模數同步寄存器的值和來自所述布期同步寄存器的值來同步模數倍數值和部分乘積值。
39.一種提高基數2N蒙哥馬利乘法的計算速度的方法，其中N＞1，該方法包括向布期重編碼器提供輸入；存儲所述布期重編碼器的輸出；以及累加蒙哥馬利乘法的結果，其中及時地交錯執行所述存儲和累加。
40.根據權利要求39所述的方法，其中將所述布期重編碼器的輸出存儲在流水線存儲器中。
41.一種減小基數2N蒙哥馬利乘法的功耗的方法，其中N≥1，該方法包括接收模數、乘數和被乘數；同步相對於模數、乘數和被乘數的值；將所述值進行累加以產生蒙哥馬利乘法的結果。
42.根據權利要求41所述的方法，還包括使用至少一個模數、乘數和被乘數來計算模數倍數；以及使用至少一個模數、乘數和被乘數來計算部分乘積，其中所述模數倍數和所述部分乘積是同步的值。
43.根據權利要求41所述的方法，其中所述同步步驟還包括在同步寄存器中存儲與模數、乘數和被乘數相關的至少兩個輸入。
44.根據權利要求42所述的方法，還包括匹配部分乘積和模數倍數到達累加器的時間，減少蒙哥馬利整個乘法的功耗。
45.一種減小基數2N蒙哥馬利乘法的功耗的方法，其中N＞1，該方法包括向布期重編碼器提供輸入；使用所述布期重編碼器來產生選擇信號；基於先前選擇信號的值來向禁止的任何選擇信號的值分配反轉位模式；以及存儲所述布期重編碼器的輸出。
46.根據權利要求45所述的方法，還包括選擇反轉位模式，以便使在當前選擇信號的值和先前選擇信號的值之間的漢明間距最小。
47.根據權利要求45所述的方法，其中選擇位模式，從而使在當前選擇信號的值和與當前選擇信號對應的先前值之間的漢明間距最小。
48.一種減小基數2N蒙哥馬利乘法的功耗的方法，其中N≥1，該方法包括確定第n次迭代結果信號的值；向電路提供使能信號和第n次迭代結果信號的值；如果所述使能信號提供第n+1次無意義的迭代結果信號的值，則不對所述第n+1次的迭代結果信號的值進行計算；反饋第n次迭代結果信號的值；以及使用第n次迭代結果信號的值，而不使用第n+1次的迭代結果信號的值。
49.根據權利要求48所述的方法，其中由組合邏輯確定第n次和第n+1次迭代結果信號的值。
50.根據權利要求49所述的方法，其中組合邏輯由多路復用器執行。
51.一種減少模數重編碼器的功耗的方法，包括確定第n個模數倍數選擇信號的值；選擇寄存器中的第n個模數倍數選擇信號的值；產生第n+1個使能信號，其中使能信號的預定值選擇0為模數倍數值；以及如果第n+1個使能信號的值是預定值，則使用第n個模數倍數選擇信號的值而不確定第n+1個模數倍數選擇信號的值。
52.根據權利要求51所述的方法，還包括使用模數倍數選擇信號來選擇模數倍數值，其中當使能信號是所述預定值時，不執行選擇步驟。
53.一種蒙哥馬利乘法器，包括用於輸入的裝置，其中該用於輸入的裝置輸入模數、乘數和被乘數的值；用於布期存儲的裝置，其中該用於布期存儲的裝置存儲至少一個從布期重編碼器輸出的值；用於模數存儲的裝置，其中該用於模數存儲的裝置存儲至少一個從模數重編碼器輸出的值；用於產生部分乘積的裝置，其中該用於產生部分乘積的裝置使用來自用於輸入的裝置的輸入產生部分乘積值；用於產生模數倍數的裝置，其中該用於產生模數倍數的裝置使用來自用於輸入的裝置的輸入來產生模數倍數；用於同步的裝置，其中該用於同步的裝置同步所述部分乘積值和模數倍數值；以及用於累加的裝置，其中該用於累加的裝置輸入同步部分乘積值和模數倍數值並產生蒙哥馬利乘法器的結果。
全文摘要
一種對執行模數乘法的蒙哥馬利模數乘法模塊進行降低功率和增加計算速度的方法。編碼方案減少了用於選擇部分乘積和模數倍數的漢明間距，並且減少了多路復用運算和功耗。同步寄存器對向減少故障和/或提高計算速度的累加器輸入的部分乘積和模數倍數值同步。寄存器提供了先前值的存儲並減少了需要從多路復用器獲取值，並且減少了多路復用器的運算和/或降低了功耗。
文檔編號G06F7/72GK1550975SQ20041004226
公開日2004年12月1日 申請日期2004年5月9日 優先權日2003年5月9日
發明者孫熙寬 申請人:三星電子株式會社