#每日三件事，第2012天#
模运算就是一个整数m，对模数n，计算余数。即：m mod n。模运算有如下性质：
（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
模运算的结果永远在[0 -(n-1)]之间。
模运算是针对整数的运算。那么对于分数和其他一些特殊情况，比如，怎么计算呢？
1.分数求模运算
比如计算, 可以写成
,根据费马小定理，a和p互素，则有
，
前提条件是a和p互素。
- 分数幂次方求模运算
比如计算，同理使用费马小定理，a和p互素，则有
，乘以
则有：
在计算二次模余方程的根时，先计算是否是平方剩余，利用公式，如果结果为1，则是平方剩余，有平方根；否则没有。平方根为
，
不一定是整数，出现分数的可能性极大。因此需要根据费马小定理来计算幂为分数的模。
此为最近学习公钥密码算法时的一点体会。
