群同构测试：从 Abel 群标准形到循环扩张的作用矩阵¶

两个群可以使用完全不同的元素标签、不同的生成元、不同的乘法表写法，却具有完全相同的乘法结构——就像同一篇文章的两种不同语言的译本。群同构问题（group isomorphism problem）要求判断两个给定的群之间是否存在同构，即双射 $\varphi:G\to H$ 满足

\[ \varphi(xy)=\varphi(x)\varphi(y)\qquad(\forall x,y\in G). \]

这个问题是著名的图同构问题的"近亲"，其精确复杂度至今悬而未决：对一般黑盒群，既无已知的多对数时间经典算法，也尚无统一的多对数时间量子算法。但是，一旦对群的结构加以限制，局面就完全不同。本文讲清两个正结果的来龙去脉：

Abel 群（Cheung–Mosca，Zoo 127）：有限 Abel 群可以由不变因子序列完全分类，而分解可以归结为 Abel 隐藏子群问题，因此量子算法在 $\operatorname{poly}(\log|G|)$ 时间内不仅能判定同构，还能把同构映射显式构造出来；
Abel 正规子群被循环群扩张的一类非交换群（Le Gall，Zoo 128）：同构测试被进一步化为"作用矩阵的幂后共轭"问题，再化为可由 Abel HSP 求解的多重集合离散对数。

阅读本文需要 Abel 隐藏子群问题（见Abel 隐藏子群问题）和 Shor 阶查找（见 Shor 算法）作为前提；本文不再重新推导它们，只引用结论。

本课知识点

同构与结构不变量——能写出群同构的定义并验证 $\varphi(a)=i^{\,a}$ 这类具体映射是同构，举出群阶相同却不同构的例子，并解释为什么算法必须计算规范结构而不是比较统计量。
黑盒群模型与经典瓶颈——能列出黑盒群模型的输入与接口，说明输入长度只有 $O(\log|G|)$，并解释枚举全部群元素的算法为何对输入长度是指数时间。
关系子群与 Abel HSP 分解——能由生成元构造同态 $\Phi$ 与关系子群 $K=\ker\Phi$，验证 $\Phi$ 满足 Abel HSP 的两个条件，并由同构定理得出 $G\cong D/K$。
Smith 标准形与不变因子判定——能用幺模行列变换把关系矩阵化为 Smith 标准形，写出"不变因子序列相同当且仅当同构"的判定准则，并手算小例子核对。
Abel-by-cyclic 群与作用矩阵——能写出半直积 $G\cong A\rtimes_\alpha\mathbb Z_m$ 的乘法公式，解释非交换性为何全部来自共轭作用 $\alpha$，并把 $\alpha$ 表示为各 Sylow 分量上的矩阵。
幂后共轭判据——能推导 $PM_\alpha P^{-1}=M_\beta^{\,k}$（$k\in\mathbb Z_m^*$），并指出推导中"$B$ 可交换"与"$k$ 为单位"两个不可省略的依据。
多重集合离散对数——能把"幂后相似"化为特征值多重集合的离散对数问题，并解释朴素配对做法的两个指数障碍及 Le Gall 如何用 Abel HSP 消除它们。
最小例子与适用边界——能在 $\mathbb Z_3\rtimes\mathbb Z_2$ 的最小例子上运用判据区分 $\mathbb Z_6$ 与 $S_3$，并列出结果依赖的结构承诺与模型承诺。

1. 问题从哪里来：标签与结构¶

1.1 同构是"换一套标签"¶

先建立一个具体直觉。考虑两个群：一个是模 $4$ 加法群

\[ \mathbb Z_4=\{0,1,2,3\},\qquad x*y=(x+y)\bmod 4, \]

另一个是复数乘法群 $\{1,i,-1,-i\}$。它们的元素名字、运算符号完全不同，但映射

\[ \varphi:\mathbb Z_4\to\{1,i,-1,-i\},\qquad \varphi(a)=i^{\,a} \]

满足 $\varphi(a*b)=i^{a+b\bmod 4}=i^a i^b=\varphi(a)\varphi(b)$（这里用了 $i^4=1$，所以指数可以模 $4$ 计算）。因此两个群同构：群的本质是乘法表的结构，而不是元素的名字。

同构测试的困难恰恰在于：算法拿到的只有"名字"（标签），而需要回答"结构"问题。两个群可能标签体系毫无相似之处，结构却相同；也可能许多容易计算的统计量全部吻合，结构却不同。

1.2 为什么群阶远远不够¶

同构必保持一切"结构不变量"：群阶、每个元素的阶、中心、交换性等等。反过来，比较不变量是否足够？不够——这些不变量通常不完备。例如

\[ \mathbb Z_6 \quad\text{与}\quad S_3 \]

都有 $6$ 个元素，但一个是 Abel 群、一个不是（$S_3$ 中两个对换不交换），因此不同构。这个例子里"交换性"一个不变量就足够区分；但加上更多统计量之后，仍然存在所有常见不变量都吻合却不同构的群对。结论：算法必须产生规范结构（canonical form），或者直接构造出同构映射，而不是只比较若干容易计算的统计量。这是全文的指导思想。

1.3 黑盒群模型与经典瓶颈¶

本文采用黑盒群（black-box group）模型，这是讨论群算法查询复杂度的标准设定：

群 $G$ 的每个元素被编码为一个唯一的长度 $n=O(\log|G|)$ 的比特串（unique encoding：一个元素只有一个合法标签）；
算法只能通过群运算预言机做乘法、求逆、判断相等；
输入还包括一小组生成元 $g_1,\ldots,g_k$。

