2、(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算模运算模运算的性质[(amodn)+(bmodn)]modn=(a+b)modn[(am
3、odn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn模运算例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×01234567000000000101234567202460246303614725404040404505274163606420642707654321模运算若x+y=0modn,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1mo
4、dn，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn={0,1,..,n-1}为模n的同余类集合。模运算Zn上模运算的性质交换律（x+w)modn=(w+x)modn(x×w)modn=(w×x)modn结合律[(x+w)+y]modn=[x+(w+y)]modn[(x×w)×y]modn=[x×(w×y)]modn分配律[w×(x+y)]modn=[w×x+w×y)]modn模运算单位元(0+w)modn=wmodn(1×w)modn=wmodn加法逆元：对w∈Zn,有z∈Zn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)≡(a+c)mo
5、dn,则b≡cmodn对乘法不一定成立，因为乘法逆元不一定存在。模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn中国剩余定理如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数定理(中国剩余定理)：设m1,m2,…,mk是两两互素的正整数，则一次同余方程组对模M有唯一解中国剩余定理中国剩余定理可以将一个很大的数x表示为一组较
6、小的数(a1,…ak)例：x≡1mod2,x≡2mod3,x≡3mod5x≡5mod7,求x解：M＝2×3×5×7＝210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以求得e1=1,e2=1,e3=3,e4=4,所以x=105×1×1＋70×1×2＋42×3×3＋30×4×5mod210＝173费尔玛定理和欧拉定理费尔玛定理若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp证明：gcd(a,p)=1,则a×Zp=Zp,a×(Zp-{0})=Zp-{0}{amodp,2amodp,…,(n-1)amodp}={0,1,…,p-1}(amodp
7、)×(2amodp)×…×(n-1)amodp=(p-1)!modp(p-1)!×ap-1=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp费尔玛定理和欧拉定理欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)定理：若n是两个素数p和q的乘积，则φ(n)＝φ(p)φ(q)=(p-1)(q-1)欧拉定理若a和n互素,则aφ(n)=1modn离散对数求模下的整数幂根据欧拉定理，若gcd(a,n)=1,则af(n)≡1modn。考虑一般am≡1modn,如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模
8、n下a的阶。例：a=7,n=19.71≡7mod19,72≡11mod19,73≡1mod19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同RSA算法的实现实现的步骤如下：Bob为实现者(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq和φ(n)=(p-1)(q-1)(3)Bob选择一个随机数e(0
