實現模運算的更好方法（算法問題）

我一直在試圖最近實現模指數運算。我正在用VHDL編寫代碼，但我正在尋找更具算法性的建議。模冪指數器的主要組成部分是模乘器，我也必須自己實現。我對乘法算法沒有任何問題 - 它只是增加和移位，我已經做了一個很好的工作，弄清楚我的所有變量是什麼意思，這樣我就可以在相當合理的時間內繁殖。實現模運算的更好方法（算法問題）

我遇到的問題是在乘法器中實現模數運算。我知道執行重複減法是可行的，但它也會很慢。我發現我可以改變模數來有效地減去模的大倍數，但我認爲可能還有更好的方法來做到這一點。我使用的作品像這樣的算法（怪異的僞代碼如下）：

result,modulus : integer (n bits) (previously defined) 
shiftcount : integer (initialized to zero) 
while((modulus<result) and (modulus(n-1) != 1)){ 
    modulus = modulus << 1 
    shiftcount++ 
} 
for(i=shiftcount;i>=0;i--){ 
    if(modulus<result){result = result-modulus} 
    if(i!=0){modulus = modulus >> 1} 
}

所以...這是一個很好的算法，或者至少一個良好的開端？維基百科沒有真正討論用於實現模運算的算法，並且每當我嘗試在其他地方搜索時，我都會發現真正有趣但卻難以置信的複雜（通常不相關）的研究論文和出版物。如果有一種明顯的方式來實現我沒有看到的，我真的很感激一些反饋。

來源

2010-05-05 ryxxui

是本顯著比乘法慢？它似乎不應該是;你有相同的基本組件。 – 2010-05-05 14:26:30

順便說一句，我也對數學家如何越來越多地撰寫維基百科文章感到沮喪。僅僅因爲使用高級概念和表示法可以很容易地表達出來並不意味着這是解釋它的最好方式;-)它與Stackoverflow上的討論和Mathoverflow上的討論類似。 – phkahler 2010-05-05 15:04:17

對於模數本身，我不確定。作爲更大的模塊化指數運算的一部分，模塊可以按照modular exponentiation上的維基百科頁面中提到的方式查找Montgomery multiplication？自從我研究這種類型的算法以來已經有一段時間了，但是從我記得的情況來看，它通常用於快速模冪運算。

編輯：爲什麼它的價值，你的模算法似乎乍一看OK。你基本上正在做分割這是一個重複的減法算法。

來源

2010-05-05 13:56:48

我不確定你在計算那裏是誠實的。你說的是模運算，但通常一個模運算在兩個數字a和b之間，其結果是a除以b的餘數。僞代碼中的a和b在哪裏？

無論如何，也許這會幫助：a mod b = a - floor(a/b) * b。

我不知道這是否更快，這取決於你是否可以比許多減法更快地進行除法和乘法運算。

加速減法方法的另一種方法是使用二分法搜索。如果你想要a mod b，你需要從a減去b，直到a小於b。所以基本上你需要找到k這樣的：

a - k*b < b, k is min

一個辦法，找出這k是線性搜索：

k = 0; 
while (a - k*b >= b) 
    ++k; 

return a - k*b;

但你也可以二進制搜索它（只跑了幾個測試但它在所有這些工作）：

k = 0; 
left = 0, right = a 
while (left < right) 
{ 
    m = (left + right)/2; 
    if (a - m*b >= b) 
     left = m + 1; 
    else 
     right = m; 
} 

return a - left*b;

我猜二元搜索解決方案將是最快的時候交易大數字。

如果要計算a mod b，僅a是一個很大的數字（你可以在原始數據類型存儲b），你可以做到這一點甚至更快：

for each digit p of a do 
    mod = (mod * 10 + p) % b 
return mod

這工作，因爲我們可以寫a作爲a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...

我認爲二進制搜索是你要找的。

來源

2010-05-05 14:13:37 IVlad

OP基本上是在做分割算法（通過重複減法，這是你如何在低級別進行分割）。當有一個乘法步驟時，二進制搜索將不會加快速度（當您在低級別進行分割時，二進制搜索的速度與分割一樣長）。 – 2010-05-05 14:23:45

@Jason S - 我不太確定OP在做什麼，但是在我看來，他的'while'循環可以用二進制搜索替代。 – IVlad 2010-05-05 14:28:23

這是非常低層次的門邏輯。移動是簡單，快速和簡單的。二進制搜索不是。 – 2010-05-05 16:06:02

如果您正在使用shift-and-add進行乘法運算（這絕不是最快的方法），那麼可以在每個加法步驟後執行模運算。如果總和大於模數，則減去模數。如果你可以預測溢出，你可以同時進行加法和減法。在每個步驟中進行模數還會減小乘數的整體大小（與輸入相同的長度而不是雙倍）。

你正在做的模數的移動讓你走向完整的除法算法（模只取其餘部分）。

編輯這是我在Python實現：

 
def mod_mul(a,b,m): 
    result = 0 
    a = a % m 
    b = b % m 
    while (b>0): 
     if (b&1)!=0: 
      result += a 
      if result >= m: result -= m 
     a = a << 1 
     if a>=m: a-= m 
     b = b>>1 
    return result

這只是模乘法（結果= A * B模m）。頂部的模運算是不需要的，但是提醒算法假設a和b小於m。

當然，對於模冪運算，您將有一個外循環在每一步進行平方或乘法的整個操作。但我認爲你知道這一點。

來源

2010-05-05 14:56:11 phkahler

這有一個額外的好處：如果每個數字在你向左移一位之前小於模數，那麼左移一位（這是數字的兩倍）的數字不能超過模數的兩倍，這意味着你只需要在這些步驟中減去一次模量。 – 2010-05-08 20:52:38

是的，我已經澄清，與一些工作python代碼:-) – phkahler 2010-05-10 01:15:32

那測試(modulus(n-1) != 1) //有點測試？

- 看起來多餘的與(modulus<result)結合在一起。

爲硬件實現設計我會意識到比意味着更多邏輯（減法）的測試小於/大於比特運算和零分支。

如果我們可以很容易做到按位測試，這可能是快速：

m=msb_of(modulus) 

while(result>0) 
{ 
    r=msb_of(result) //countdown from prev msb onto result 
    shift=r-m  //countdown from r onto modulus or 
        //unroll the small subtraction 

    takeoff=(modulus<<(shift)) //or integrate this into count of shift 

    result=result-takeoff; //necessary subtraction 

    if(shift!=0 && result<0) 
    { result=result+(takeoff>>1); } 

    } //endwhile 

if(result==0) { return result } 
else   { return result+takeoff }

（未測試的代碼可能包含陷阱）

result是repetively遞減通過modulus轉移到匹配最多顯著位。

在每次減法之後：result具有丟失超過1msb的約50/50的機會。它也有〜50/50的機率，加上減去的一半，總是會再次變爲正值。 >應當放回陽性如果移位是不等於0

工作循環退出時result是防鑽撞和「轉向」爲0

來源

2010-05-08 20:27:08 strainer

實現模運算的更好方法（算法問題）

回答

相關問題