1

もちろん、GMPライブラリやその他の多数の任意精度ライブラリを使用するなど、これに対する簡単な解決策があることは知っています。これは授業用なので、これらのルートを使用することはできません。すべての操作を構築した後、RSA 暗号化スキームを実行できるようになります。

ベクトルを使用して、バイナリで表された n ビットの数値を格納しています。後で 10 進数に変換しますが、2 進数を操作し、表示用にのみ変換する必要があります。

足し算、引き算、掛け算の実装に成功しました。私は除算と剰余演算に固執しています...特に剰余累乗です。少なくとも基本的なレベルではアルゴリズムを理解していますが、それを任意の長さの数値で機能するコードに変換することはできないようです。外部ライブラリなしで c++ で行われたこのタイプの作業の例を見つけることができないようです。

具体的な質問:

私が書いている除算関数を呼び出して、返された剰余を使用する以外に、n ビットの数値でモジュラスを実行するより良い方法はありますか?

GMP ソース コードをまったく理解できないので、良い C++ の例をいくつか見てみたいと思います。

勉強するための良いリソースや助けをいただければ幸いです。ありがとう

4

1 に答える 1

1

除算を使用してモジュラス演算を偽造できます。モジュラス操作は次と同等です。

v = n - (n / m) * m

ここで、n は除数、m はモジュラス、v は出力値 (すべて任意精度の数値) です。

除算に行き詰まっている場合は、手動で長い除算を実行するように実装できます。(中学校で乗算と減算を使用してこれを行う方法を学習している必要があります。プロセスを基数 2 に変換するのは簡単です。行き詰まっている場合は、紙の上でいくつか実行してください。より効率的なアルゴリズムが必要な場合は、おそらく「任意精度分割アルゴリズム」などをグーグルで検索して見つけてください）

モジュラスが得られたら、二乗を繰り返して剰余累乗を計算できます。大きな整数 X を 67 乗、mod N で計算する様子を観察してください。

v1  = X mod N         // X^1 mod N
v2  = v1  * v1  mod N // X^2 mod N
v4  = v2  * v2  mod N // X^4 mod N
v8  = v4  * v4  mod N
v16 = v8  * v8  mod N
v32 = v16 * v16 mod N
v64 = v32 * v32 mod N // X^64 mod N

v66 = v64 * v2  mod N // X^66 mod N
v67 = v66 * v1  mod N // X^67 mod N

数学的に、これが理にかなっている理由がわかります。このアルゴリズムは、剰余累乗を計算するために一般的に選択されるアルゴリズムであり、指数のサイズに対して対数、底のサイズに対して対数の時間と空間で動作します (つまり、巨大な数に対しても高速です)。

PS外部ライブラリの使用を許可しないのはばかげていると教授に伝えてください。プログラマーが学べる最も重要なことの 1 つは、いつ怠けるかということです (つまり、独自のソリューションを自作するのではなく、何かを行うためにライブラリを見つけて使用するとき)。

于 2012-09-26T19:31:40.843 に答える