注意输入长度只有 $O(\log|G|)$：几个生成元加上预言机接口。因此，任何需要枚举全部 $|G|$ 个元素的算法，对输入长度而言都是指数时间的。经典算法面对的正是这个瓶颈：如果群以完整乘法表给出（输入长度约 $|G|^2\log|G|$），经典算法可以穷举生成元的像，在约 $|G|^{\log|G|+O(1)}$ 时间内判定同构；对图同构，已有拟多项式时间的经典算法。但在黑盒模型下输入只有 $O(\log|G|)$ 长，这些"指数级枚举"办法全部失效，经典算法对一般黑盒群是指数时间的。量子算法的机会在于：Shor 式的周期/隐藏子群机制恰好能在 $\operatorname{poly}(\log|G|)$ 时间内提取群的"关系结构"，这正是同构测试所需要的信息。

1.4 历史脉络¶

Zoo 127（Cheung–Mosca, 2001）：给出分解有限 Abel 黑盒群的量子算法——求出一组生成元及完整关系，把 Abel 群写成循环群直积。Abel 群同构测试是它的直接推论。
Zoo 128（Le Gall, 2010）：把同构测试推进到一类非交换群——含 Abel 正规子群 $A$、且商群为与 $|A|$ 互素的循环群的群（"Abel-by-cyclic"）。算法把问题化为有限域上矩阵的"幂后共轭"与多重集合离散对数，仍由 Abel HSP 求解。
Zoo 202（Zatloukal, 2013）：研究更一般的群扩张等价测试，用 Abel HSP 加速作用相容性与上同调类的检查。

需要在一开始就强调：这些结果都没有解决一般群同构问题，也没有直接解决图同构问题。它们依赖明确的结构承诺（Abel、Abel-by-cyclic、互素阶、唯一编码），本文第 7 节会回到这个边界。

2. 工具箱回顾¶

本文反复使用四件工具，这里只陈述结论并注明出处，不重新推导。

阶查找（order finding）。给定黑盒群中元素 $g$，求最小正整数 $r$ 使 $g^r=e$。量子算法（Shor 阶查找，即相位估计作用于模乘酉算子的群论版本）在 $\operatorname{poly}(\log|G|)$ 时间完成。

Abel 隐藏子群问题（Abelian HSP）。设 $D$ 为已知结构的有限 Abel 群，函数 $f:D\to S$ 满足：存在子群 $K\le D$，使得 $f$ 在 $K$ 的每个陪集上取常值、在不同陪集上取不同值。这样的 $f$ 称为隐藏（hide）子群 $K$。量子算法（Simon/Shor 框架对一般 Abel 群的推广）用 $\operatorname{poly}(\log|D|)$ 次查询求出 $K$ 的一组生成元。详见Abel 隐藏子群问题。

构造性成员测试（constructive membership）。给定生成元 $g_1,\ldots,g_k$ 和元素 $h\in G$（$G$ Abel），求指数向量 $a$ 使 $h=\prod_i g_i^{a_i}$。做法是对函数 $(a,t)\mapsto \Phi(a)\cdot h^{-t}$（其中 $\Phi$ 见下节）做 Abel HSP：隐藏子群由关系与 $h$ 的表示共同生成，求出后即读出 $a$。复杂度同为 $\operatorname{poly}(\log|G|)$。

Smith 标准形（Smith normal form）。对任意整数矩阵 $R$，存在行列式为 $\pm1$ 的整数方阵（幺模矩阵）$U,V$，使

\[ URV=\operatorname{diag}(d_1,d_2,\ldots,d_t,0,\ldots,0), \qquad d_1\mid d_2\mid\cdots\mid d_t,\quad d_i\ge1. \]

对角元 $d_i$（不变因子）由 $R$ 唯一确定；$U,V$ 与对角化过程可以在多项式时间内算出（经典算法，只需要整数行列运算）。

3. Abel 群：关系子群与 Smith 标准形¶

本节把 Cheung–Mosca 分解完整走一遍。核心思想一句话：Abel 群与"循环群直积"之间的差别，全部藏在生成元满足的关系里；而关系构成一个格子（$\mathbb Z^k$ 的子群），量子算法擅长的正是找格子。

3.1 从生成元到关系子群¶

设 Abel 黑盒群 $G$ 的生成元为 $g_1,\ldots,g_k$。第一步，用量子阶查找求出每个生成元的阶

\[ r_i=|g_i|,\qquad i=1,\ldots,k, \]

即最小正整数使 $g_i^{r_i}=e$。第二步，定义"自由"直积群到 $G$ 的映射

\[ \Phi: D=\mathbb Z_{r_1}\times\cdots\times\mathbb Z_{r_k} \longrightarrow G, \qquad a=(a_1,\ldots,a_k)\mapsto\prod_{i=1}^k g_i^{a_i}. \]

先验证 $\Phi$ 是群同态。这一步必须用到 $G$ 是 Abel 群：

\[ \Phi(a+b)=\prod_i g_i^{a_i+b_i} =\prod_i g_i^{a_i}\,g_i^{b_i} =\left(\prod_i g_i^{a_i}\right)\left(\prod_i g_i^{b_i}\right) =\Phi(a)\Phi(b), \]

其中第三个等号把 $g_i^{b_i}$ 逐个移到对应位置，只有两两可交换时才合法。由于 $g_1,\ldots,g_k$ 生成 $G$，每个群元素都能写成 $\prod_i g_i^{a_i}$，即 $\Phi$ 是满射。

定义关系子群

\[ K=\ker\Phi=\{a\in D:\ g_1^{a_1}\cdots g_k^{a_k}=e\}. \]

