一種用於計算機系統的快速模數運算"emod"的製作方法

2023-06-05 17:16:46

專利名稱：一種用於計算機系統的快速模數運算"emod"的製作方法
背景技術：
本發明涉及模數運算。具體地說，它涉及可被高效率執行的模數運算。
模數運算(俗稱為「mod」運算)用於確定除法運算的餘數。因此，A mod N的表達式確定了將數A除以N後所獲得的餘數結果。例如，17除以3後商為5，餘數是2，「17 mod3」產生值為2的結果。
在許多計算應用中都執行Mod運算，包括兩方在從事加密通信前所進行的密鑰協商。在密鑰協商的上下文中，在兩個終端處對具有(AB)mod n形式的方程進行估算。通常，A和B值可以很大——從1024到2048位那麼長。當然，當兩個具有長度I的操作數相乘時，結果可能長達2I。在這麼大操作數的情況下，在處理器中建立具有全寬度乘法結果的結果寄存器是不切實際的。相反，當生成乘法結果時，一般通過對每個乘積進行mod運算來截斷它們。因為mod運算利用具有自身長度(比如j)的模數來除每個乘積，所以結果的長度總是小於j。
假設長度為I的操作數其中含有相等數量的0和1，對(AB)mod n的估算就需要I次乘法和I次mod運算。這包含了大量的計算開銷。與這些計算相關聯的開銷在高負載的環境中變得格外嚴重，例如在計算機伺服器中，預計每小時將收到幾千次密鑰協商請求(也許更多)。
由此，在本領域中需要一種快速的、計算上節省的技術來求解具有大操作數的mod運算。


圖1圖示了根據本發明一種實施方案的方法。
圖2圖示了根據本發明一種實施方案的方法。
圖3圖示了根據本發明一種實施方案的另一種方法。
圖4是圖示了根據本發明一種實施方案的中間積生成器的框圖。
圖5是圖示了根據本發明一種可替換實施方案的IPG的框圖。
圖6圖示了根據本發明一種實施方案的乘法器。
圖7圖示了根據本發明一種實施方案的乘法器電路。
圖8圖示了根據本發明另一種實施方案的乘法器電路。
圖9圖示了根據本發明一種實施方案的乘法器電路。
圖10圖示了根據本發明另一種實施方案的乘法器電路。
圖11圖示了根據本發明一種實施方案的另一種方法。
具體實施例方式
本發明的各種實施方案介紹了一種用在mod計算中的「emod」運算。emod是對傳統mod運算而言是一種計算上的替代，是一種計算上不那麼昂貴，但精度也不那麼精確的運算。emod運算可以與在(AB)mod n計算或(A·B)mod n計算的估算過程中產生的中間乘法(interstitial multiplication)一同使用。最後，當得到一個最終乘積時，可以執行傳統的mod運算來獲得最終的結果。按照這種方式，本發明的實施方案避免了也許數以千計的mod運算的計算開銷，否則可能要在運算的中間階段執行這些mod運算。
雖然計算機執行的是二進位值(基2)的算術運算，但是通過使用傳統的十進位數(基10)的例子，可以最好地理解emod運算的優點。為了估算23754 mod 3331的運算，通常是將23754除以3331而獲得餘數437。然而，這種除法在計算上是很昂貴的。如果使用接近10k的某個模數的倍數(其中，k是任意數)，就容易多了。使用這樣一個倍數(比如用9993來取代3331)，就可以利用一系列減法來取代除法運算。在從23754中兩次減去9993後，剩餘數為3768(該數包括正確的餘數437加上3331)。這個剩餘數足以和在計算的中間階段所獲得的中間積一起使用。當獲得最終結果並採用真正的mod運算時，將會從可能已從各中間階段延續下來的模數的任何倍數中分隔出正確的餘數。然而，這個「假想模數」的使用提高了處理速度。
以上解釋的實施例也適用於二進位方案。在基2域中，對於某個模數n，選擇一個非常接近2k(k是任意數)的倍數。就像上面十進位實施例中在最高有效位位置中包含一串連續的9一樣，在二進位的實施例中，假想模數在最高有效位位置中將包含一串連續的1。這個性質簡化了在從操作數A中減去該假想模數時所進行的減法運算。
給定模數n，可以選出假想模數mn，使得m·n＝2k-d，其中d＜n。然後可以將emod運算用作遞歸減法，在所述的遞歸減法中，從源操作數中減去mn，直到剩餘數小於mn。這兩個參數d和m控制著emod運算。
(A·B)emod n的估算根據一種實施方案，可以通過將操作數B解析為每個長w位的多個字來估算c＝(A·B)emod n (1)因此B=B[M-1],B[M-2],,B
=i=0M-12wiB[i]---(2)]]>於是，方程1變為
c=(Ai=0M-12wiB[i])emodn---(3)]]>＝((...(A·B[M-1]·2w+A·B[M-2])·2w+...)·2w+A·B
)emod nemod運算是分布式的，並且可以在圓括號內重複。這一性質導致了圖1中所圖示的方法。
圖1示出了根據本發明一種實施方案的方法1000。根據方法1000，變量c可以被初始化為0(框1010)。此後，方法1000可以迭代地考慮被乘數B的每一個字，從對應於B的最高有效位位置的字一直到對應於最低有效位位置的字。在每次迭代期間，方法1000可以將前次迭代後的c值左移一個字的長度(框1020)。新的B字(標記為「B[i]」)與A相乘後的值可以和c移位後的值相加(框1030)。此後，可以對框1030所得到的結果執行emod運算(框1040)。emod的結果可以用作下一次迭代的初始值c。在最後一次迭代之後，所獲得的c值就是計算結果。
在一種實施方案中，可以根據以下偽代碼用軟體實現圖1中的方法。

