アルゴリズムにおける mod とは何ですか?

アルゴリズムでは、mod は剰余を求めることを意味します。 mod演算、つまり剰余演算とは、整数演算において、整数xを整数yで割ったときの商を考慮せずに余りを求める演算です。

mod 演算、つまり剰余演算は、整数演算において整数 x を別の整数 y で割った余りを求める演算です。演算の商。コンピュータープログラミングには MOD 演算があり、その形式は mod(nExp1,nExp2) で、これは 2 つの数式を除算した余りです。

モジュロ p 演算エディタ

正の整数 p と任意の整数 n が与えられると、次の方程式が存在する必要があります。

n = kp r ここで、 k 、 r は整数で、0 ≤ r

正の整数 p と整数 a および b について、次の演算が定義されます。

モジュロ演算: a mod p は、a を p で割った余りを表します。

加算法 p: (a b) mod p、結果は a b を p で割った算術合計の剰余です。つまり、(a b) = kp r の場合、(a b) mod p = r となります。

modul p 減算: (a-b) mod p、結果は算術差 a-b を p で割った余りです。

Modul p 乗算: (a × b) mod p、結果は a × b 算術乗算を p で割った余りになります。

モジュラー p 演算には、次のような通常の四則演算と多くの類似したルールがあることがわかります。

結合法則	((a b) mod p c)mod p = (a (b c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p
COMmutativity	(a b) mod p = (b a ) mod p (a × b) mod p = (b × a) mod p
##分配法則	((a b)mod p × c) mod p = ((a × c) mod p (b × c) mod p) mod p (a×b) mod c= (a mod c * b mod c) mod c (a b) mod c=(a mod c b mod c) mod c (a-b) mod c=(a mod c- b mod c ) mod c

最初の式の簡単な証明:

((a b) mod p c) mod p = (a (b c) mod p) mod p

仮定

a = k1*p r1

b = k2*p r2

c = k3*p r3

a b = (k1 k2) p (r1 r2)

If (r1 r2) >= p、then

(a b) mod p = (r1 r2 ) -p

それ以外の場合は

#(a b) mod p = (r1 r2)

次に、c を使用して modulo p sum 演算を実行すると、結果は

r1 r2 r3 の算術和を p で割った余り。

右辺を計算しても同じ結果が得られ、証明が得られます。

等しい法 p

2 つの数値 a と b が a mod p = b mod p を満たす場合、それらは等しい法 p であると言われ、次のように表されます。 as

a ≡ b (mod p)

このとき、a と b は a = kp b を満たすことが証明できます (k は整数)。

p を法とする等価と p を法とする乗算では、四則演算とはまったく異なる規則があります。四則演算では、c が 0 以外の整数の場合、a =b

として

ac = bc が得られますが、剰余 p 演算ではこの関係は得られません。例:

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

But

3 mod 9 = 3

6 mod 9 =6

定理 (消去法): gcd(c,p) = 1 の場合、ac ≡ bc mod p は a ≡ (b mod p を推定できます) )

証明:

なぜなら、ac ≡ bc (mod p)

だから、ac = bc kp、つまり、c(a-b) = kp

c と p は 1 以外の共通因数で割られていないため、 c|kp

c と p には共通因数がないため、c|k であることは明らかであり、したがって k = ck'

したがって、c(a-b)=kp は c(a-b) =ck'p

したがって、a-b = k'p となり、a ≡ b (mod p)

となります。 a = b の場合、a ≡ b mod p は明らかに true

得证

関連知識の詳細については、

PHP中文网

をご覧ください。

以上がアルゴリズムにおける mod とは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。