$K$ 正是"生成元之间全部乘法关系"的集合：每个 $a\in K$ 是一条关系 $g_1^{a_1}\cdots g_k^{a_k}=e$。例如若 $g_1g_2=g_2g_1$ 之外的唯一关系是 $g_1^2=g_2^3$，那么 $(2,-3)\in K$。

3.2 用 Abel HSP 求关系子群¶

把 $\Phi$ 看成函数 $f:D\to G$（输出用元素的标签表示）。它满足 Abel HSP 的全部条件：

$f$ 在 $K$ 的每个陪集上取常值：若 $b=a+k$、$k\in K$，则 $$ f(b)=\Phi(a+k)=\Phi(a)\Phi(k)=\Phi(a)\cdot e=f(a), $$ 用了同态性质与 $k\in\ker\Phi$；
$f$ 在不同陪集上取不同值：若 $f(a)=f(b)$，则 $\Phi(a-b)=\Phi(a)\Phi(b)^{-1}=e$，即 $a-b\in K$，二者属于同一陪集。

（这正是群同态基本定理证明里"纤维即陪集"的那一步。）因此运行 Abel HSP 算法，用 $\operatorname{poly}(\log|D|)$ 次查询得到 $K$ 的一组生成元 $k^{(1)},\ldots,k^{(s)}\in D$——每个生成元是一个 $k$ 维整数向量（分量按模 $r_i$ 理解）。

再由群同态基本定理（第一同构定理）：满同态 $\Phi:D\to G$ 诱导同构

\[ G\cong D/K. \]

到此，$G$ 的结构完全被"数据化"：$D$ 是已知的循环直积，$K$ 是已知生成元的子群。

3.3 Smith 标准形：从关系到不变因子¶

$D/K$ 仍不是一个"规范"的答案——同一个群可以由不同的 $D,K$ 给出。规范化的工具是 Smith 标准形。

把 $K$ 的生成元写成行向量，添上各分量的模 $r_i$ 关系，排成一个整数矩阵 $R$（关系矩阵，relation matrix）：每一行是 $\mathbb Z^k$ 中一个把生成元组合映到 $e$ 的关系。于是

\[ G\cong \mathbb Z^k/\langle R\text{ 的行}\rangle. \]

对这个商群做 Smith 标准形的代数含义是：

行变换（左乘幺模阵 $U$）= 更换关系集合的基，不改变它们生成的子群；
列变换（右乘幺模阵 $V$）= 更换 $\mathbb Z^k$ 的基，也就是把 $g_1,\ldots,g_k$ 换成一组新生成元 $h_j=\prod_i g_i^{V_{ij}}$（整数可逆组合仍生成同一个群）。

由于行列变换不改变商群的同构型，Smith 标准形给出

\[ G\cong \mathbb Z_{d_1}\times\cdots\times\mathbb Z_{d_t}, \qquad d_1\mid d_2\mid\cdots\mid d_t, \]

其中删去了 $d_i=1$ 的平凡因子。不变因子序列 $(d_1,\ldots,d_t)$ 由 $G$ 唯一确定（Smith 标准形的唯一性），因此：

判定准则：两个有限 Abel 群同构，当且仅当它们的不变因子序列 $(d_1,\ldots,d_t)$ 完全相同。

这就是第 1.2 节所说的"规范结构"：同构测试被归结为计算并比较一个整数序列。而且 Smith 变换的矩阵 $V$ 记录了新基与旧生成元之间的坐标，所以算法不只是回答 yes/no——把两边的规范基对齐，就能构造出显式同构映射（constructive membership 负责把任意元素换算到规范基坐标）。

3.4 小例子：手算一次 Smith 标准形¶

设 Abel 群 $G$ 由 $g_1,g_2$ 生成，阶查找给出 $r_1=r_2=6$，即 $D=\mathbb Z_6\times\mathbb Z_6$。运行 Abel HSP 后，设返回的关系子群 $K$ 由

\[ k^{(1)}=(2,2),\qquad k^{(2)}=(0,3) \]

生成（即关系 $g_1^2g_2^2=e$ 与 $g_2^3=e$）。关系矩阵为

\[\begin{split} R=\begin{pmatrix}2&2\\0&3\end{pmatrix}. \end{split}\]

下面只做整数幺模行列运算，把 $R$ 对角化。每一步都标注依据：

第一步，第 2 列减去第 1 列（列变换，合法）：

\[\begin{split} \begin{pmatrix}2&0\\0&3\end{pmatrix}. \end{split}\]

第二步，把第 2 列加到第 1 列，再把第 1 行从第 2 行中减去，目的是用 $\gcd(2,3)=1$ 造出角上的 $1$：

\[\begin{split} \begin{pmatrix}2&0\\0&3\end{pmatrix} \xrightarrow{C_1\leftarrow C_1+C_2} \begin{pmatrix}2&0\\3&3\end{pmatrix} \xrightarrow{R_2\leftarrow R_2-R_1} \begin{pmatrix}2&0\\1&3\end{pmatrix}. \end{split}\]

第三步，交换两行把 $1$ 换到左上角，再消去同行的 $3$ 与同列的 $2$：

\[\begin{split} \begin{pmatrix}2&0\\1&3\end{pmatrix} \xrightarrow{R_1\leftrightarrow R_2} \begin{pmatrix}1&3\\2&0\end{pmatrix} \xrightarrow{C_2\leftarrow C_2-3C_1} \begin{pmatrix}1&0\\2&-6\end{pmatrix} \xrightarrow{R_2\leftarrow R_2-2R_1} \begin{pmatrix}1&0\\0&-6\end{pmatrix}. \end{split}\]

最后把第二行乘以 $-1$（幺模），得到 Smith 标准形

