c# - 数値を手動で変更する簡単な方法

Question

a と b の非常に大きな値に対して (a^b) % c を計算できるようにする必要があります (これらは個別に限界を押し上げており、a^b を計算しようとするとオーバーフロー エラーが発生します)。十分に小さい数の場合、単位 (a^b)%c = (a%c)^b%c を使用すると機能しますが、c が大きすぎる場合、これは実際には役に立ちません。mod 操作を 1 つずつ手動で行うループを作成しました。

private static long no_Overflow_Mod(ulong num_base, ulong num_exponent, ulong mod) 
    {
        long answer = 1;
        for (int x = 0; x < num_exponent; x++)
        {
            answer = (answer * num_base) % mod;
        }
        return answer;
    }

しかし、これには非常に長い時間がかかります。実際に a を b 乗する必要がなく、かつ時間のかかるループを使用せずに、この操作を行う簡単で高速な方法はありますか? 他のすべてが失敗した場合は、巨大なデータ型を表す bool 配列を作成し、ビットごとの演算子でこれを行う方法を見つけることができますが、もっと良い方法が必要です。

Answer 1

私はあなたが探していると思います: http://en.wikipedia.org/wiki/Montgomery_reduction または Modular Exponentiation (ウィキペディアから) に基づくより簡単な方法

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;

    while (exponent > 0) {
        if ((exponent & 1) == 1) {
            // multiply in this bit's contribution while using modulus to keep result small
            result = (result * base) % modulus;
        }
        // move to the next bit of the exponent, square (and mod) the base accordingly
        exponent >>= 1;
        base = (base * base) % modulus;
    }

    return result;
}

Answer 2

Fast Modular Exponentiation（私はそれが呼ばれているものだと思います）が機能するかもしれません。

与えられたa、b、cおよびa ^ b（mod c）：

1. bを2の累乗の合計として記述します（b = 72の場合、これは2 ^ 6 + 2 ^ 3です）。
2.実行：
    （1）a ^ 2（mod c）= a *
    （2）（a *）^ 2（mod c）= a *
    （3）（a *）^ 2（mod c）= a *
    ..。
    （n）（a *）^ 2（mod c）= a *

3.上からa*を使用して、識別した2の累乗にa*を掛けます。例えば：
    b = 72、3でa *を使用し、6でa*を使用します。
    a *（3）xa *（6）（mod c）

4.前のステップを一度に1回乗算すると、最後にa ^ b％cになります。

さて、データ型でそれをどのように行うのか、私にはわかりません。あなたのデータ型がc^2をサポートできる限り、私はあなたが大丈夫だと思います。

文字列を使用する場合は、加算、減算、乗算の文字列バージョンを作成するだけです（それほど難しくはありません）。この方法は、それを行うのに十分速いはずです。（そして、mod cによってステップ1を開始して、aがcより大きくならないようにすることができます）。

編集：ああ、べき乗剰余に関するwikiページを見てください。

Answer 3

Python には (a**b)%c を返す pow(a,b,c) があります (より速いだけです)。多分彼らはあなたが言ったアイデンティティをするだけです.

Answer 4

あなたはこれを試すことができます：

C＃：非常に大きな数（> Int64.MaxValue）でモジュラス（mod）演算を実行する
http://www.del337ed.com/blog/index.php/2009/02/04/c-doing-a-modulus- mod-operation-on-a-very-large-number-int64maxvalue /

Answer 5

パワーとMODの間にはある種の関係があるように私には思えます。べき乗は掛け算の繰り返しであり、mod は割り算に関係しています。掛け算と割り算が逆であることはわかっているので、その関係から、べき乗と mod の間には相関関係があると思います。

たとえば、5 の累乗を取ります。

5 % 4 = 1
25 % 4 = 1
125 % 4 = 1
625 % 4 = 1
...

パターンは、b のすべての値に対して 5 ^ b % 4 = 1 であることは明らかです。

この状況ではあまり明確ではありません:

5 % 3 = 2
25 % 3 = 1
125 % 3 = 2
625 % 3 = 1
3125 % 3 = 2
15625 % 3 = 1
78125 % 3 = 2
...

しかし、まだパターンがあります。

パターンの背後にある計算を行うことができれば、実際のパワーを実行せずに mod の価値を把握できたとしても、私は驚かないでしょう。

Answer 6

'a' を十分に小さい数に因数分解してみることができます。

「a」の因数が「x」、「y」、「z」の場合、

a^b = (x^b)(y^b)(z^b)。

次に、ID を使用できます: (a^b)%c = (a%c)^b%c

Answer 7

暗号の宿題のようです。

ヒント:フェルマーの小定理を調べてください。