基本相乘/求模算法其中，shiftleft(w，c)僅將c操作數左移w位。這等同於在二進位中乘以2w。
emod操作符基於假想模數mn＝m·n進行運算，產生一個精度因子d＝2k-mn。如果操作數c被分成兩部分，商q和餘數r，使得c＝q·2k+r (4)則emod運算可以被定義為(c emod n)＝((q·2k+r)emod n)＝(q-2k+r-q·mn) (5)＝(r+q·d)這個emod函數可以被合併到圖1的方法中，如圖2的實施方案所示。
圖2圖示了根據本發明一種實施方案的方法1100。根據方法1100，虛擬變量c可以被初始化為0(框1110)。此後，該方法可以迭代地考慮被乘數B的每一個字，從對應於B的最高有效位位置的字一直到對應於最低有效位位置的字。所述方法可以由前次迭代得到的c值來計算商值q和餘數值r(框1120、1130)。可以將c中從最高有效位位置到第k位位置之間的位範圍(a span of bits)在左移w位後作為商q。可以將c中從第k-1位位置到第0位位置之間的剩餘位在左移w位後作為餘數r。此後，c值可被估算為c＝A·B[i]+r+d·q(6)(框1140)。最後一次迭代所獲得的c值可被當作emod函數的結果。
在一種實施方案中，可以根據以下偽代碼用軟體實現圖2中的方法。

相乘/求模算法這種實現方式要求可以立即得到乘積d·q。實際上，由於要花一些時間來生成這個乘積，所以上述方法在該乘積變為可用之前實際上被停止了。
在可替換的實施方案中，所述方法在沒有獲得d·q乘積的情況下，可以完成當前的迭代。而且它還可以前進到i的下一次迭代，並結合從前面的迭代中取得d·q乘積。圖3圖示了這種實施方案。
圖3圖示了根據本發明一種實施方案的方法1200。根據方法1200，變量c可被初始化為0(框1210)。此後，該方法可以迭代地考慮被乘數B的每一個字，從對應於B的最高有效位位置的字一直到對應於最低有效位位置的字。在每次迭代中，方法1200可以由前次迭代得到的c值來計算商值q[i]和餘數值r[i](框1120、1130)。可以將c中從最高有效位位置到第k位位置之問的位範圍在左移w位後作為商q[i]。可以將c中從第k-1位位置到最低有效位位置之間的剩餘位在左移w位後作為餘數r[i]。前次迭代所獲得的商q[i-1]也可以被左移w位(框1240)。此後，c值可被估算為c＝A·B[i]+r[i]十d·q[i-1]， (7)這裡，q[i-1]值是在框1240中所獲得的移位後的值(框1250)。
在最後一次迭代之後，最後一次迭代所獲得的商可以與c相加(框1260)。這一運算所獲得的值可被當作emod運算的結果。
在一種實施方案中，可以根據以下偽代碼用軟體實現圖3中的方法。