\[ \operatorname{diag}(1,6). \]

验证：对角元整除关系 $1\mid6$ 成立；行列式绝对值 $=6=|K|$ 在变换下不变（幺模变换行列式为 $\pm1$）。因此

\[ G\cong\mathbb Z_1\times\mathbb Z_6=\mathbb Z_6. \]

虽然 $G$ 由两个 $6$ 阶元素生成、表面上"像" $\mathbb Z_6\times\mathbb Z_6$，关系 $g_1^2g_2^2=e$、$g_2^3=e$ 实际上把它"压缩"成了一个 $6$ 阶循环群。不变因子序列 $(6)$ 就是这个群在同构意义下的"指纹"。

3.5 复杂度逐项分析¶

整条流水线关于输入长度 $\log|G|$ 是多项式的，逐项看每个因子：

阶查找：对 $k$ 个生成元各做一次 Shor 阶查找。生成元个数 $k\le\log_2|G|$（每个生成元至少使群阶翻倍，严格说是群有一个长度 $\le\log_2|G|$ 的生成元链），单次代价 $\operatorname{poly}(\log|G|)$，合计 $\operatorname{poly}(\log|G|)$。
Abel HSP：作用在 $D=\prod_i\mathbb Z_{r_i}$ 上，$\log|D|=\sum_i\log r_i=O(k\log|G|)$，故查询与后处理都是 $\operatorname{poly}(\log|G|)$。
Smith 标准形：经典多项式时间算法，矩阵规模 $O(k)$、表值 $O(\log|G|)$ 比特，代价 $\operatorname{poly}(k,\log|G|)$。
构造性成员测试（组装同构时用到）：每次 $\operatorname{poly}(\log|G|)$。

每一项都是 $\operatorname{poly}(\log|G|)$，复合仍是 $\operatorname{poly}(\log|G|)$。这就是"Abel 群同构测试有多对数时间量子算法"的完整含义——注意它不是单一的量子加速点，而是阶查找与 HSP 两个量子子程序嵌在多项式时间的经典框架里。

4. 循环扩张类 $\mathscr S$¶

Abel 群的情形解决后，自然的下一步是"离 Abel 群最近"的非交换群。Le Gall（Zoo 128）考虑满足

\[ G=\langle A,y\rangle \]

的一类群，其中

\[ A\trianglelefteq G,\qquad A\ \text{Abelian},\qquad |y|=m,\qquad\gcd(|A|,m)=1. \]

也就是说：$G$ 由一个 Abel 正规子群 $A$ 和一个循环补 $\langle y\rangle\cong\mathbb Z_m$ 生成，并且两部分阶互素。这类群称为 Abel-by-cyclic 群。

4.1 直觉：非交换性只有一个来源¶

先看这个结构"长什么样"。由于 $A\trianglelefteq G$ 且 $G/A=\langle yA\rangle\cong\mathbb Z_m$，每个元素都能唯一写成

\[ g=a\,y^j,\qquad a\in A,\ j\in\mathbb Z_m. \]

两个元素相乘时，麻烦出在把 $y^j$"穿过"$b$：

\[ (a y^i)(b y^j)=a\,y^i b\,y^{-i}\,y^{i+j} =a\,\alpha^i(b)\,y^{i+j}, \]

其中

\[ \alpha(a)=yay^{-1} \]

是 $y$ 对 $A$ 的共轭作用。因为 $A$ 正规，$yay^{-1}\in A$，所以 $\alpha$ 是 $A$ 的一个自同构；因为 $|y|=m$，$\alpha^m(a)=y^may^{-m}=a$，即 $\alpha^m=\mathrm{id}$。

这个乘法公式说明：$G$ 的全部非交换性都来自 $\alpha$。若 $\alpha=\mathrm{id}$，则 $G=A\times\mathbb Z_m$ 是 Abel 群；$\alpha$ 越"不平凡"，群越非交换。结构上这是一个半直积

\[ G\cong A\rtimes_{\alpha}\mathbb Z_m. \]

这里需要交代 $\gcd(|A|,m)=1$ 这个条件的作用：群论中的 Schur–Zassenhaus 定理保证，当正规子群与商群的阶互素时，扩张一定分裂——$G$ 一定是半直积（而不是更一般的、由 $2$-cocycle 扭结的扩张，后者见第 7 节），并且补群存在且在共轭意义下唯一。本文不证明这个定理，但要记住结论：互素阶保证了"$A$ 加循环补"这个描述是完备且良定义的，这是整个算法能成立的前提之一。

4.2 作用矩阵：把 $\alpha$ 变成线性代数¶

要让算法处理 $\alpha$，需要把它写成矩阵。分三步：

第一步，用第 3 节的方法把 $A$ 分解为不变因子直积，并按素数归并为 Sylow 分量：

\[ A=A_{p_1}\times A_{p_2}\times\cdots, \qquad A_p=\mathbb Z_{p^{e_1}}\times\cdots\times\mathbb Z_{p^{e_s}}. \]

第二步，注意 Abel 群的每个 Sylow $p$-子群是唯一的（所有 $p$ 幂阶元素的集合），因此被任何自同构保持。所以 $\alpha$ 分解为各 Sylow 分量上的自同构 $\alpha_p$，不存在分量之间的交叉项。

第三步，在每个 Sylow 分量上取定 Abel 基后，$\alpha_p$ 就是一个可逆的整数线性变换；在分量的底（即 $p$-挠部分）上，它表示为有限域 $\mathbb F_p$ 上的可逆矩阵 $M$。于是

群结构由三类数据完全控制：

Abel 群 $A$ 的不变因子（第 3 节已解决）；

