3

除算のモジュラスを見つけている間、私はプログラムで立ち往生しています。

たとえば、私が持っているとしましょう：

((a*b*c)/(d*e)) % n

ここで、単純に式を計算して n にモジュロすることはできません。これは、乗算と除算がループしており、値が long long に収まらないほど大きいためです。

コメントで明確にされているように、n は素数と見なすことができます。

乗算の場合、次のように簡単に計算できることがわかりました。

((a%n*b%n)%n*c%n)%n

しかし、除算部分の計算方法がわかりませんでした。

私が直面している問題は、簡単な例です。

((7*3*5)/(5*3)) % 11

上記の式の値は 7 になります

しかし、乗算をモジュロで計算すると、次のようになります。

((7%11)*(3%11))%11 = 10
((10%11)*(5%11))%11 = 6

今は 6/15 が残っており、正しい答えを生成する方法がありません。

誰かが私を助けてくれませんか。上記の例でロジックを理解してください。

4

7 に答える 7

5

11 は素数なので、Z 11は体です。15 % 11isであるため4、1/15等しい3( 3 * 4 % 11is は 1 であるため)。したがって、これは6/15mod 11 です。6 * 37

質問の下のコメントで、モジュラスが常に素数になることを明確にしています。

乗法逆元の表を効率的に生成するため2に、累乗を累乗して生成される値を確認できます。p が奇素数である体Z pでは、2 p-1 = 1であることに注意してください。したがって、Z 11については、次のようになります。

 2^1 = 2
 2^2 = 4
 2^3 = 8
 2^4 = 5
 2^5 = 10
 2^6 = 9
 2^7 = 7
 2^8 = 3
 2^9 = 6

5したがって、 (2 4 )の乗法逆数は 2 6 (9) です。

したがって、上記の表は次のように生成できます。

power_of_2[0] = 1;
for (int i = 1; i < n; ++i) {
    power_of_2[i] = (2*power_of_2[i-1]) % n;
}

また、乗法逆テーブルは次のように計算できます。

mult_inverse[1] = 1;
for (int i = 1; i < n; ++i) {
    mult_inverse[power_of_2[i]] = power_of_2[n-1-i];
}
于 2013-07-09T22:01:12.447 に答える
2

あなたの例では、15 = 4 mod 11 であるため、実際には (6/4) mod 11 を評価する必要があります。

これに対する正確な解を見つけるには、6 = ( (x * 4) mod 11) のように並べ替えます。これにより、モジュロ除算がどのように機能するかがより明確になります。

他に何もなければ、係数が常に小さい場合は、0 から係数 -1 まで反復して解を得ることができます。

モジュラスが素数でない場合、簡約問題には複数の解が存在する可能性があることに注意してください。たとえば、4 = ( ( x * 2) mod 8) には 2 と 6 の 2 つの解があります。これは、形式の簡約問題で発生します。

  a = ( (x * b) mod c)

b と c が互いに素でない場合 (つまり、それらが公約数を共有する場合)。

同様に、b と c が互いに素でない場合、簡約問題の解がない可能性があります。たとえば、3 = ( (x * 2) mod 8) には解がありません。これは、b と c の最大公約数が a も割らない場合に発生します。

これらの後者の 2 つの状況は、n が素数でない場合、0 から n-1 までの整数が乗算でグループ (または同等に、+ と * の下の体)を形成せず、単に環のあまり有用でない構造を形成する結果です。

于 2013-07-09T22:14:42.443 に答える
2

n は素数なので、整数 b の除算は単純に b の逆数を掛けることになります。あれは：

(a / b) mod n = (a * inv(b)) mod n

どこ

inv(b) = (b ^ (n - 2)) mod n

inv(b) の計算は、二乗アルゴリズムによる指数を使用して O(log(n)) 時間で実行できます。コードは次のとおりです。

int inv(int b, int n)
{
    int r = 1, m = n - 2;
    while (m)
    {
        if (m & 1) r = (long long)r * b % n;
        b = (long long)b * b % n;
        m >>= 1;
    }
    return r;
}

なぜそれが機能するのですか？フェルマーの小定理によれば、n が素数の場合、任意の正の整数 b に対して b ^ (n - 1) mod n = 1 となります。したがって、inv(b) * b mod n = 1 となります。

inv(b) を見つけるためのもう 1 つの解決策は、拡張ユークリッド アルゴリズムです。このアルゴリズムを実装するには、もう少しコードが必要です。

于 2013-07-11T03:50:54.903 に答える
0

次のように分割を配布できると思います

z = d*e/3
(a/z)*(b/z)*(c/z) % n

整数除算の問題だけが残ります。

于 2013-07-09T21:59:34.690 に答える