剩余类环上可逆矩阵的计数

$G{L}_n({\mathbb{Z}}_m)$

令$m\in {\mathbb{N}}^{+}$是任意正整数，利用数论基本定理，可以写作
$$m=p_1^{e_1}{p}_2^{e_2}\cdots p_s^{e_s}$$
其中$p_i,i=1,\cdots ,s$都是素数，$e_i,i=1,\cdots ,s$是正整数。

下面我们考虑一般线性群$G{L}_n({\mathbb{Z}}_m)$的结构。它里面的元素都是${\mathbb{Z}}_m$上的$n$阶可逆矩阵。

步骤一

首先，我们证明：
$$A\in G{L}_n({\mathbb{Z}}_m)⟺det(A)\in {\mathbb{Z}}_m^{\ast }$$
也就是说，矩阵$A$是可逆阵，当仅当它的行列式在${\mathbb{Z}}_m$上乘法可逆。

Proof:

1. 证明“$\Rightarrow$”，

   对于一个$A\in {\mathbb{Z}}_m^{n\times n}$，如果$A\in G{L}_n({\mathbb{Z}}_m)$，总存在一个$B\in {\mathbb{Z}}_m^{n\times n}$，使得
   $$AB=BA=I_n\in {\mathbb{Z}}_m^{n\times n}$$
   那么计算对应的行列式
   $$det(A)\cdot det(B)=det(B)\cdot det(A)=det(I_n)=1$$
   于是$det(A)$可逆，且$det(A{)}^{-1}=det(B)$

2. 证明“$\Leftarrow$”，

   对于一个$A\in {\mathbb{Z}}_m^{n\times n}$，如果$det(A)\in {\mathbb{Z}}_m^{\ast }$，那么总存在一个$b\in {\mathbb{Z}}_m$，使得
   $$det(A)\cdot b=b\cdot det(A)=1\in {\mathbb{Z}}_m$$
   构造$A$的伴随矩阵$A^{\ast }$，那么
   $$A{A}^{\ast }=A^{\ast }A=det(A)\cdot I_n$$
   两边同乘以$b$，
   $$(b\cdot A^{\ast })A=A(b\cdot A^{\ast })=(b\cdot det(A))\cdot I_n=I_n$$
   从而$A$可逆，且$A^{-1}=b\cdot A^{\ast }$

步骤二

然后，我们证明存在如下的群同构：
$$G{L}_n({\mathbb{Z}}_m)\cong G{L}_n({\mathbb{Z}}_{p_1^{e_1}})\times G{L}_n({\mathbb{Z}}_{p_2^{e_2}})\times \cdots \times G{L}_n({\mathbb{Z}}_{p_s^{e_s}})$$
Proof：

构造映射
$$\varphi (A):=(A\mathrm{mod}{p}_1^{e_1},A\mathrm{mod}{p}_2^{e_2},\cdots ,A\mathrm{mod}{p}_s^{e_s})$$
我们将证明它是双射。

1. 证明是单的，

   对于任意的$A,B\in G{L}_n({\mathbb{Z}}_m)$且$A\ne B$，假设有
   $$\varphi (A)=\varphi (B)$$
   那么就是说
   $$\forall k=1,\cdots ,s,A\equiv B\mathrm{mod}{p}_k^{e_k}$$
   等价于
   $$\forall k=1,\cdots ,s,\forall i,j=1,\cdots ,n,A_{ij}-B_{ij}\equiv 0\mathrm{mod}{p}_k^{e_k}$$
   那么
   $$\forall i,j=1,\cdots ,n,A_{ij}-B_{ij}\equiv 0\mathrm{mod}m$$
   也就是
   $$A\equiv B\mathrm{mod}m$$
   这与假设矛盾。因此，只要两个原像不同，它们的像就不同，是单射。