循环补群的阶 $m$；

作用自同构 $\alpha$ 在合适基下的矩阵（的共轭类）。

第 3 点是新东西，也是同构测试的难点所在：基可以任意换，$M$ 本身不是不变量，$M$ 的共轭类（相似类）才是。

4.3 标准分解：消除表达的任意性¶

还有一个更隐蔽的任意性：同一个群 $G$ 可能有多种 $(A,y)$ 表达。例如 $G=A\rtimes\mathbb Z_m$ 中把 $y$ 换成 $y^k$（$\gcd(k,m)=1$）仍是合法补群生成元；$A$ 也可能有多个"最大的"候选。如果两个待测群各自给出不同的表达，直接比较矩阵毫无意义。

Le Gall 的解决办法是定义标准分解（standard decomposition）：在所有合法分解中取循环阶最小（因而最规范）的那个，把它作为群的规范描述。计算标准分解只需要：

量子阶查找（测候选 $y$ 的阶）；
Abel 群分解（第 3 节，刻画候选 $A$）；
构造性成员测试（检验元素属于哪个子群、换算坐标）。

每件工具都是 $\operatorname{poly}(\log|G|)$，候选的数量也有多项式界，所以这一步整体关于 $\log|G|$ 为多项式。此后，同构测试只需在两边标准分解之间进行。

5. 同构判据：幂后共轭¶

5.1 设定与目标¶

设两个待测群已经算出匹配的标准分解

\[ G=A\rtimes_{\alpha}\langle y\rangle,\qquad H=B\rtimes_{\beta}\langle z\rangle, \]

并且前置检查已通过：$A\cong B$（用第 3 节的 Abel 判定准则）、$|y|=|z|=m$。记 $\alpha,\beta$ 在各自 Abel 基下的作用矩阵为 $M_\alpha,M_\beta$（在各有限域分量上分别讨论）。本节推导：

同构判据：$G\cong H$ 当且仅当存在 $k\in\mathbb Z_m^*$ 与基变换 $P$，使

\[P\,M_\alpha\,P^{-1}=M_\beta^{\,k}.\]

即：一个矩阵与另一个矩阵的第 $k$ 次幂相似——"幂后共轭"。

5.2 同构在补群上能做什么¶

设 $\varphi:G\to H$ 是同构。先看 $\varphi(y)$。把 $\varphi$ 复合上商映射 $H\to H/B\cong\mathbb Z_m$，得到满同态 $G\to\mathbb Z_m$，其核包含 $A$；标准分解的匹配性保证它诱导的正是商群之间的同构 $G/A\to H/B$。而 $\mathbb Z_m$ 的自同构恰为乘以单位 $k\in\mathbb Z_m^*$（生成元必须映到生成元，阶为 $m$ 的元素恰为 $z^k$、$\gcd(k,m)=1$）。因此

\[ \varphi(y)=b\,z^k,\qquad b\in B,\ k\in\mathbb Z_m^*. \]

同时，标准分解的规范性保证 $\varphi$ 把 $A$ 映到 $B$；在两边 Abel 基下，这个 Abel 群同构就是一个可逆的基变换矩阵 $P$：

\[ \varphi(a)\ \longleftrightarrow\ P\,\mathbf a, \]

其中 $\mathbf a$ 是 $a$ 的坐标列向量。

5.3 逐步推导幂后共轭方程¶

同构必须保持共轭作用，即对一切 $a\in A$：

\[ \varphi\bigl(y\,a\,y^{-1}\bigr)=\varphi(y)\,\varphi(a)\,\varphi(y)^{-1}. \]

左边：由 $\alpha$ 的定义，$yay^{-1}=\alpha(a)$，所以左边 $=\varphi(\alpha(a))$，坐标为

\[ P\,M_\alpha\,\mathbf a. \]

右边：代入 $\varphi(y)=bz^k$：

\[ (bz^k)\,\varphi(a)\,(bz^k)^{-1} =b\,z^k\,\varphi(a)\,z^{-k}\,b^{-1}. \]

关键一步：$\varphi(a)\in B$ 且 $B$ 是 Abel 群，所以 $b$ 与 $z^k\varphi(a)z^{-k}\in B$ 可交换，$b\cdots b^{-1}$ 消去：

\[ b\,z^k\,\varphi(a)\,z^{-k}\,b^{-1} =z^k\,\varphi(a)\,z^{-k} =\beta^{\,k}\bigl(\varphi(a)\bigr), \]

最后一步用了 $\beta$ 的定义迭代 $k$ 次（$\beta^k(c)=z^k c z^{-k}$）。右边坐标为

\[ M_\beta^{\,k}\,P\,\mathbf a. \]

左右相等且对一切 $\mathbf a$ 成立，因此

\[ P\,M_\alpha\,\mathbf a=M_\beta^{\,k}P\,\mathbf a \ \Longrightarrow\ P\,M_\alpha\,P^{-1}=M_\beta^{\,k}. \]

这就是判据的必要性。充分性也成立：给定满足方程的 $k,P$，定义 $\varphi(ay^j)=\bigl(P\text{ 对应的元素}\bigr)z^{kj}$，直接验证它保持第 4.1 节的乘法公式，从而是同构。推导中两处不可省略的依据再强调一次：$B$ 可交换（消去 $b$）和 $k$ 必须是单位（商群同构）。

5.4 从矩阵相似到多重集合离散对数¶

剩下的问题是纯线性代数：给定 $M_\alpha,M_\beta$，是否存在 $k\in\mathbb Z_m^*$ 使 $M_\alpha\sim M_\beta^k$（相似）？