具有1個周期q延遲的相乘/求模算法在這種實施方案中，前次迭代所產生的d·q乘積(重新標記為d·q1)被向左移位，以解決兩個字之間的位置差。
如上所述，圖3的實施方案在等待d·q運算的估算結果時無需停止。這種實施方案適用於高負載的應用，在這種應用中最重要的就是避免計算延時。
大數與小數間的乘法如上所述，被乘數B可以被解析為多個更小的字B[w]，w＝0到M-1，這些字可被用作與乘數A之間執行乘法的基礎。下面將討論這一實施方案的電路實現方式。
圖4中的框圖根據本發明的一種實施方案示出了中間積生成器(「IPG」)100。IPG 100由被乘數A生成中間積。它可以包括被乘數寄存器(這裡被稱為「A寄存器」)110、一對移位器120、130(分別標記為「移位1」和「移位2」)和「3A寄存器」140。圖中用虛線來表示A寄存器和3A寄存器，這是因為它們可以(但不是必須)被放置在IPG 100自身內；或者，可以在某種其他電路中提供這些寄存器，但是它們的內容可以作為輸入被提供給IPG100。IPG 100還可以包括一對多路復用器(俗稱為「MUX」)150、160和反相器170。
移位器120、130中的每一個都提供了那些代表A寄存器中所存儲的值在移位預定數量的位(bit)位置後的值。第一移位器120可以提供朝最高有效位位置移位了1位位置的A值。它被標記為「移位1」。第二移位器130可以提供己經朝最高有效位位置移位2位位置的A值，它被標記為「移位2」。在二進位數據系統中，單位移位和雙位移位分別導致了源數據值的兩倍乘法和四倍乘法。
可以以任意數量的實施方案來提供移位器120、130。也許最簡單的實施方案就是在A寄存器110和MUX 150之間提供硬連線互連作為移位器。例如，A寄存器110中的每個位位置i可以連接到MUX 150的位置i+1，以構成「移位1」移位器120。同樣，A寄存器中的每個位位置i可以連接到MUX 150的位置i+2，從而滿足「移位2」移位器130。移位1移位器的最低有效位位置可以接地。移位2移位器中輸入到MUX 150的兩個最低有效位位置也可以接地。就面積或控制層次而言，這種體系結構以最低的實現成本提供了所需要的移位功能。
可替換地，移位器120、130可被配備為正式的移位寄存器，它們完整地帶有用於存儲移位後的值的存儲單元(未示出)。雖然這種替換方案不具有任何性能優勢，但是它可以適用於為其他目的使用這種移位寄存器的應用中。
3A寄存器140，正如它的名字所暗示的那樣，是用於存儲代表三倍於A寄存器中數值的值的寄存器。存儲在這個寄存器中的值可以通過將A寄存器110和移位1寄存器120的值直接相加而獲得，或者可替換地，可以從移位2寄存器140的值中減去移位1寄存器120的值，從而獲得該寄存器中的值。用於實現這些功能的電路是簡單易懂的，並且為了保持圖示說明的簡潔，從圖1中省去了上述電路。在一種實施方案中，3A寄存器140也可以被配備在IPG 100之外；因此用虛線示出。
A寄存器110、兩個移位器120和130以及3A寄存器140的輸出可以被輸入到第一MUX 150。第一MUX 150的輸出可被輸入到第二MUX 160和反相器170。反相器170的輸出可以作為第二輸入被提供給第二MUX 160。反相器170可以生成從第一MUX 150輸出的多個位的2的互補反碼(complement inversion)。第二MUX 160可以具有直接耦合到零值「」的第三輸入。或者，零值可被輸入到第一MUX 150。因此，給定輸入值A，則IPG 100可能生成以下任何輸出A、A、2A、2A、3A、3A、4A、4A和。
IPG 100可以包括控制器180，用於掌管兩個MUX 150、160的操作。如下面討論的那樣，給定輸入的「段」，控制器180可以產生一個控制信號(標記為ci)，該信號使得MUX 150、160在驅動時鐘(未示出)的每個周期上輸出可能的輸出中所選定的一個輸出。
圖5是圖示了根據本發明一種可替換實施方案的IPG 200的框圖。根據本發明的一種實施方案，IPG 200可以包括多個反相器210、220、230-1、230-2和3X乘法器240、一對移位器250-1和250-2以及多路復用器260。在這種實施方案中，IPG 200被圖示為與外部的被乘數寄存器相連，而不是將被乘數寄存器包括為自身的一部分。被乘數可以在IPG200的第一終端270上被輸入給IPG 200。反相器之一210可以耦合到第一終端270，以在被乘數出現時將其反相。
3X乘法器如同它的名稱所暗示的那樣，當被乘數出現在輸入終端時生成一個三倍於被乘數的值。第二反相器220可以耦合到3X乘法器240以反相它的輸出。
移位器250-1、250-2和圖2實施方案中的一樣，提供了移位後的被乘數。它們之一(例如移位器250-1)將輸入的被乘數移位單個位位置；另一個250-2將被乘數移位2個位位置。與各個移位器250-1、250-2相接的反相器230-1、230-2可以生成被乘數的反相的移位後的值。可以根據上述任何一種實施方案來提供移位器250-1、250-2。
反相器210、220、230-1、230-1，3X乘法器240和移位器250-1、250-2的輸出可被輸入到多路復用器260。多路復用器260也可被控制為不輸出來自IPG 200的任何輸入。這種情況下，多路復用器260使IPG 200從中生成零輸出。
根據一種實施方案，當想要基於一個長被乘數A和短乘數B來執行乘法運算時，被乘數A可被輸入到IPG 200中。A、3A、A和3A的值將在一個短的初始化時期後對多路復用器260可用。同樣，A和A移位後的值也將對多路復用器260可用。一旦這些值可用，則它們可從IPG中被取出，並基於乘數段的值被轉發到乘法電路的剩餘部分(在圖5中未示出)。
所述的IPG包括控制器290，該控制器響應於這些乘數段，讓多路復用器260從該IPG內取出先前存儲的值之一。我們知道，許多乘法電路包括用於其他目的的控制器。控制器290可被集成到這些公知的控制器中，或者在需要時以獨立的元件出現。圖5僅為方便起見，圖示了與IPG 200獨立的控制器290。
在一種實施方案中，乘數B可被解析成幾個四位段si。每個段si包括乘數B中的B3i+2-B3i-1位。由這些段可以生成控制信號CTRL，用以確定IPG內的哪一個值應當從多路復用器輸出。在一種實施方案中，所述IPG可以根據下面表1所示的方案來生成輸出。

