#每日三件事，第2012天#

模運算就是一個整數(shù)m，對模數(shù)n，計算余數(shù)。即：m mod n。模運算有如下性質(zhì)：

（1）若q|(a-b)，則a≡b (mod q) , 11 ≡4 (mod 7) , 18 ≡ 4(mod 7)
（2）(a mod q) = (b mod q) 意味a≡b mod q
（3）對稱性，a≡b mod q等價于b≡a mod q
（4）傳遞性，若a≡b mod q 且b≡c mod q ，則a≡c mod q

模運算的結(jié)果永遠(yuǎn)在[0 -(n-1)]之間。

模運算是針對整數(shù)的運算。那么對于分?jǐn)?shù)和其他一些特殊情況，比如，怎么計算呢？

1.分?jǐn)?shù)求模運算

比如計算, 可以寫成 ,根據(jù)費馬小定理，a和p互素，則有 ，

前提條件是a和p互素。

2. 分?jǐn)?shù)冪次方求模運算

比如計算，同理使用費馬小定理，a和p互素，則有 ，乘以則有：

在計算二次模余方程的根時，先計算是否是平方剩余，利用公式，如果結(jié)果為1，則是平方剩余，有平方根；否則沒有。平方根為，不一定是整數(shù)，出現(xiàn)分?jǐn)?shù)的可能性極大。因此需要根據(jù)費馬小定理來計算冪為分?jǐn)?shù)的模。

此為最近學(xué)習(xí)公鑰密碼算法時的一點體會。