6

5^65537時間を乗算する代わりに計算したい5 65537場合は、 を実行することをお勧めします((5^2)^16)*5。これにより、16 回の 2 乗と 1 回の乗算が行われます。
しかし、私の質問は、非常に大きな数を 2 乗することで 2 乗回数を補っているのではないでしょうか? コンピューターの基本的なビット乗算に進むと、これはどのように高速になりますか。
コメントを読んだ後、私はこの疑問を持っています：

     How is the cost of each multiplication not dependant on the size. because when
multiplying the number of bits of the multiplier will increase and this will increase the 
number of additions and the number of left shifts.
4

1 に答える 1

12

乗算演算をカウントします。

5^65537 = 65537 multiplications
((5^2)^16)*5 = (2 + 16 + 1) = 19 multiplications.

このことから、乗算はより大きな数で機能しているにもかかわらず、これははるかに少ない作業であることがわかります。このアルゴリズムはSquare and Multiply と呼ばれます。

実際には、このような大きな数を計算する必要がある暗号システムは、 Modular Exponentiationと呼ばれる手法を使用して、巨大な中間数を回避します。

于 2012-04-12T05:14:49.630 に答える