🌊 作者主页：海拥
🌊 简介：🏆CSDN全栈领域优质创作者、🥇HDZ核心组成员、🥈蝉联C站周榜前十
🌊 粉丝福利：粉丝群 每周送6~9本书，不定期送各种小礼品，往期获奖公布

@TOC

同余

设整数a，b，n(n ≠0)，如果a-b是n的整数倍，则a≡b(mod n)，即a同余于b模n。也可理解为a/n的余数等于b/n的余数。
(mod n)运算将所有的整数(无论小于n还是大于n)，都映射到{0,1,…,n-1}组成的集合。
模算术的性质：
(a mod n) + (b mod n) = (a+b) mod n
(a mod n) - (b mod n) = (a-b) mod n
(a mod n) * (b mod n) = (a*b) mod n

性质

性质一、有整数a，b，c，n(n ≠0)：
如果a≡b(mod n)， b≡c(mod n) 那么a≡c(mod n) (传递性)

==证明==： 因为a≡b(mod n)，b≡c(mod n)，
即a=b+k1n，b=c+ k2n，
所以a=c+ k2n+k1n=c+(k1+k2)n，
即a等于c加上n的整数倍，即a≡c(mod n)。

性质二、如果a≡b(mod n)， c≡d(mod n) 那么：
a+c≡b+d(mod n)， a-c≡b-d(mod n)， ac≡bd (mod n)

==证明==：ac≡bd (mod n) 因为a≡b(mod n)， c≡d(mod n)， 即a=b+k1n，c=d+k2n，
所以，ac=(b+k1n)(d+k2n)=bd+(bk2+dk1+nk1k2)n, 其中K=(bk2+dk1+nk1k2)为整数，
即：ac=bd+Kn，即：ac≡bd (mod n)。

除法

设整数a，b，c，n(n ≠0)，且gcd(a, n)=1。
如果ab≡ac (mod n)，那么b≡c (mod n)（消去律）

==证明==：∵ gcd(a, n)=1，∴有x和y，使ax+ny=1 两边同乘以(b-c): (b-c)(ax+ny)=b-c
即:(ab-ac)x+n(b-c)y=b-c ……① ∵ ab≡ac (mod n), 即ab=ac+k1n, ∴ab-ac
是n的倍数 同时，n(b-c)y显然也是n的倍数 所以，:(ab-ac)x+n(b-c)y也是n的倍数，假设是k2倍 则①式变为：b-c=
k2n 即b≡c (mod n) 模运算消去律基础

欧几里德算法(Euclid)

求最大公约数，辗转相除直到余数为零
对于任意非负整数a和任意正整数b，有： gcd(a,b) = gcd(b,a mod b)
求：gcd(482,1180)

保证机密性

Kae ：Alice的加密秘钥
Kad： Alice的解密秘钥
Kbe： Bob的加密秘钥
Kbd ：Bob的解密秘钥

保证真实性

Kad： Alice的私钥
Kae ：Alice的公钥

既保证机密性又保证真实性

Kad： Alice的私钥
Kae ：Alice的公钥
Kbe： Bob的公钥
Kbd ：Bob的私钥

选p=7，q=17。
求n=p×q=119，φ(n)=(p-1)(q-1)=96。

取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。
确定满足d·e=1 mod 96且小于96的d，
因为77×5=385=4×96+1，所以d为77。
因此公开钥为{5，119}，秘密钥为{77，119}。
设明文m=19，则由加密过程得密文为
C=195 mod 119≡2476099 mod 119=66
解密为6677mod 119=19