在演算法中,mod的意思是取模,就是取餘數。 mod運算,即求餘運算,是在整數運算中求一個整數x除以另一個整數y的餘數的運算,且不考慮運算的商數。
mod運算,即求餘運算,是在整數運算中求一個整數x 除以另一個整數y的餘數的運算,且不考慮運算的商。在電腦程式設計中都有MOD運算,其格式為: mod(nExp1,nExp2)
,即是兩個數值運算式作除法運算後的餘數。
模p運算編輯
給定一個正整數p,任一個整數n,一定存在等式
n = kp r 其中k 、r是整數,且0 ≤ r < p,稱呼k為n除以p的商,r為n除以p的餘數。
對於正整數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中文網其他相關文章!