素数を法とする速い乗算と減算

Question

スカラーモジュロp（pは素数（2^32）-5）でintのベクトル（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は符号なし整数をサポートしていないので、私はlong型を使用していますが、あなたはすべての数は= X ことを期待することができますので、両方のベクトルはモッズpは2^32）-5

これを最適化する方法はありますか？ mod p演算は実行時間の大部分を占めているので、これを最適化する方法の1つは、乗算後にmodPを実行せず、減算後に行うだけです。どのようにそれを行う上の任意のアイデアですか？

Answer 1

2^32 = 5（mod p）という事実を利用して計算を高速化し、分割を回避することは可能です。

乗算および減算の後、結果を低（x％2^32）および高（x/2^32）部分に分割します。次に、hi部分に5を掛け、低い部分と合計します。次に、この手順をもう一度繰り返します。結果がpより大きい場合は、pを減算します。否定結果の場合は、pを追加します。

編集：結合された乗算と減算がオーバーフローする可能性があるため、乗算の結果もpを法とする必要があります。しかし、上記の手順の1ステップだけで十分です。分割し、5に掛けて加算します。

Answer 2

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

Wolfram Alphaを参照してください。

Answer 3

私は分裂や弾性係数を使用せずにこれを行うには、2つの方法を知っている：

方法1：不変乗算。 （see this paper）

ここでの基本的な考え方は、pの逆数をあらかじめ計算して近似することです。整数乗算を使用して整数除算を行うことができます。次に、乗算してモジュラスを得ることができます。これは実装が容易なアプローチです。

方法2：（I通常使用するもの）、浮動小数点を使用することです。数値を浮動小数点に変換し、あらかじめ計算された逆数pで乗算します。その後、丸めて整数に変換し直します。このアプローチは正解するのが難しいですが、私の経験からは適切に実行すれば速くなります。

ここでの両方のアプローチは、整数または浮動小数点のいずれかの逆数の事前計算を除いて除算を含まない。

これらの方法のどちらを使用するかは、直接的な使用よりも高速であるかどうか（%）、それらを実装する方法によって異なります。だから私はいずれかがより速くなることを保証することはできません。