群、有限群和无限群 用Nn表示n个不同符号的集合,{1,2,,n}.n个不同符号的 个置换是一个Nn到N的一一映射。定义Sn为n个不同符号的所 有置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n 的一个置换,容易验证Sn是一个群: A1:如果π,p∈Sn,则合成映射π"p根据置换m来改变p中元素的次 序而形成,如,{3,2,1y{1,3,2}={2,3,1},显然Tp∈Sn A2:映射的合成显而易见满足结合律 °A3:恒等映射就是不改变n个元素位置的置换,对于Sn,单位元是 {1,2,,n} °A4:对于任意π∈Sn,抵消由π定义置换的映射就是π的逆元,这 个逆元总是存在,例如:{2,3,1}3,1,2}={1,2,3}, 有限群 Finite group和无限群 INfinite Group:如果一个群的 元素是有限的,则该群称为有限群,且群的阶等于群中元素的 个数;否则称为无限群 皿 都 mfy@ustc.edu.cn 现代密码学理论与实践 5/55mfy@ustc.edu.cn 现代密码学理论与实践 5/55  用Nn表示n个不同符号的集合，{1,2,…,n}. n个不同符号的一 个置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所 有置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n} 的一个置换，容易验证Sn是一个群： ◦ A1：如果π,ρ∈Sn，则合成映射π•ρ根据置换π来改变ρ中元素的次 序而形成，如，{3,2,1}•{1,3,2}={2,3,1},显然π•ρ ∈Sn ◦ A2：映射的合成显而易见满足结合律 ◦ A3：恒等映射就是不改变n个元素位置的置换，对于Sn，单位元是 {1,2,…,n} ◦ A4：对于任意π∈Sn ，抵消由π定义置换的映射就是π的逆元，这 个逆元总是存在，例如： {2,3,1}•{3,1,2}={1,2,3},  有限群Finite Group和无限群Infinite Group：如果一个群的 元素是有限的，则该群称为有限群，且群的阶等于群中元素的 个数；否则称为无限群