The Schreier-Sims Algorithm
Abstract. 本文将浅谈计算群论中的 Schreier-Sims 算法,该算法的核心思想是将群 $G$ 的信息表示为一列正规子群 $1 = G_1 \subset G_2 \subset \cdots \subset G_k = G$,通过 $G_i$ 在 $G_{i+1}$ 中的截面,回答一些重要的问题如某元素是否在群当中、某给定生成元的有限群的阶数是多少等。
本文的第二节介绍该算法使用的重要技术截面(Transversal)和 Schreier 引理,第三节介绍该算法的核心技术 BSGS,但是很遗憾我们暂时没能看懂如何求解一组 BSGS,只能给出一类大多数应用问题的简单快速的下替算法(参见第 3.3 节)。