表1其中，A是輸入A的2的補碼(complement)。控制值CTRL可以按照下式與四位輸入模式相關CTRL＝-4si3+2si2+si1+si0(8)其中，sij代表si段的第j位位置。對於s0段，作為虛構位位置「B-1」的第0位位置可被設置為0，以使得所述控制器對s0段的響應與表1一致。
從圖6中可以看出，乘數B不會將所有段全部填滿，除非該乘數的長度是3的倍數。在一種實施方案中，當乘數的長度不是3的倍數時，它可以進行充分長度地符號擴展，以填滿最後一段中尚未使用的部分。這一般包括複製符號位，即最高有效位BMSB，以填充在該最高有效位之外的虛構的位位置。
前面所描述的IPG實施方案可被應用於不同體系結構的乘法器電路。在每種應用中，IPG的使用基本上都通過每三位位置進行一次加法，而不像傳統技術那樣每個位位置都進行一次加法，從而使得乘法器電路實現了更快的運算。
圖7是根據本發明一種實施方案在組合乘法器300中應用IPG的圖。組合乘法器300可以包括第一和第二寄存器310，分別用於存儲被乘數A和乘數B。它可以包括IPG 330、控制器340、多個中間積寄存器350.1-350.L、加法器樹360和乘積寄存器370。
在運算期間，IPG 330可被初始化來建立A、A、3A和3A值以及A和A移位後的值。控制器340可以將乘數B解析為多個段，並且響應於每個段中的位模式，讓IPG 330將其中一個值加載到對應的中間積寄存器(比如350.1)中。在一種實施方案中，中間積寄存器350.1-350.L的數量可以取決於乘數B所支持的段的數量。因此，中間積寄存器350.1-350.L的數量可以與乘數寄存器320的長度綁定。
一旦將值加載到每一個中間積寄存器350.1-350.L中，組合乘法器300就可以通過對所有的中間積寄存器350.1-350.L求和，從而使最終的乘積被存儲在乘積寄存器370中。加法器樹360接受來自每個乘積寄存器的中間積值，並以認識中間積寄存器之間的各個位偏移量的方式來對它們求和。加法器樹本身是公知的，可以針對這一目的進行修改。
在一種被乘數A長m，乘數B長n的實施方案中，乘積寄存器370可以象傳統的組合乘法器中一樣，具有n+m的長度。而中間積寄存器350.1-350.L可以具有m+2的長度，雖然在傳統的組合乘法器中它們的長度為m。
傳統的組合乘法器對於乘數B的每個位位置都包括一個中間積寄存器。在前面的實施方案中，對於乘數B的每三個位位置才只有一個中間積寄存器(例如350.1)。因此，由於上述實施方案中的組合乘法器300與傳統的對應部分相比，包括大約三分之一數量的中間積寄存器，所以加法器樹包括三分之一數量的用於計算最終總和的加法器。因為在更少的中間值上執行最終的加法，因而可以更快地獲得最終的和，所以預計在本實施方案中將更快地產生結果。因此，這一實施方案以更少的邏輯產生了更高的吞吐率。
圖8是根據本發明一種實施方案的、與移位-相加乘法器電路400集成在一起的IPG的應用框圖。乘法器電路400可以包括一對寄存器410、420，用於存儲被乘數A和乘數B。移位-相加乘法器電路400還可以包括IPG 430、控制器、進位存儲加法器(carry saveadder)450和乘積寄存器460。
在運算期間，乘法器電路400可以被初始化。在這種實施方案中，乘積寄存器460可以被清零，並可用被乘數A的值來初始化中間積生成器430。此後，在運算期間，控制器440可以從乘數寄存器420中移出每個段，並且響應於新的段，可使得所選擇的值從IPG430被輸出到進位存儲加法器450的第一輸入端。乘積寄存器460的最高有效位可被移位3個位置，並被輸入到進位存儲加法器的第二輸入端。進位存儲加法器450可以將提供給它兩個輸入端的每一個的值加起來，並將該值寫回到乘積寄存器460。按照乘數B所支持的段的數量多少，可以以遞增的方式多次重複這一過程。
與圖4的實施方案一樣，圖8的實施方案相對於傳統的移位-相加乘法器電路提供了改善的性能。傳統電路對乘數B的每個位位置都執行加法。相反，圖8中所示的實施方案對乘數B的每三個位位置才執行一次加法。同樣，更少數量的加法使得圖8的移位-相加乘法器能夠比傳統電路花費更少量的時間來生成乘法積。
在另一種實施方案中，乘法器電路可以省略掉乘數寄存器(例如圖8的乘數寄存器420)。圖9圖示了一個乘法器500，它由被乘數寄存器510、IPG 520、控制器530、進位存儲加法器540和乘積寄存器550組成。作為初始化步驟，被乘數值(A)可被輸入到IPG520。此外，乘數值(B)可被加載到乘積寄存器550的最低有效位位置中。
在每個時鐘周期上，乘積寄存器550的內容都可以向下移動三個位位置(three bitpositions)。當乘積寄存器的最低有效位被移出乘積寄存器時，它們可以作為新的段被輸入到控制器530。響應於這三位(及從前一個時鐘周期的移位中的1位)，控制器530可以使得IPG 520生成前面表1中所示的輸出。該IPG輸出可被提供給進位存儲加法器540的第一輸入端。乘積寄存器向下移位後的值可以被提供給進位存儲加法器540的第二輸入端。進位存儲加法器540可以將這兩個輸入值加起來，並將它們存儲到乘積寄存器的最高有效位位置。再一次，本實施方案相對於一次執行單位移位的其他移位-相加乘法器而言，提供了改善的性能。與圖4的實施方案相比，由於寄存器420(圖4)可被省略，所以這種實施方案還提供了更好的寄存器利用。
圖10圖示了根據本發明另一種實施方案的乘法電路600。這一實施方案可被用來估值前面的方程7。在這一實施方案中，乘法器600可以包括一對IPG 610、620。第一IPG 610可以估值方程7中的A·B[i]項，第二IPG 620可以估值d·q[i-1]項。第一IPG 610可以接受來自各個寄存器630、640的值A和3A作為輸入。第一IPG 610可以由控制器650來控制，而該控制器650又被B的各個字(未示出的輸入)控制。
第二IPG 620可以接受來自各個源660、670的值d和3d。第二IPG 620可以由q值680來控制。
乘法電路600可以包括進位存儲加法器690，它接受兩個IPG 610、620的輸出以及乘積寄存器700的結果值作為其輸入。進位存儲加法器690的輸出可被輸入到乘積寄存器700。乘積寄存器700可以是一個移位寄存器，用於實現關於圖3所描述的移位。從最低有效位位置開始的位範圍(span of bits)可以作為r[i]值輸出到進位存儲加法器690。
眾所公知，進位存儲加法器生成所謂「冗餘形式」的結果。由於進位存儲加法器不必執行傳統的進位傳播(費時的操作)就可以生成加法運算的結果，所以它們比其他類型的加法器要快一些。取而代之的是，每個「位位置」使用多位來存儲加法結果。以冗餘形式執行多次加法。在最終的加法後，可以執行一次進位傳播，以獲得非冗餘形式的結果。
根據一種實施方案，乘積寄存器700中對應於商q的部分可被輸入到先行進位(carrylookahead)加法器之類的第二加法器710。第二加法器710可以生成非冗餘的結果，該結果可以作為q值被反饋到第二IPG 610。
關於(A·B)emod n運算的估算，已提供了以上的實施方案。如果是關於(A·B)modn運算而進行的，則在圖1-3所示的方法後可以進行單次mod運算，以完成估算過程。然而，為了估算其他的運算，例如可以推遲mod n運算的ABemod n運算，可以有利地使用這些實施方案。
ABemod n的估算下面針對ABmod n運算來描述emod運算的實施方案。該運算的求解可以按照嵌入式循環過程來進行，所述循環過程由外循環和內循環組成。
外循環可以掃描指數的位，用以控制乘法。外循環的每次運行過程可以包括平方操作c＝(c·c)emod n，(9)並且取決於指數的當前位，還可以包括附加的乘法c＝(c·a)emod n。(10)這種實施方案如圖11所示。
圖11圖示了根據本發明一種實施方案的另一種方法1300。根據方法1200，虛擬變量c可被初始化為0(框1210)。此後，所述方法迭代地考慮指數B的每個位i。在每次迭代中，所述方法可以使用內循環來估算方程9(框1320)。此後，方法1300可以確定指數B的第i位(B[i])是否等於1。如果是的，則方法1300可以使用內循環來估算方程10(框1330)。當框1330的操作結束時，或者如果第i位不是1，那麼運算可以前進到下一次迭代。
在結束了最後的迭代後，方法1300可以對c值調用傳統的mod運算(框1340)。這個結果得到了ABmod n的結果。
可以使用前面參考圖1-3所描述的任何一種方法來執行運算的內循環。在內循環的處理期間，可以使用同一硬體來實現兩種情形。對適合平方運算的情形無需特殊的處理。一般來說，操作數c和mn具有同樣的大小，而a要小一些。
確定d和m為了確定參數d和m，可以如下確定n中有效位的數量size(n)，滿足2size(n)-1≤n＜2size(n)(11)另外，k可以相對於某個期望的精度值被定義為k＝size(n)+precision (12)此外，mn可被定義為n的整數倍m·n，使得d＝2k-mn＜n (13)參數mn在以二進位格式出現時，具有等於或超過精度值的前導1的數量。
為了根據n和2k得出m和d，注意mn=mn=int(2kn)n---(14)]]>其中，int(x)是得出某個值x的最大整數。為了得到m，可以使用Newton法ui+1＝(ui·(2k+1-ui-n))/2k(15)方程15具有以下性質ui＝(2k/n)，當i＝∞時 (16)

