$子群可以构造一种集合叫陪集$
$陪集又可以引出一个很重要的定理\mbox{:}拉格朗日定理,它研究的是有限群的元素个数问题.$
$陪集又引出了一种特殊的子群,正规子群.$
$正规子群又可以构造一种叫商群的群$
$商群的元素个数又和拉格朗日定理有关.$
$陪集$
$定义\mbox{:}H是群G的子群,a\in G,则aH\mbox{:}=\{a\cdot h | h \in H\}$
$称为H关于a在群G的左陪集(left\ cost)$
$同理,$
$Ha:=\{h\cdot a | h\in H\}$
$称为H关于a在G中的右陪集(right\ cost)$
$用任意元素a和子群H中每个元素进行运算,运算结果就构成一个集合$
$这种集合就叫陪集$
$不过,陪集也有左右之分$
$这都是运算不一定满足交换律导致的$
$a在H左边集合叫H关于a在G中的左陪集,a在H右边,就叫H关于a在G中的右陪集$
$如果左陪集aH=右陪集Ha,叫H关于a在G中的陪集,简称陪集,a叫代表元(representative).$
$为了加以区别,元素a在H中构造的陪集,就用[a]_{H}表示$
$陪集的定义告诉我们,它的研究目的是以H为基准,去观察群里每个元素与H的关系.$
$为了表述清楚,我们取\mathbb{Z}中的每个整数,依次和3\mathbb{Z}里的每个整数运算.$
$因为是加法群,构造的陪集就写成这样$
$[0]_{3\mathbb{Z}}=\{0,0\pm 3,0\pm 6\cdots\}$
$[1]_{3\mathbb{Z}}=\{1,1\pm 3,1\pm 6\cdots\}$
$[2]_{3\mathbb{Z}}=\{2,2\pm 3,2\pm 6\cdots\}$
$可以看到,每个整数只会存在于某个唯一的陪集中.所以这种陪集其实是对整数群进行的划分.$
$每个整数都根据它和子群的关系来确定它会进入哪个陪集.$
$每个陪集的构造依据就是整数与3的倍数的距离.$
$[0]_{3\mathbb{Z}}这个陪集,它的元素与3的倍数的距离都是0$
$[0]_{3\mathbb{Z}}这个陪集其实就是3\mathbb{Z}本身,这正与距离是0相吻合.$
$[1]_{3\mathbb{Z}}这个陪集,它的元素与3的倍数的距离都是1$
$[2]_{3\mathbb{Z}}这个陪集,它的元素与3的倍数的距离都是2$
$陪集就是划分后,最终形成的那些集合.$
$性质1\mbox{:}a\in [a]_{H}$
$因为单位元在子群里,H=\{e,\cdots\}$
$a与子群里的元素运算时$
$必然会遇到单位元$
$运算结果就是a本身.$
$[a]_{H}=\{a\cdot e\cdots\}$
$=\{a,\cdots\}$
$这就导致了a进入了陪集.$
$[e]_{H}=H$
$其实子群本身也是一个陪集,它就相当于用单位元和子群构造出来的陪集.$
$因为单位元和子群中的任意元素运算都等于那些元素本身.$
$H=\{\cdots,h,\cdots\}$
$[e]_{H}=\{\cdots,e\cdot h,\cdots\}$
$=\{\cdots,h,\cdots\}$
$=H$
$我们管这些子群和本身叫平凡陪集.$
$而其他的就叫非平凡陪集$
$所以用子群H构造的陪集里,必然包含H本身.$

$模运算符写作mod,在a mod b这个式子里,要注意,a可以是任意整数$
$但b是正整数$
$a mod b的结果就是a除以b的余数$
$a相当于被除数,b相当于除数,q是商,r是余数$
$模运算符其实在C语言里也有,就是百分号$
$比如计算5除以3的余数C语言里就可以写成5%3$
$日常生活中有很多应用模运算的例子$
$钟表就是最典型的例子,问你17点是下午几点?$
$你会一口答上来是下午5点$
$那如果问你35点是几点呢?用模运算就很容易回答$
$我们先看17点是怎么对应到下午5点的,钟面上有12个刻度$
$所以就用17去模12$
$商是1,余数是5$
$设a和b都是整数,如果整数d分别是a和b的因子$
$则称d是a和b的公因子$
$如果d是非负整数$
$而且d是a和b的公因子中最大的,那么d就叫做a和b的最大公约数$
$a和b的最大公约数记作gcd(a,b)$
$根据以上定义知道,a和b的所有公因子必然都是最大公约数的因子$
$也就是说,它俩的公因子都整除它俩的最大公约数$
$12和18的公因子有\pm 1,\pm 2,\pm 3,\pm 6.$
$它们都整除最大公约数6,注意,因子也可以是负的$
$公因子可以是任意整数(既可以是0,也可以是负的)$
$但最大公约数只能是0或正的,不能是负的$
$再强调一遍,最大公约数不能是负的$
$比如求-3,6的最大公约数,我们可以把负号忽略掉,直接求3和6的最大公约数,答案是3,再比如求-15和-20的最大公约数,就相当于求15和20的最大公约数$
$特别的,0和0的最大公约数是0$
$如果a和b的最大公约数是1,那么称a和b互素,记作gcd(a,b)=1,a和b是否互素和它们是否素数无关.$
$设a,b\in \mathbb{Z},如果gcd(a,b)=1,则称a和b互素.$
$提个问题,对于两个互素的整数a和b,a和b的公因子有哪些?$
$因为a,b的公因子都是最大公约数的因子,既然它俩互素,那么其他因子必然都是1的因子$
$所以a和b的公因子就只有\pm 1$
$gcd(a,b)\leftrightarrow a和b的因子只有\pm 1$
$因为最大公因子不是负的,所以再求其他的公因子时,很容易把负的漏掉$
$当然,根据互素的定义,如果a和b的公因子只有正负一,它俩一定互素$
$如果a和b的最大公约数是d,那么必然存在2个整数q_{1}和q_{2}$
$使得a=q_{1}d,b=q_{2}d,且gcd(q_{2},q_{2})=1$
$这个很容易验证$
$因为如果q_{1}和q_{2}还有大于1的公因子,设为t吧.$
$那么a和b就会有更大的公约数,即td,这就与d是最大公约数相矛盾$
$举个例子,15和20的最大公约数是5,那么q_{1}=3,q_{2}=4而$
$3和4就是互素的.$

