下载文档原格式
摘要：置换群的性质分析与应用是近世代数这门课程里的很重要的一个知识点！利用置换群的相关性质可以使得一些繁琐复杂的问题变得简单容易，对解题有很大的帮助。
本文就其置换群的性质和应用进行一个描述！应用主要是谈论置换群在求解正多边形的对称变换群、正多面体的对称变换群，多项式的对称变换群中的应用！关键词：群; 置换; 置换群; 对称变换群Abstract：Permutation group is the nature of the analysis and application of modern algebra in this course is very important to a knowledge point! Use of the relevant permutation group can make the cumbersome nature of the complex problems become simple and easy, very helpful for problem-solving. This permutation group of its nature and application of a description! Application are mainly talking about regular polygon Permutation in solving the symmetry transformation group, regular polyhedron symmetry transformation group, the polynomial transformation group of symmetry!Key words：group; permutation; permutation group; symmetric transformation group目录1.前言 (1)2.主要内容 (1)2.1基本概念 (1)2.2置换群的性质 (2)2.2.1置换的性质 (2)2.2.2置换的分解 (2)2.2.3置换的奇偶性 (4)2.3置换在求解对称变换群中的应用 (5)2.3.1二维平面内求解正多边形的对称变换群 (6)2.3.2 在求解正多面体的对称变换群中的应用 (6)2.3.3 在求解多项式的对称变换群中的应用 (8)3. 结束语 (9)4. 参考文献 (9)5. 致谢 (9)置换群的性质分析及其应用1、前言置换群是群论中很重要的一类群，群论最早就是从研究置换群开始的，它还是一类重要的非交换群，每个有限的抽象群都与一个置换群同构，且现实生活中的许多对称现象总是以某种方式与置换及置换群有着密切的联系！所以研究置换群的性质及应用就显得格外的重要了！因此，我就置换群的一些性质进行了一个总结，并对置换群在对称变换群中的应用进行一个概括总结！2、主要内容2.1 基本概念：2.1.1 群：设G是一个非空集合，若在G上定义一个二元运算·满足S1：结合律：对任何cba,,∈G有()()cbacba⋅⋅=⋅⋅,则称G是一个半群，记作（G，·）。
快速幂取余
所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。
在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。
应用的公式：
d=a b mod n=(…((((a mod n)*a)mod n)*a)mod n…*a)mod n {共b个a}
(a × b) mod c=( (a mod c) × b) mod c.
1.有三根杆子A，B，C。
A杆上有3N个(N>1)穿孔圆盘，共有N个不同的大小，每个尺寸都有三个完全相同的圆盘，盘的尺寸由下到上依次变小。
要求按下列规则将所有圆盘移至C 杆：
1.每次只能移动一个圆盘；
2.大盘不能叠在小盘上面。
置换群2接着上⼀节，为了研究置换群的结构,我们来考虑对称群S n和交错群A n的的⽣成元系.定理1 对称群S n可以由(12),(13),⋯,(1n)⽣成，即S n=<(12),(13),⋯,(1n)>.证明⾸先<(12),⋯,(1n)>⊂S n,同时注意到每个置换都可以分解成⼀些对换的乘积,⽽对换(i j),(i≠j)可以被表⽰成(i j)=(1 i)(1 j)(1 i)这说明S n⊂<(12),⋯,(1n)>,从⽽S n=<(12),⋯,(1n)>.定理2 交错群A n可以由全体3−轮换⽣成.证明注意到任意的3−轮换(i j k)=(1 k)(1 j)(1 i),这说明3−轮换必然是偶置换,从⽽乘积也是.另⼀⽅⾯两个对换的乘积σ=(ij)(st)可被⼀些3−轮换表⽰即可.1)若i=s,j=t,那么σ=(1)=(123)(123)(123),结论成⽴;2）若i=s,j≠t,则σ=(i t j),结论也成⽴;3)若i≠j,s≠t,那么σ=(i j)(s t)=(1 i s)(1 i j)(1 s t)注意此处默认i,i,s,t均不为1.这说明偶置换可被表⽰成3−轮换的乘积.所以定理成⽴.即A n可由全体3−轮换⽣成.要注意的是群的⽣成元并不唯⼀,例如我们还有S n=<(12),(23),⋯,(n−1,n)>=<(12),(12⋯n)>以及A n=<(123),(124),⋯,(12n)>,n≥3另⼀个问题,S n中任意的置换σ=(a b⋯c)⋯(αβ⋯γ),我们考虑与之共轭的置换δ=τστ−1,注意到δ(τ(a))=τσ(a)=τ(b)同理δ(τ(b))=τ(c),不难看出δ=τστ−1=(τ(a) τ(b) ⋯τ(c))⋯(τ(α) τ(β) ⋯τ(γ))可以看出σ与δ具有相同的形式,这⾥的形式指的是分解成不相交的轮换的结果中,轮换的长度以及轮换的个数对应相等,某些书中也将这个称为置换的型：例如在S13中的置换(1234)(567)(89)(10,11),那么称他的型为1222314150⋯130,其原理就是置换分解成不相交轮换在不考虑次序情况下是唯⼀的.⼀般的在S n中如果某个置换的型为1r12r2⋯n r n,那么必然有n∑i=1ir i=n借助于型的概念,我们可以说S n中置换σ的共轭置换⼀定与之具有相同的型,那么反之是否成⽴呢？答案是肯定的,我们有定理S n中两个置换σ,δ共轭的充要条件是他们的型相同.证明必要性已然说明,再证充分性,设σ=(a b⋯c)⋯(αβ⋯γ),δ=(a′b′⋯c′)⋯(α′β′⋯γ′),那么取置换τ=a b⋯γa′b′⋯γ′可以验证δ=τστ−1,说明σ,δ是共轭的.按照置换的型可以很容易写出对称群S n中的全部共轭类,以S5为例,我们知道|S5|=5!=120,其全部的共轭类如下: 15型:仅有⼀个,即为(1);1321型:共\binom{5}{2}=10个;1^23^1型:共A_{5}^{3}/3=20个,即在5个元素中选取3个元素的圆排列(轮换对称性);1^14^1型:共A_{5}^{4}/4=30个;1^12^2型:共\binom{5}{1}\binom{4}{2}/2=15个;()2^13^1型:共\binom{5}{2}A_{3}^{3}/3=20个;5^1型:共A_{5}^{5}/5=24个.⼀般的我们有,在对称群S_n中,型为1^{r_1}2^{r_2}\cdots n^{r_n}的置换的个数为\frac{n!}{\prod\limits_{i=1}^{n}r_i!i^{r_i}}(在数字较⼤时⽤词结论计算是⽅便的,但是在数字较⼩时⽤前⾯排列组合的思路更快捷)⽤数学归纳法来证明是可⾏的,我们更希望给出如下的直接求法.记集合A:=表⽰n个元素1,2,\cdots,n的所有重排的集合,⽽集合B:=表⽰型为1^{r_1}2^{r_2}\cdots n^{r_n}的置换的全体.作映射\pi:A\to B,具体⽅式如下:对于重排a_1,a_2,\cdots,a_n,将前r_1个当做r_1个1-轮换,接下来的2r_2个每2个⼀组作为r_2个2-轮换,接下来的3r_3个每3个⼀组作为r_3个3-轮换……这样就构造出了型为1^{r_1}2^{r_2}\cdots n^{r_n}的置换,显然\pi是个满射但是并⾮单射.对于任意的\sigma\in B,那么\pi^{-1}(\sigma)便是n个元素的⼀个重排.我们把\sigma写成按照轮换长度递增的顺序的形式,显然这种表⽰并不唯⼀,因为每个r-轮换(a_1~a_2~\cdots~a_r)有r种不同的表⽰,并且每⼀种表⽰对应的在\pi下的原象均不同.另⼀⽅⾯不相交轮换是可换的,因此在保持长度递增情况下,r_i个i-轮换可以有r_{i}!种表⽰,结合起来可以看出\pi^{-1}(\sigma)共有\prod_{i=1}^{n}r_{i}!i^{r_i}种不同情况.⽽|A|=n!,因此|B|=\frac{n!} {\prod\limits_{i=1}^{n}r_i!i^{r_i}}利⽤置换的型,我们可以确定对称群的正规⼦群,例如我们考虑S_4的共轭类：1^5型:仅1个,即为(1)；1^22^1型:\binom{4}{2}=6个,分别是(12),(13),(14),(23),(24),(34)；1^13^1型:A_{4}^{3}/3=8个,分别是(123),(124),(132),(134),(142),(143),(213),(234)；2^2型:\binom{4}{2}/2=3个,分别是(12)(34),(13)(24),(14)(23)；4^1型:仅⼀个,即为(1234).设H是S_4的正规⼦群,根据Lagrange定理|H|只能是1,2,3,4,6,8,12,24,如果H是⾮平凡的,那么|H|只能是2,3,4,6,8,12,注意正规⼦群是⼀些共轭类组成的⼦群:1)显然|H|\neq 2,3,6,8,因为这些元素不可能是完整的若⼲共轭类;2)⽽|H|=4是可能的,此时H中的元素为:(1),(12)(34),(13)(24),显然此时H同构于Kelin四元群\mathbb K_4=\{1,a,b,ab\},其中a^2=b^2=(ab)^2=1;3)同样的|H|=12也是可以的,此时H由⼳元,8个1^13^1型置换以及3个2^2型置换构成,即为全体偶置换,此时H同构于A_4.以上分析说明S_4只有4个正规⼦群\{1\},K_4,A_4,S_4.类似的分析可以得到A_4的正规⼦群只有\{1\},K_4,A_4.更进⼀步的我们还有S_4/K_4\simeq S_3证明我们可以将S_3视作S_4的⼦群,将\sigma\in S_3看成\sigma(4)=4即可.由前⾯的结论K_4\triangleleft S_4,从⽽K_4S_3\leq S_4,注意到K_4\cap S_3=\{1\},那么|K_4S_3|=\frac{|S_3|\cdot|k_4|}{|K_4\cap S_3|}=24=|S_4|这说明S_4=K_4S_3,根据第⼀同构定理S_3/K_4\cap S_3\simeq S_4/K_4,即S_4/K_4\simeq S_3另⼀种证法是直接分析6阶群S_4/K_4的结构,事实上6阶群仅有2个,他们是\mathbb Z_6和S_3\simeq D_3.Loading [MathJax]/extensions/TeX/mathchoice.js。
上海电力学院Shanghai University of Electric Power实验报告院系名称：计算机科学与技术学院 __ 课程名称： _____ _ 应用密码学 _ _ __ 实验项目名称：置换群相关的运算及实现 ________实验一置换群相关的运算及实现一、实验目的理解密码学相关基本概念理解并能够编写基本的古典密码体制熟练应用C++编程实现密码体制二、实验内容1、求S3的所有元素并输出所有的置换。
2、水域S3的任意两个置换元素，求他们的复合运算的结果。
3、给定S3的某个置换，求它的逆置换。
三、实验原理1.置换群：n元对称群的任意一个子群，都叫做一个n元置换群2.矩阵的复合运算3.矩阵的求逆运算四、实验步骤（包括流程图、功能模块）1.申请18个空间，将3个元素依次循环填入填充。
2.通过置换，求得所有置换群3.矩阵的复合运算4.矩阵的求逆运算【算法流程图】五、软件使用说明（开发环境、参数使用详细说明、实验结果+相应截图等）【功能模块】求取置换群for (int i = 0; i<3; i++){swap(Abelian[i * 6], Abelian[i * 6 + i]);swap(Abelian[i * 6 + 3], Abelian[i * 6 + 3 + i]);swap(Abelian[i * 6 + 4], Abelian[i * 6 + 4 + 1]);}矩阵的复合for (int i = 0; i<3; i++){for (int j = 0; j<3; j++)if (Abelian[3 * (m - 1) + i] == Abelian_Group_src[j])Compound_Operate[i] = Abelian[3 * (n - 1) + j];}逆矩阵for (int i = 0; i<3; i++){for (int j = 0; j<3; j++)if (Abelian[3 * (n - 1) + i] == Abelian_Group_src[j])inverse_operation[j] = Abelian_Group_src[i];}【开发环境】Visual Studio 2013 （Windows10）【参数使用】输入的三个元素：4、5、6选择做复合运算的两个置换：4、5求逆的矩阵编号：4【实验结果】六、参考资料（书籍或网络文章）《密码编码学与网络安全——原理与实践（第五版）》七、实验心得和总结八、源代码#include<iostream>#include<string.h>using namespace std;int main(){//1int *Abelian_Group_src = new int[3];cout << "请依次输入元素值：";for (int i = 0; i<3; i++)cin >> Abelian_Group_src[i];int Abelian[18];for (int i = 0; i<18; i = i + 3)//因为每个置换群的第一行都相同，所以只需要对剩下的一行操作即可。
快速幂取模算法详解转载⾃：https:///dbc_121/article/details/77646508快速幂取模的⽤途：在ACM这类竞赛中，可能会遇到指数型的数据取模问题，这个时候如果直接⽤int或者long long储存，就有可能会超出计算机整数的存取范围，⽽导致数据出错。
所以我们需要⼀种⽅法进⾏计算。
⽽这种⽅法就是我们这次要讲到的快速幂取模（简称快速幂）。
这种算法在时间和空间上都做了尽可能的优化，所以学会之后，会觉得⾮常好⽤。
快速幂取模的思路：快速幂实现的最基本的理论就是我们离散课上或者数论中学过的⼀条公式推出的引理。
引理：积的取余等于取余的积的取余。
再在这条引理的基础之上，对指数型数据进⾏拆分以及合并，从⽽得到我们⽤的快速幂算法。
本⽂我就不⽤例题讲解，直接对快速幂进⾏解析。
毕竟快速幂的算法相对简单，⽽且适⽤题型较为⼀致。
快速幂具体分析：对a^b进⾏分析。
对于当a和b较⼩是直接⽤int或者long存是没有问题的，但是当a和b⼤到⼀定程度时，这就不是暴⼒存就可以解决的问题了。
我们应该怎么去解决这个问题呢？在这⾥我们需要把注意⼒放在“⼤”字上⾯，正是由于a和b过⼤才导致的问题。
所以我们要想办法不断地减⼩a和b的规模，所谓逐个击破。
根据上⾯的那条引理，我们知道了可以把指数拆开，从这个突破⼝突破。
这⾥我们就不难想到这样⼀个算法：//①a是底数，b是指数，mode是取模数，sum是记录取模的结果int sum = 1;a = a % mode;for(int i = 1; i <= b; i++){sum = sum * a;}sum = sum % c;这是直接利⽤的引理⽽写出来的代码，这只是单纯的降低的a的规模，但是这还达不到我们的要求，所以我们需要进⼀步改进算法。
（当然还可以继续降低啊的规模，即将循环中的那句换成sum = （sum * a）%mode）我们已经实现的降低a的规模，所谓我们要想着怎么降低b的规模。