矩阵相似当且仅当有理标准形（rational canonical form）相同，等价地不变因子/初等因子组相同。若逐个枚举 $k\in\mathbb Z_m^*$ 再比较有理标准形，$k$ 有 $\varphi(m)$ 种取法，而 $m$ 可以到 $|G|$ 量级——这是指数搜索，必须避免。

换个角度看相似条件。把特征多项式在扩域中完全分解，设 $M_\alpha$ 的特征值多重集合为

\[ X=\{x_1,\ldots,x_v\},\qquad M_\beta\ \text{的特征值多重集合为}\ Y=\{y_1,\ldots,y_v\}. \]

相似矩阵有相同的特征值多重集合；而 $M_\beta^k$ 的特征值恰为 $\{y_1^k,\ldots,y_v^k\}$（特征值随矩阵幂次取幂，这是 Jordan 块或直接对角化的直接推论）。于是必要条件——并且在配合有理标准形逐块核对后也是充分条件——是：

多重集合离散对数（set discrete logarithm）：给定有限域（扩域）中的两个多重集合 $X,Y$，寻找 $k$ 使

\[\{y_1^k,\ldots,y_v^k\}=X\quad(\text{作为多重集合相等}).\]

5.5 为什么朴素做法失败，Le Gall 如何解决¶

朴素思路是"逐个猜配对"：猜 $x_1=y_{\pi(1)}^k$，解普通离散对数得 $k$，再验证其余元素。它有两个指数障碍：

配对组合爆炸：$v$ 个元素的配对有 $v!$ 种，逐一枚举是指数的。
模阶歧义：由单个方程 $x_i=y_{\pi(i)}^k$ 解出的 $k$ 只确定到模 $\operatorname{ord}(y_{\pi(i)})$；不同配对给出不同模数的剩余类，中国剩余定理不一定能把它们拼成一个公共的 $k$（各 $\operatorname{ord}(y_j)$ 未必互素，同余式组可能不相容，需要回溯）。

Le Gall 的观察是：这两个障碍本质上是"带有多重配对约束的周期查找"，而 Abel HSP 恰好擅长同时处理耦合的周期约束。他把整个 set discrete logarithm 编码为若干个 Abel HSP 实例：隐藏子群的结构同时记录"哪个 $x$ 对应哪个 $y$ 的幂"与"$k$ 在各模数下的剩余"，一次 HSP 求出隐藏子群即同时消除配对歧义与模阶歧义，而不必枚举。每个 HSP 实例的规模是 $\operatorname{poly}(v,\log|\mathbb F|)$，实例个数也是多项式，因此总的求解时间为

\[ \operatorname{poly}\bigl(v,\ \log|\mathbb F|\bigr), \]

其中 $v$ 是矩阵维数（$v\le\log_2|A|$，因为每个不变因子分量至少贡献一个因子 $2$），$\log|\mathbb F|$ 是扩域的表值长度（扩域次数不超过矩阵维数，故也是 $\operatorname{poly}(\log|G|)$)。逐项看：因子 $v$ 来自矩阵维数与多重集合大小；因子 $\log|\mathbb F|$ 来自域中元素的比特长度与域运算代价；HSP 框架本身贡献关于这两个量的多项式开销。

最后，若找到合法的 $k$，回溯整条推导链：离散对数给出 $k$，矩阵共轭给出 $P$，$P$ 与 Abel 基变换（第 3 节的 Smith 坐标）合成 $A\to B$ 的显式映射，再配上 $y\mapsto z^k$（适当补上 $B$ 中的校正项），即组装出显式群同构。判定与构造是同一个算法的两个输出。

6. 小例子：平凡作用与反演作用¶

取 $A=\mathbb Z_3$、$m=2$，把第 4–5 节的全部机制在最小尺度上演算一遍。

6.1 平凡作用给出 $\mathbb Z_6$¶

若 $y$ 对 $A$ 的作用平凡，即 $\alpha(a)=a$，作用矩阵是 $1\times1$ 矩阵 $[1]$。此时乘法公式退化为

\[ (a,y^i)(b,y^j)=(a+b,\ y^{i+j}), \]

即直积 $\mathbb Z_3\times\mathbb Z_2$。由中国剩余定理（$\gcd(2,3)=1$），

\[ A\rtimes\mathbb Z_2\cong\mathbb Z_3\times\mathbb Z_2\cong\mathbb Z_6. \]

6.2 反演作用给出 $S_3$¶

若作用为反演

\[ \alpha(a)=-a\pmod 3, \]

作用矩阵是 $[-1]=[2]$（$\mathbb F_3$ 中 $-1\equiv2$）。注意 $[2]^2=[4]=[1]$，确有 $\alpha^2=\mathrm{id}$，与 $m=2$ 自洽。此时

\[ \mathbb Z_3\rtimes_{-1}\mathbb Z_2\cong S_3: \]

把 $A=\mathbb Z_3$ 的生成元对应到 $3$-循环 $(123)$，把 $y$ 对应到对换 $(12)$，则对换共轭 $3$-循环确实把它取逆：$(12)(123)(12)=(132)=(123)^{-1}$，这正是 $\alpha(a)=-a$。两个生成元满足 $S_3$ 的定义关系，故同构。

6.3 用判据验证二者不同构¶

两群的 $A$（不变因子都是 $(3)$）与 $m=2$ 完全相同，唯一差别在 $1\times1$ 作用矩阵 $[1]$ 与 $[2]$。套用幂后共轭判据：

可取的幂次：$k\in\mathbb Z_2^*=\{1\}$，只有 $k=1$；
$1\times1$ 可逆矩阵的共轭：$P[p]P^{-1}=[p]$，因为 $\mathbb F_3^*$ 可交换，一维情形共轭不改变任何东西；
因此判据要求 $[1]=[2]^1=[2]$，在 $\mathbb F_3$ 中不成立。

