37

私達はことを知っています

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

Pプライムはどこですか。

(A / B) % PどこA,Bが非常に大きくなり、オーバーフローする可能性があるかを計算する必要があります。

(A / B) % Pモジュラー算術のそのような種類の式は、とに当てはまりますか(A - B) % P。

そうでない場合は、正解を説明してください。

つまり、それは本当(A / B) % P = ((A % P) / (B % P)) % Pですか？

（N *（N ^ 2 + 5）/ 6）％Pを計算しようとしました。ここで、Nは10^15まで大きくなる可能性があります。

ここで、A = n *（n ^ 2 + 5）はn = 10^15で確実にオーバーフローする可能性があります

4

4 に答える 4

52

はい、しかしそれは異なります：

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

modb^(-1) mod pのモジュラ逆数はどこにありますか。の場合、。bpp = primeb^(-1) mod p = b^(p - 2) mod p

編集：

（N *（N ^ 2 + 5）/ 6）％P

これからのモジュラ逆数は必要ありません。分数を単純化するだけです：とN or N^2+5で割り切れるでしょう。だからそれらを分割すると、あなたは持っています。23(a*b) mod P

于 2012-09-02T10:39:46.537 に答える
6

ウラドの答えは正しいです：

(a - b) mod p = ((a mod p - b mod p) + p) mod p
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

これらおよびその他のいくつかの操作の概要は、「同等性」セクションにあります。

これは素数だけでなく機能することをお知らせしたいと思いますp。最初のものはどの場合でも機能しますp。2つ目は、モジュラ逆数が定義されているすべてpので機能します。b^(-1)

モジュラ逆数は、拡張ユークリッドアルゴリズムで計算できます

于 2016-02-23T23:30:09.687 に答える
0

アルゴリズムが何であれ、入力がAとBであり、それらがオーバーフローした場合、アルゴリズムを開始することはできません。それらの数字がどこから来ているのかを教えておくことが重要です。それらはあなたが持っている他の数の合計または積ですか？

大きな数の場合は、大きな数の場合は特別な数学ライブラリを使用する必要があります。任意の大きさの整数を処理する方法 このようなライブラリの可能性は、（A / B）％Pを実行できることです。

于 2012-09-02T10:19:00.543 に答える
0

以下は、2つの数値をモジュラー除算する別の方法です。

（A / B）％p =（A * Modular_inverse（B））％p

Also , 
int modular_inverse(int n, int p){
    return power(n, p-2, p);
}

int power(ll x, ll i,ll p)
{
int ans = 1;
while(i > 0){
    if(i&1)ans = (ans*x)%p;
     i >>=1;
     x = (x*x)%p;
   }
return ans;
}
于 2021-09-08T23:09:29.893 に答える