首頁  >  文章  >  演算法中mod是什麼意思?

演算法中mod是什麼意思?

青灯夜游
青灯夜游原創
2020-08-29 12:43:4638609瀏覽

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

演算法中mod是什麼意思?

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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn