演算法中mod是什麼意思？

在演算法中，mod的意思是取模，就是取餘數。 mod運算，即求餘運算，是在整數運算中求一個整數x除以另一個整數y的餘數的運算，且不考慮運算的商數。

mod運算，即求餘運算，是在整數運算中求一個整數x 除以另一個整數y的餘數的運算，且不考慮運算的商。在電腦程式設計中都有MOD運算，其格式為： mod(nExp1,nExp2)，即是兩個數值運算式作除法運算後的餘數。

模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。

模p減法：(a-b) mod p ，其結果是a-b算術差除以p的餘數。

模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
交換律	(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)

若(r1 r2) >= p ，則

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

否則

(a b) mod p = (r1 r2)

再和c進行模p和運算，得到

結果為r1 r2 r3 的算術和除以p的餘數。

對右邊進行計算可以得到同樣的結果，得證。

模p相等

若兩個數a、b滿足a mod p = b mod p，則稱他們模p相等，記做

a ≡ b (mod p)

可以證明，此時a、b滿足a = kp b，其中k為某個整數。

對於模p相等和模p乘法來說，有一個和四則運算中迥然不同的規則。在四則運算中，如果c是非0整數，則

ac = bc 可以得到a =b

但是在模p運算中，這種關係不存在，例如：

(3 x 3) mod 9 = 0

(6 x 3) mod 9 = 0

但

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以外的公因子，因此上式要成立必須滿足下面兩個條件中的一個

1) c能整除k

2) a = b

#如果2不成立，則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 顯然成立

#得證

更多相關知識，請造訪：PHP中文網！

以上是演算法中mod是什麼意思？的詳細內容。更多資訊請關注PHP中文網其他相關文章！