故两群不同构。这与直接观察一致：$\mathbb Z_6$ 可交换而 $S_3$ 不可交换。注意判据里"$k$ 只允许取单位"这一点在本例中是决定性的——如果允许 $k=0$，$[2]^0=[1]$ 会错误地判为同构，但 $z^0=e$ 根本不生成商群，对应的"映射"不是双射。

这个例子还说明判据中 $\mathbb Z_m^*$ 的"幂次自由度"何时真正起作用：$m=2$ 时 $\mathbb Z_2^*$ 只有一个元素，幂自由度消失；$m\ge3$ 时才会出现"矩阵不共轭但幂后共轭"的非平凡同构（见练习 6 第 3 题）。

7. 群扩张等价与一般边界¶

7.1 比 Abel-by-cyclic 更一般的扩张¶

一般群扩张写作短正合列

\[ 1\to A\to G\to Q\to1, \]

含义是 $A\trianglelefteq G$ 且 $G/A\cong Q$，但 $Q$ 不一定能嵌入 $G$ 作为子群（扩张不一定分裂）。此时结构由两部分数据决定：

作用：$Q$ 对 $A$ 的共轭作用（在 $A$ Abel 时，这使 $A$ 成为 $Q$-模）；
$2$-cocycle：取截面 $s:Q\to G$（每个陪集选一个代表），乘法亏量