2. 证明是满的，

   对于任意的
   $$(A^{(1)},A^{(2)},\cdots ,A^{(s)})\in G{L}_n({\mathbb{Z}}_{p_1^{e_1}})\times G{L}_n({\mathbb{Z}}_{p_2^{e_2}})\times \cdots \times G{L}_n({\mathbb{Z}}_{p_s^{e_s}})$$
   我们将它拆解为$n\times n$片：
   $$\forall i,j=1,\cdots ,n,(A_{ij}^{(1)},A_{ij}^{(2)},\cdots ,A_{ij}^{(s)})\in {\mathbb{Z}}_{p_1^{e_1}}\times {\mathbb{Z}}_{p_2^{e_2}}\times \cdots \times {\mathbb{Z}}_{p_s^{e_s}}$$
   由于模数两两互素，利用 CRT，每一片都存在唯一的元素与之对应
   $$CRT(A_{ij}^{(1)}\mathrm{mod}{p}_1^{e_1},A_{ij}^{(2)}\mathrm{mod}{p}_2^{e_2},\cdots ,A_{ij}^{(s)}\mathrm{mod}{p}_s^{e_s})=A_{ij}\mathrm{mod}m$$
   将这些数排列成矩阵$A\in {\mathbb{Z}}_m^{n\times n}$，易知
   $$\forall k=1,\cdots ,s,A\mathrm{mod}{p}_k^{e_k}=A^{(k)}\in G{L}_n({\mathbb{Z}}_m)$$
   依据步骤一，得到
   $$\forall k=1,\cdots ,s,det(A)\mathrm{mod}{p}_k^{e_k}\equiv det(A\mathrm{mod}{p}_k^{e_k})\in {\mathbb{Z}}_{p_k^{e_k}}^{\ast }$$
   那么
   $$det(A)\in {\mathbb{Z}}_m^{\ast }$$
   再根据步骤一，得到
   $$A\in G{L}_n({\mathbb{Z}}_m)$$
   因此，像空间中的任意元素，都存在原像空间上的元素与之对应，是满射。

$|G{L}_n({\mathbb{Z}}_m)|$

对于剩余类环${\mathbb{Z}}_m$，其中
$$m=p_1^{e_1}{p}_2^{e_2}\cdots p_s^{e_s}$$
我们证明了群同构：
$$G{L}_n({\mathbb{Z}}_m)\cong G{L}_n({\mathbb{Z}}_{p_1^{e_1}})\times G{L}_n({\mathbb{Z}}_{p_2^{e_2}})\times \cdots \times G{L}_n({\mathbb{Z}}_{p_s^{e_s}})$$
因此两者的大小相同，
$$|G{L}_n({\mathbb{Z}}_m)|=|G{L}_n({\mathbb{Z}}_{p_1^{e_1}})|\times |G{L}_n({\mathbb{Z}}_{p_2^{e_2}})|\times \cdots \times |G{L}_n({\mathbb{Z}}_{p_s^{e_s}})|$$
接下来我们计算$G{L}_n({\mathbb{Z}}_{p^e})$的大小。

步骤一

对于素域${\mathbb{Z}}_p$，因为它是无零因子环，因此任意的非零向量$v$，向量组 { v } \{v\} {v}是线性无关的。否则，存在$a\ne 0$，使得$a\cdot v=0$；不失一般性的，令第一分量$v[1]\ne 0$，那么$a\cdot v[1]=0$，这与无零因子环矛盾。

为了构造出${\mathbb{Z}}_p$上的一个可逆阵，这等价于在空间${\mathbb{Z}}_p^n$上挑选一个大小为$n$的线性无关向量组：

1. 挑选第一个向量$v_1$，它除了不能是零向量。而其他的选择都可以令 { v 1 } \{v_1\} {v1​}是线性无关的，有$p^n-1$种选择
2. 挑选第二个向量$v_2$，为了保持线性无关，它不能落在子空间 S p a n ( { v 1 } ) Span(\{v_1\}) Span({v1​})内部。其他的选择都可以保持 { v 1 , v 2 } \{v_1,v_2\} {v1​,v2​}是线性无关的，因此有$p^n-p$种选择
3. 挑选第三个向量$v_2$，为了保持线性无关，它不能落在子空间 S p a n ( { v 1 , v 2 } ) Span(\{v_1,v_2\}) Span({v1​,v2​})内部。其他的选择都可以保持 { v 1 , v 2 , v 3 } \{v_1,v_2,v_3\} {v1​,v2​,v3​}是线性无关的，因此有$p^n-p^2$种选择
4. 继续挑选其他向量，保持选出的向量组是线性无关的，直到选出$n$个向量。

因此，
$$|G{L}_n({\mathbb{Z}}_p)|=(p^n-1)(p^n-p)\cdots (p^n-p^{n-1})$$

步骤二

$\varphi (p^e)=p^{e-1}(p-1)$，因此环${\mathbb{Z}}_{p^e}$中包含$p^{e-1}$个不可逆元素。实际上，这些不可逆元素都是$p$的倍数：
S = { k p :   k = 0 , 1 , ⋯   , p e − 1 − 1 } S = \{kp:\, k=0,1,\cdots,p^{e-1}-1\} S={kp:k=0,1,⋯,pe−1−1}
令$E_{ij},i,j=1,\cdots ,n$表示一个$n$阶方阵，它只有第$i$行第$j$列的元素是$1$，其他位置都为$0$

我们将证明，所有的$G{L}_n({\mathbb{Z}}_{p^e})$中的可逆阵$A^{\prime }$都形如
$$A^{\prime }=A+\sum _{i,j}{s}_{ij}\cdot E_{ij},\exists A\in G{L}_n({\mathbb{Z}}_p),\exists s_{ij}\in S$$

1. 证明“$\Rightarrow$”，

   任取$A^{\prime }\in G{L}_n({\mathbb{Z}}_{p^e})$，它满足
   $$(det(A^{\prime }),p^e)=1$$
   易知
   $$(det(A^{\prime }),p)=1$$
   因此，选取矩阵$A=A^{\prime }\mathrm{mod}p$，再令$A^{\prime }-A={\sum }_{i,j}{s}_{ij}\cdot E_{ij}$，容易验证：
   $$A\in G{L}_n({\mathbb{Z}}_p)$$
   以及
   $$\forall i,j=1,\cdots ,n,s_{ij}\in S$$

2. 证明“$\Leftarrow$”，

   任取$A\in G{L}_n({\mathbb{Z}}_p)$，等价于$det(A)\in {\mathbb{Z}}_p^{\ast }$，也就是$(det(A),p)=1$

   那么，构造${\mathbb{Z}}_{p^e}$上矩阵
   $$A^{\prime }=A+\sum _{i,j}{s}_{ij}\cdot E_{ij},\forall s_{ij}\in S$$
   由于$\forall i,j,p|s_{ij}$，因此
   $$det(A^{\prime })\equiv det(A^{\prime }\mathrm{mod}p)\equiv det(A)\mathrm{mod}p$$
   从而
   $$(det(A^{\prime }),p)=(det(A),p)=1$$
   也就是$A^{\prime }$的行列式与$p$互素，进一步可以得到
   $$(det(A^{\prime }),p^e)=1$$
   这等价于
   $$A^{\prime }\in G{L}_n({\mathbb{Z}}_{p^e})$$

因此，每存在$1$个$A\in G{L}_n({\mathbb{Z}}_p)$，就存在$|S{|}^{n^2}$个$A^{\prime }\in G{L}_n({\mathbb{Z}}_{p^e})$与之对应，并且不重叠。即：
$$|G{L}_n({\mathbb{Z}}_{p^e})|=|G{L}_n({\mathbb{Z}}_p)|\cdot |S{|}^{n^2}=|G{L}_n({\mathbb{Z}}_p)|\cdot p^{(e-1)n^2}$$

实例 - $G{L}_n({\mathbb{Z}}_{26})$

由于$m=2^1\times 13^1$，因此有
$$G{L}_n({\mathbb{Z}}_{26})\cong G{L}_n({\mathbb{Z}}_2)\times G{L}_n({\mathbb{Z}}_{13})$$
群$G{L}_n({\mathbb{Z}}_2)$的大小为：
$$|G{L}_n({\mathbb{Z}}_2)|=(2^n-1)(2^n-2)\cdots (2^n-2^{n-1})\times 2^{(1-1)n^2}$$
群$G{L}_n({\mathbb{Z}}_{13})$的大小为：
$$|G{L}_n({\mathbb{Z}}_{13})|=(13^n-1)(13^n-13)\cdots (13^n-13^{n-1})\times 13^{(1-1)n^2}$$
得到：
$$|G{L}_n({\mathbb{Z}}_{26})|=(2^n-1)(2^n-2)\cdots (2^n-2^{n-1})\cdot (13^n-1)(13^n-13)\cdots (13^n-13^{n-1})$$
这就是 Hill 加密方案的密钥空间大小。