快速乘法和減法模

我需要優化一些代碼，其中我通過標量模p（其中p是質數（2^32）-5）乘以整數（32位）的向量，然後減去來自另一個向量的矢量模p。快速乘法和減法模

的代碼看起來是這樣的：

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) { 
    for (int i = 0; i < equationToSubtractFrom.length; i++) { 
     equationToSubtractFrom[i] = modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i])); 
    } 
}

我使用的是多頭，因爲Java不支持無符號整數，但兩個矢量的模p所以你可以期待每一個數字爲0 < = X <（ 2^32）-5

任何想法來優化？ mod p操作佔用了大部分執行時間，所以優化這種方法的一種方式可能在乘法之後不能做modP，而只能在減法之後做。任何想法如何做到這一點？

來源

2011-10-27 Yrlec

使用2^32 = 5（mod p）的事實，可以加速計算並避免任何分割。

乘除法後，將結果分爲低（x％2^32）和hi（x/2^32）部分。然後將hi部分乘以5，並與低部分相加。然後再次重複此過程。如果結果大於p，則減去p。對於否定結果，請添加p。

編輯：由於組合的乘法和減法可能會溢出，所以乘法的結果也應該以模p爲模。但上述過程只有一步就足夠了：只需分割，乘以5，然後添加。

來源

2011-10-27 13:04:25

e - (f * e mod p) mod p = (e-e f) mod p

查看Wolfram Alpha。

來源

2011-10-27 10:35:00 Artefacto

謝謝。我試圖在乘法之後刪除mod p，但現在我的迴歸測試失敗了。我想我得到某種形式的溢出錯誤。我會更仔細地研究它。 – Yrlec

我知道有兩種方法可以做到這一點沒有使用部門或模量：

方法1：不變乘法。（see this paper）

這裏的基本思想是預先計算和近似的倒數p它允許你做一個整數除法只使用幾個整數乘法。然後你可以乘以返回並獲得你的模數。這是更容易實施的方法。

方法2：（在一個我通常使用），是使用浮點。將數字轉換爲浮點數並乘以預先計算的倒數p。然後舍入並轉換回整數。這種方法很難做到，但從我的經驗來看，如果做得好，速度會更快。

這裏的兩種方法除了在整數或浮點上預先計算倒數之外，不涉及任何分割。

無論這兩種方法中的哪一種比直接使用%都要快，這取決於您可以如何實施它們。所以我不能保證任何一個會更快。

來源

2011-10-27 10:42:16 Mysticial

快速乘法和減法模

回答

相關問題