\[ s(q)s(q')=f(q,q')\,s(qq') \]

定义函数 $f:Q\times Q\to A$。群乘法结合律迫使 $f$ 满足 cocycle 方程（对 $A$ Abel、作用记为 $q\cdot a$ 的加法记号）：

\[ q\cdot f(q',q'')+f(q,q'q'')=f(q,q')+f(qq',q''), \]

即**$2$-cocycle 条件**——它正是"结合律在代表元层面的表达"。

截面本身有任意性：把 $s(q)$ 换成 $c(q)s(q)$（$c:Q\to A$ 任意），$f$ 会加上一个由 $c$ 决定的coboundary。因此扩张的等价类不是由单个 cocycle、而是由它的上同调类（$H^2(Q,A)$ 中的元素）决定。于是扩张等价测试 = "作用是否相容 + 两个 cocycle 是否属于同一上同调类"，两者都是线性代数/同调性质的约束。Zatloukal（Zoo 202）对若干参数族用 Abel HSP 加速这些线性与同调约束的求解。

7.2 边界：这些结果没有解决什么¶

必须如实说明适用范围，三类保留条款：

不等于一般群同构已解决：Le Gall 算法依赖 Abel-by-cyclic 结构承诺（存在 Abel 正规子群与互素阶循环补）。对没有这种结构的群（例如幂零类更高的群、单群的直积等），标准分解与幂后共轭判据都可能失效或不再完备。
不等于图同构已解决：图同构可自然地化为置换群相关的问题，但置换群一般不是 Abel-by-cyclic 群，本文算法不直接适用。
依赖模型承诺：互素阶 $\gcd(|A|,m)=1$ 保证了 Schur–Zassenhaus 分裂与补群的共轭唯一性；unique encoding（每个元素唯一标签）保证了 HSP 中"函数在不同陪集取不同值"的良定义性。超出这些承诺时，standard decomposition 和幂后共轭判据都可能失效。

8. 小结¶

本文的链条可以概括为四句话：

Abel 群同构由关系子群的 Smith 标准形完全决定：生成元的阶给出自由直积 $D$，Abel HSP 求出关系子群 $K$，Smith 标准形给出唯一不变因子序列，比较序列即判定同构，而且构造性；
Abel-by-cyclic 群还需额外记录循环补群对正规 Abel 子群的共轭作用；互素阶条件（Schur–Zassenhaus）保证半直积描述完备，标准分解消除表达任意性；
两个作用给出同构，当且仅当适当幂次（$k\in\mathbb Z_m^*$）之后两个作用矩阵在基变换下共轭：$PM_\alpha P^{-1}=M_\beta^k$；推导的关键两步是商群同构迫使 $k$ 为单位、$B$ 可交换使补群校正项 $b$ 消去；
幂后共轭经特征多项式化为多重集合离散对数；Le Gall 将其分解为若干 Abel HSP，同时消除配对组合与模阶歧义，在 $\operatorname{poly}(v,\log|\mathbb F|)$ 时间求 $k$。

练习题¶

练习 1【同构与结构不变量】（→ 1.1 节）

基础：写出群同构的定义（保持运算的双射），并对正文的 $\varphi:\mathbb Z_4\to\{1,i,-1,-i\}$、$\varphi(a)=i^{\,a}$ 取 $a=2$、$b=3$ 验证 $\varphi(a*b)=\varphi(a)\varphi(b)$。
基础：$\mathbb Z_6$ 与 $S_3$ 都有 $6$ 个元素，说明它们为什么不同构，并指出你用到了哪个结构不变量。
进阶：设 $\varphi:G\to H$ 是保持运算的双射。证明 $\varphi(e_G)=e_H$ 与 $\varphi(x^{-1})=\varphi(x)^{-1}$，并由此说明同构保持一切由乘法表决定的性质。

提示：对 $\varphi(e_Ge_G)=\varphi(e_G)\varphi(e_G)$ 两边消去 $\varphi(e_G)$。

练习 2【黑盒群模型与经典瓶颈】（→ 1.3 节）

基础：列出黑盒群模型给算法的输入与接口（唯一编码、群运算预言机、生成元组），并说明输入长度为什么只有 $O(\log|G|)$。
进阶：乘法表输入下经典穷举判定同构约需 $|G|^{\log|G|+O(1)}$ 时间。把它改写成黑盒模型输入长度 $n=\log|G|$ 的函数，解释为什么这一时间是指数的。

提示：$|G|^{\log|G|}=2^{(\log|G|)^2}$。

练习 3【关系子群与 Abel HSP 分解】（→ 3.1 节）

基础：设 Abel 群 $G=\langle g_1,g_2\rangle$，$|g_1|=4$、$|g_2|=6$。写出 $D$ 与 $\Phi$ 的定义，说明 $\Phi$ 为什么是满射，并验证 $(4,0),(0,6)\in K$。
进阶：在 $S_3$ 中取 $g_1=(12)$、$g_2=(123)$（阶分别为 $2,3$）。计算 $\Phi\bigl((1,1)+(1,1)\bigr)$ 与 $\Phi(1,1)\,\Phi(1,1)$，说明二者不相等，并指出正文推导的哪一步对非交换群失效。

提示：$(12)(123)=(23)$，而 $(23)^2=e$、$(123)^2=(132)$。

练习 4【Smith 标准形与不变因子判定】（→ 3.3 节）

基础：写出有限 Abel 群同构的判定准则。$\mathbb Z_{12}$ 与 $\mathbb Z_2\times\mathbb Z_6$ 群阶相同，分别求出它们的不变因子序列并判断是否同构。
基础：在正文 3.4 节的例子中，用 $|G|=|D|/|K|=36/6$ 复核 $G\cong\mathbb Z_6$ 的结论。
进阶：求 $\mathbb Z_4\times\mathbb Z_6$ 的不变因子分解。

提示：先按素数拆成初等因子 $\mathbb Z_4\times\mathbb Z_2\times\mathbb Z_3$，再用中国剩余定理按"每个素数取一列"的方式重新组装成整除链。

练习 5【Abel-by-cyclic 群与作用矩阵】（→ 4.2 节）

基础：在 $G=A\rtimes_\alpha\langle y\rangle$ 中推导乘法公式 $(ay^i)(by^j)=a\,\alpha^i(b)\,y^{i+j}$，并说明 $\alpha=\mathrm{id}$ 时 $G$ 为什么退化为 Abel 直积。
基础：解释为什么 $A$ 的每个 Sylow 子群都被 $\alpha$ 保持，从而作用矩阵可以按素数分量分块、没有交叉项。
进阶：证明在 $A\rtimes_\alpha\langle y\rangle$ 中若把补群生成元 $y$ 换成 $y^k$ 且 $\gcd(k,m)=1$，则新生成元对应的作用矩阵变为 $M_\alpha^{\,k}$。

提示：直接计算 $y^k a y^{-k}$，并说明 $\gcd$ 条件用在哪里。

练习 6【幂后共轭判据】（→ 5.3 节）

基础：完整陈述幂后共轭判据，并解释 $k$ 为什么必须取自 $\mathbb Z_m^*$ 而不是整个 $\mathbb Z_m$。
进阶：第 5.2 节断言 $\mathbb Z_m$ 的自同构恰为"乘以 $k\in\mathbb Z_m^*$"。证明它，并举例说明 $k$ 非单位时映射 $z\mapsto z^k$ 为何不是同构。
进阶：在 $\mathbb Z_5\rtimes\mathbb Z_4$ 中比较两个作用 $\alpha:a\mapsto2a$ 与 $\beta:a\mapsto3a$：它们给出的两个群是否同构？

提示：$\mathbb Z_4^*=\{1,3\}$，检查是否存在 $k\in\mathbb Z_4^*$ 使 $[3]=[2]^k$ 在 $\mathbb F_5$ 中成立；并说明为什么 $k$ 不能取 $2$。

练习 7【多重集合离散对数】（→ 5.4 节）

基础：陈述多重集合离散对数问题的定义，并说明为什么 $M_\beta^{\,k}$ 的特征值恰为 $M_\beta$ 各特征值的 $k$ 次幂。
基础：列出"逐个猜配对、解普通离散对数"做法的两个指数障碍，并说明 Le Gall 的 Abel HSP 编码如何同时消除它们。
进阶：在 $\mathbb F_7$ 中求所有 $k$ 使多重集合 $\{2^k,3^k\}=\{4,5\}$，并指出单个方程 $2^k=4$ 的解为什么不足以确定答案（模阶歧义的具体体现）。

提示：$\operatorname{ord}(2)=3$、$\operatorname{ord}(3)=6$，把条件拆成两个同余方程。

练习 8【最小例子与适用边界】（→ 6.1 节）

基础：取 $A=\mathbb Z_3$、$m=2$：写出平凡作用与反演作用在 $\mathbb F_3$ 上的作用矩阵，并用判据说明两群不同构（注意 $\mathbb Z_2^*=\{1\}$，一维矩阵共轭不改变任何东西）。
基础：验证 $(12)(123)(12)=(132)=(123)^{-1}$，说明"对换共轭 $3$-循环等于取逆"正是反演作用 $\alpha(a)=-a$。
进阶：解释群同构、群扩张等价和图同构三者为何不能互换结论：每个问题的输入承诺分别是什么，本文算法依赖其中哪些？

提示：对照第 7.2 节的三条保留条款。

参考文献¶

Zoo 编号 127：Kevin Cheung 与 Michele Mosca, Decomposing Finite Abelian Groups.
Zoo 编号 128：François Le Gall, An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem.
Zoo 编号 202：Kevin Zatloukal, Classical and Quantum Algorithms for Testing Equivalence of Group Extensions.