信息安全数学基础复习

记些定理罢了

整除

1.对于任意整数x,y,必有(a,b)|ax+by
2.若a=bq+c，q是一个整数，则有(a,b)=(b,c)
3.欧几里得算法及拓展欧几里得算法的应用
4.对于任意两个整数a,b,存在整数x,y使得(a,b)=xa+yb

同余

1.如果ad与bd模m同余，且d与m互素，则a与b模m同余
2.若a，b模m同余，d是三者的公因数，则a\d,b\d模m\d同余
3.若a，b模m同余，则a，b模m的因数同余
4.完全剩余系与简化剩余系的概念
5.phi(m)为欧拉函数，为m的剩余类中与m互素的个数。如果m和n互素，则phi(mn)=phi(m)phi(n)
6.根据5所得的欧拉函数计算公式
7.欧拉公式：设m是正整数，r是m简化剩余系中的一个数。则r^phi(m)模m与1同余
8.若a是m简化剩余系的一个元素，则称满足a^t模m和1同余的最小整数t为a在模m下的阶，记为t=ord(a)。并且t|phi(m)
9.rsa的加密和解密
(一)基础
1.产生两个大的随机素数p和q
2.计算n=pq和phi(n)=(p-1)(q-1)
3.选择1-phi(n)之间的随机整数e，使得(e,phi(n))=1
4.计算e在模phi(n)下的逆元d
5.公钥即为(n,e),私钥即为d
(二)加密
1.原文为m
2.加密c=m^e模m
(三)解密
1.计算m=c^d模n

同余方程及其求解

1.一次同余方程ax=b(mod m)有解的充要条件是(a,m)|b,而且解数是(a,m)。解为x=x0b+km0;k=0,1,2……(a,m)-1
2.中国剩余定理，求解同余方程组。看书算了，懒得打字了。

群论

1.群需要满足三个条件。结合律，有单位元，有逆元。
2.G为一非空集合，G上乘法封闭且满足结合律。如果对于G中的任意元素a，b，方程ax=b和xa=b在G中有解，则G是群。
3.交换群也被称为阿贝尔群
4.一个定义了乘法的有限集合G，若乘法在G中封闭，且满足结合律和消去律，则G是群(利用结论2证明)
5.群G的非空集合H是子群的充要条件是任意中的元素a，b，有ab^-1是H的元素
6.G可以表示为若干个不相交的左陪集之并
7.拉格朗日定理|G|=|H|[G:H]
8.如果aH=Ha，则称H为正规子群(显然所有交换群的子群都是正规子群)
9.如果为正规子群，则a^-1Ha=H
10.H为G的正规子群，纪录G/H={aH/a是G的元素}，在此集合上定义运算(aH)*(bH)=(ab)H。这样构成了一个群。同时这个群也被称为商群。
11.Z/mZ被称为剩余类群
12.同构，核，相~巴拉巴拉。反正翻书也看不懂，无所谓吧
13.循环群的定义和生成元的定义。无限循环群只有a和a的相反数两个生成元
14.G=< a >是n阶循环群，a^k是G的生成元当且仅当(k,n)=1
15.a^k的阶为n(k,n)
16.循环群的子群是循环群，商群也是循环群

环和域

1.加法是阿贝尔群，乘法满足结合律和左右分配律的集合称为环。满足乘法交换律的环叫交换环。有单位元的环称为含幺交换环。无零因子的含幺交换环是一个整环。每个元素均有逆元的含幺环被称为除环。交换的除环被称为域。
2.如果环中不存在a，b，使得不为0的ab相乘等于0，则称这个环无零因子。
3.模素数的简化剩余类无零因子。
4.无零因子环中乘法的消去律成立，反之亦然。
5.无零因子环的非零元加法阶相等，为无穷大或者是素数。这个阶被称为环的特征。
6.一个至少有两个元素的无零因子的有限环是除环。
7.有限整环是域。
8.环同态、同构巴拉巴拉一大堆。
9.R是环，I是一个非空子集。如果满足
一，任给I中元素a，b，有a-b属于I
二.任给a属于I，r属于R，有ar和ra均属于I
则称这个子环为理想（理想一定是子环，反之不成立）