15

最近、モジュラー指数関数を実装しようとしています。私は 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}
}

それで...これは良いアルゴリズムですか、それとも少なくとも始めるのに良い場所ですか? ウィキペディアではモジュロ演算を実装するためのアルゴリズムについてはあまり議論されていません。他の場所を検索しようとすると、非常に興味深いが信じられないほど複雑な (そして多くの場合無関係な) 研究論文や出版物を見つけることができます。私が見ていないこれを実装する明白な方法がある場合は、フィードバックをいただければ幸いです。

4

5 に答える 5

13

正直なところ、あなたがそこで何を計算しているのかわかりません。モジュロ演算について話しますが、通常、モジュロ演算は と の 2 つの数値の間で行われa、bその結果は で割った余りになりaますb。aandbは疑似コードのどこにありますか?

とにかく、これが役立つかもしれません: a mod b = a - floor(a / b) * b.

これが速いかどうかはわかりません。多くの減算よりも除算と乗算を高速に実行できるかどうかに依存します。

減算アプローチを高速化する別の方法は、二分探索を使用することです。必要に応じて、が よりも小さくなるまでからa mod b減算する必要があります。したがって、基本的に次のようなものを見つける必要があります。baabk

a - k*b < b, k is min

これを見つける 1 つの方法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しかない場合 (プリミティブ データ型に格納できます)、さらに高速に実行できます。ab

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-05T14:13:37.400 に答える
6

乗算に shift-and-add を使用している場合 (これは決して最速の方法ではありません)、各加算ステップの後にモジュロ演算を実行できます。合計がモジュラスより大きい場合は、モジュラスを引きます。オーバーフローを予測できれば、加算と減算を同時に行うことができます。各ステップでモジュロを実行すると、乗数の全体的なサイズも縮小されます (2 倍ではなく入力と同じ長さ)。

あなたがしているモジュラスのシフトは、完全な除算アルゴリズムに向けてほとんどの道を歩んでいます（モジュロは残りを取るだけです）。

EDIT 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

これは単なる剰余乗算 ( result = a*b mod m) です。上部のモジュロ演算は必要ありませんが、アルゴリズムが を想定しており、 未満であることを思い出しaてbくださいm。

もちろん、剰余累乗の場合は、二乗または乗算を実行する各ステップでこの操作全体を実行する外側のループがあります。しかし、あなたはそれを知っていたと思います。

于 2010-05-05T14:56:11.440 に答える
0

そのテスト(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 }

(テストされていないコードには落とし穴が含まれている可能性があります)

resultmodulus最上位ビットに一致するようにシフトすることにより、繰り返しデクリメントされます。

各減算後: result~50/50 の確率で 1 msb 以上を失います。また、マイナスになる可能性も 50/50 あります。差し引いた分の半分を足すと、常に再びプラスになります。> shift が 0 でない場合は正に戻す必要があります

resultがアンダーランで、'shift' が 0 の場合、ワーキング ループは終了します。

于 2010-05-08T20:27:08.383 に答える
0

モジュロ自体については、よくわかりません。より大きな剰余指数演算の一部としての剰余については、剰余累乗に関するウィキペディアのページで言及されているように、モンゴメリー乗算を調べましたか? このタイプのアルゴリズムを調べてからしばらく経ちましたが、私が思い出す限り、高速剰余べき乗で一般的に使用されています。

編集:一見すると、モジュロアルゴリズムは問題ないように見えます。基本的には、繰り返し減算アルゴリズムである除算を行っています。

于 2010-05-05T13:56:48.207 に答える