由於只想得到(2k/n)的整數部分，所以這一迭代過程收斂得很快。為了保持ui中位的數量最小，也可以在每次迭代後取得整數部分，並丟棄小數部分ui+1＝(ui·(2k+1-ui·n))/2k(17)這種實施方案有時會導致以下問題，即迭代過程在到達正確的數值之前停止。然而，稍稍修改最後的迭代就可以解決這個問題。
uFinal＝((uFinal-1+1)·(2k+1-uFinal-1·n)div2k在另一種實施方案中，僅通過從位置(k+1)往上將負數-(ui·n)的前導1設置為0，就可以完成(2k+1-ui·n)的計算，其中(ui·n)＜2k+1。這相當於保持從位置k到0的位不變。
在一種實施方案中，可以根據下列偽代碼用軟體來實現m和d的計算。


用於計算m＝(2kdiv n)和d＝(2k-mn)的算法其中，函數selectbits(max downto min，c)返回c中從max位置到min位置之間的位(包括max和min位置)。
以上給出的實施方案提供了一種mod運算的替代計算方式，標記為「emod」，該運算以丟失一定精度為代價，帶來少得多的計算花銷。在執行帶有乘法或指數運算的mod運算時，它是很有用的。通過對中間積使用emod運算，操作數長度可以保持在某一預定的長度窗內。當得到最終的乘積時，應用傳統的mod運算以獲得最終的結果。這種方案比只使用mod運算要花費少得多的處理量，就可以獲得最終的結果。
這裡具體圖示並描述了本發明的幾種實施方案。然而可以理解，本發明的修改和變化被以上教導所覆蓋，並落入所附權利要求書的範圍之內，而不會偏離本發明的精神和範圍。
權利要求
1.一種對操作數執行模數運算的方法，所述操作數由迭代執行的數學函數來表示，所述模數取值為n，所述方法包括在完成了多次中間迭代的每一次迭代後，使用一個等於n的倍數的假想模數來確定其結果的模數，所述假想模數接近於取某個任意k值的2k值，以及在完成了最終的迭代後，使用真正的模數n來確定其結果的模數。
2.一種求解(A·B)mod n運算的方法，包括對於B的幾個字中的每一個字，迭代地將c值移位一個字長；將移位後的c值與A·B[i]值相加，其中B[i]是B的第i個字，使用等於n的倍數的假想模數mn，對所述相加的結果執行emod運算，以及在最後一次迭代之後，對所述最後一次迭代所得到的相加結果執行模數運算。
3.一種求解(A·B)mod n運算的方法，包括對於B的幾個字中的每一個字，迭代地由c的先前估值的高次序部分生成商q，由所述c值的低次序部分生成餘數r，將c重新估值為A·B[i]+r+d·q，其中d是假想模數的精度值，其中B[i]是B的第i個字，在最後一次迭代之後，對所述最後一次迭代所得到的重新估值結果執行模數運算。
4.一種求解(A·B)mod n運算的方法，包括對於B的幾個字中的每一個字，迭代地由c的先前估值的高次序部分生成商q[i]，其中i代表當前迭代，由所述c值的低次序部分生成餘數r[i]，將商q[i-1]左移一個字寬，將c重新估值為A·B[i]+r[i]+d·q[i-1]，其中d是假想模數的精度值，其中B[i]是B的第i個字，並且所述重新估值過程使用移位後的商，在最後一次迭代之後，對所述最後一次迭代所得到的重新估值結果執行模數運算。
5.一種求解ABmod n運算的方法，包括對於B的每個位位置i，迭代地執行c＝(c·c)emod n運算，以及如果B的第i位位置是1，則執行c＝(c·A)emod n運算；以及在最後一次迭代之後，對所述最後一次運算所得到的c執行A mod N運算，其中，所述emod n運算根據假想模數mn來計算模數結果，其中mn是n的整數倍。
全文摘要
emod運算是對傳統的模數運算而言是一種計算上的替代，這是一種減少了計算花銷，但也降低了精度的運算。可以對某個基數n定義一種模數運算，此時，emod運算使用「假想模數」來確定操作數的模數，所述假想模數是n的整數倍。選擇假想模數，使得emod運算與模數運算相比，在計算上不那麼昂貴。因此，emod運算對於使用超大操作數的乘法或指數運算格外有用。在完成了與乘法或指數運算相關的中間處理後，可以使用一次傳統的模數運算，以得到最終的結果。
文檔編號G06F7/72GK1729444SQ03816215
公開日2006年2月1日 申請日期2003年5月2日 優先權日2002年5月9日
發明者埃裡克·霍斯泰德 申請人:英特爾公司