{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 fannian122333 的文章《模运算——开启密码学学习之路》','https://www.xiaopingtou.net/article-50930.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
模运算——开启密码学学习之路
综述：学完高数，线性代数，概率论，数学已经学了一大半，本以为数学的知识也就到此结束，但没有想到这只是自己自欺欺人。开始看导师密码学的论文的时候，第一眼就吓傻眼，模运算mod
，没想到还有数论这种东西存在，而且用处广泛。其中《密码编码学与网络安全》书中，我就见证其用处是无处不在，从奇偶数的判别到素数的判别，从模幂运算到最大公约数的求法，从费马定理到欧拉定理，从孙子问题到凯撒密码问题，从RSA密钥到椭圆曲线。无不充斥着模运算的身影，只怪自己是井底之蛙。于是乎要理解密码学和椭圆曲线，就得学习模运算。
基本概念：
概念：就是求余数，11 Mod 2，余数值为1；
数学上的定义：给定一个正整数p ，任意一个整数
n（正数,负数,0都行） ，一定存在等式n
= p*k+r （0≤r）（备注，这个式子很重要，后面许多性质都要用到这个等式） 例子：-11
mod 7 = 3；
部分且重要性质：（这里只列了几个需要证明的性质）
1.同余式：正整数a，b对p取模，它们的余数相同，记做
a ≡
b % p或者a
≡ b (mod p)。
2.若p|(a-b)，则a≡b
(mod p) 备注：（|是整除性符号，也就是（a- b）是p的因子）
证明：令a-b=kp;那么a=kp+b1;所以a mod p = kp+b mod
p =b mod ;所以a≡b (mod p)
3.结合率（(x+y )mod p +c）mod p =（x+
(y +c mod) p）mod p ;
证明：存在x= k1p +r1,y
= k2p+r2;c=k3p+r3；则代入等式左边，等于r1+r2+r3,等式右边也等于r1+r2+r3
。
4.非常重要的运算：加法逆元和乘法逆元
定义：加法逆元
（x+y）mod p =0
乘法逆元（x*y）mod p =1
举例：模8加法和乘法逆元
w
-w
W-1
0
0
不存在
1
7
1
2
6
不存在
3
5
3
4
4
不存在
5
3
5
6
2
不存在
7
1
7
重大运算规则：
费马定理：若p是素数，且a是正整数不能被p整除，意思是a,p
互素。
ap-1 ≡
1 mod p
构造素数 p
的完全剩余系 P ={1,2,3,4...p-1}
用a乘以集合中所有元素并对p去模，则得到X ={1a,2a,3a,4a...(p-1)a}
也是p的一个完全剩余系。由完全剩余系的性质，
1*2*3*...(p-1)=a*2a*3a*...a(p-1)
即 (p-1)!=(p-1)!ap-1
(mod p)
易知 ，同余式两边可约去(p-1)! ，得到ap-1
≡1
(mod p)
欧拉定理;
欧拉定理是在费马定理上进一步的扩展
所以证明和推理是 一样的，
但涉及到欧拉函数（解决给定一个正整数，在其内与它互为素数的个数）
aφ(n) ≡1
(mod n)
在欧拉函数中，当n为质数时，φ(n)=n-1;很好验证，比如你n=5，那么5以内有
1,2,3,4和5为互质，所以φ(5)=4；
中国剩余定理：
听说这个定理又叫做孙子定理，比较难懂，用来简化模计算，很牛逼的一个定理，可惜看了两遍没看懂它的证明过程。
熟悉的应用：
（1）加密解密的证明
对于明文分组M和密文分组C,加密和解密过程中
C =Me mod n; 式子（1）
M=Cd mod n; 式子（2）
其中收发双方均是已知n,发送方已知是e，只有接收方有d，公钥{e，n}，私钥{e,n},主要是为了证明如何证明式子（2），也就是接收方如何还原数据。
要证明这个M=Cd mod n=(Me mod
n)d mod n成立，
先证明Cd mod n=(Me mod
n)d mod = (Me)d
mod n
根据模的定义数学上的定义：给定一个正整数p ，任意一个整数
n（正数,负数,0都行） ，一定存在等式n
= p*k+r
令Me
=k*n+r
所以 (Me mod n)d
mod n = rd mod n
(Me)d=(k*n+r)d
泰勒展开，会发现除了rd，所有项都有k*n。所以(Me)d
mod n=(k*n+r)d
mod n =rd mod n
所以 (Me mod n)d
mod = (Me)d
mod n
接下来在证明 (Me)d
mod n = M
因为
n = pq
e满足gcd（φ(n)，e）=1；1φ(n)
ed ≡
1 mod
φ(n)；
d ≡
e-1mod (φ(n));d和e是模φ(n)的乘法逆元
所以 (Me)d
mod n = Mkφ(n)+1mod n=(M*Mkφ(n))
mod n
由欧拉定理得：aφ(n)+1≡
1 mod n
所以
(M*Mkφ(n)) mod n = M
所以 (Me)d
mod n = M
结合之上所证明得：M=(Me)d
mod n=(Me mod n)d
mod=Cd mod n
所以解密的式子（2）成立。
应用（2）-解决实际问题（循环类）
以下是朋友问我的一道经典题目，当时正好想到用模数的方法解决
问题：如图4个带指针的时钟A,B,C,D，每转动一个方位时，临近的两个时钟也会随之转动方位，例如A顺时针转90°，那么B，C,也会顺时针转动90°，那么问该怎么转动四个时钟，使四个指针都朝上。
解：这个问题挺有趣的但又不能一个个去尝试，而且这个问题有一定的可循环性。
分析可得，A总的要比其他三个多转动4k+1（这里假设都是顺时针）。假设A转动a次，B转动b次，C转动c次，D转动d次。
由 （a+b+c）mod 4 = 1
（a+b+d）mod 4 =
（c+b+d）mod 4 =
（c+a+d）mod 4 =0
故：a+b+c = 4k+1
a+b+d=4n
a+c+d =4m
b+c+d=4t
化简： b-c =4（n-m）
a-c=4（n-t）n-t
a-b =4（m-t）
求得其中的一个解：b =11,c= 3,a =7,d =2;