$Hill密码体制$
$假设甲方要将信息"HELP"(明文)发送给乙方,则发送者事先与接受者约定某个二维函数\mu$
$假如设$
$y_{1}=3x_{1}+3x_{2}$
$y_{2}=2x_{1}+5x_{2}$
$然后将HELP分为两组(H,E)和(L,P)$
$按上面的编码方法得\mbox{:}$
$H\cdots 7\cdots x_{1}$
$E\cdots 4\cdots x_{2}$
$L\cdots 11\cdots x_{1}$
$P\cdots 15\cdots x_{2}$
$用前面的函数\mu 作用后,得$
$y_{1}=3x_{1}+3x_{2}=3\times 7+3\times 4=33\equiv 7(mod\ 26)\cdots 7\cdots H$
$y_{2}=2x_{2}+5x_{2}=2\times 7+5\times 4=34\equiv 8(mod\ 26)\cdots 8\cdots I$
$y_{1}=3x_{1}+3x_{2}=3\times 11+3\times 15=78\equiv 0(mod\ 26)\cdots 0\cdots A$
$y_{2}=2x_{1}+5x_{2}=2\times 11+5\times 15=97\equiv 19(mod\ 26)\cdots 19\cdots T$

$完善保密性,具有无限计算资源也无法获得关于明文的任何信息(无条件安全性)$
$香农定理:密钥不能短于明文$
$香农的研究告诉我们,完善保密性和香农定理就像是一个硬币的两面$
$加密方案达到完善保密性,即使攻击者具有无限计算资源,也无法从密文中获取到有关明文的任何信息$
$这被称作无条件安全性,但是香农定理是依附在完善保密性上的魔咒,为了达到完善保密性,需要的密钥就不能短于明文$

$因此,我们得到结论,要达到完善保密性,加密方案就必须收到香农定理的制约,导致非常不实用$
$一次一密就遇到了这样的问题,搞得难以使用$
$然而,一次一密的优点也非常明显$
$加解密只需要异或操作,软硬件实现都非常非常非常简单,运行起来嗖嗖的$

$群同态在两个群之间建立了联系,它的研究意义在于,可以利用一个群的知识去分析另一个群$
$设群(G,*)和群(G^{'},\cdot),如果函数f:G\to G^{'}对于\forall a,b\in G,都有$
$f(a*b)=f(a)\cdot f(b)$
$那么则称f为从(G,*)到(G^{'},\cdot)的群同态$
$为啥单位元的像也是单位元呢?$
$e映射进G^{'},对应的元素是f(e)$
$让它和G^{'}的单位元e^{'}运算f(e)\cdot e^{'}=f(e),就得到f(e)本身$
$而e=e\times e,所以f(e)=f(e\times e),根据群同态的运算公式,得到f(e)和f(e)运算,f(e)\cdot f(e)$
$两边同时消去f(e)，就证明完了$

$为什么互为逆元的元素的像仍互为逆元呢?$
$G中任意元素a,它映射后就是f(a)$
$所以这个其实就是要证明,a的逆元映射后等于f(a)的逆元,就可以了$
$这个其实就是要证明,f(a^{-1})和f(a)^{-1}互为逆元,也就是说,他俩运算后等于单位元e^{'}$
$根据群同态的公式,就等于这个f(a^{1})\cdot f(a)=f(a^{-1}\times a)$
$它等于f(e)等于e^{'}$
$就证明完了$

$这个性质,你也可以这样理解,$
$f是群同态的话,-1次方,这个可以拿到f外面来$
$接着看$
$H是G的子群,它的所有元素的像就记为f(H),这个像的集合f(H)$
$在G^{'}中也构成子群,或者说子群的像仍是子群$
$这个就用证明子群的老套路$
$只要证明f(H)中任意两个元素f(a)和f(b)满足$
$f(a)运算f(b)的逆元仍是属于f(H)的就可以了$