公钥密码所需的数学基础

1. 完全剩余系
   (1) 定理1：对于给定的正整数m，有且恰有m个不同的模m的剩余类。
   (2) 定理2：设m是正整数，整数a满足gcd(a,m)=1，b是任意整数。若x遍历模m的一个完全剩余系，则ax+b也遍历m的一个完全剩余系。
   (3)定理3：设 $m_1,m_2$ 是两个互素的正整数。如果x遍历$m_1$ 的一个完全剩余系，y遍历 $m_2$ 的一个完全剩余系，则 $m_1y+m_2x$ 遍历 $m_1m_2$ 的一个完全剩余系。

2. 简化剩余系
   (1)定理1：设m是正整数，整数a满足gcd(a,m)=1.若x遍历模m的一个简化剩余系，则ax也遍历模m的一个简化剩余系。
   (2)定理2：设 $m_1,m_2$ 是两个互素的正整数。如果x遍历$m_1$ 的一个简化剩余系，y遍历 $m_2$ 的一个简化剩余系，则 $m_1y+m_2x$ 遍历 $m_1m_2$ 的一个简化剩余系。

3. 欧拉定理
   (1)推论1：设m，n是两个互素的整数，则φ(mn)=φ(m)φ(n).
   (2)定理1：若$m=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ ，则

$φ(m)=m\prod_{i=1}^{k} \left( 1-\frac{1}{p_i}\right)$

(3)定理2（欧拉定理）：设m是正整数，$r\in Z_m$ ,若gcd(r,m)=1,则$r^{φ(m)} ≡ 1 (mod m)$ 。

4. 群：设G是一个具有代数运算 $\circ$ 非空集合，并且满足：
   (1)封闭性：G中任意两个元素做运算得到的结果仍属于G；
   (2)结合律：$\forall a,b,c \in G$ ,有

$(a\circ c)\circ c = a\circ( c\circ c);$

(3)有单位元：即G中存在一个元素e：$\forall a \in G$，有

$e\circ a = a\circ e = a$

(4)有逆元：即对于任意 $a \in G$，存在一个元素 $a^{-1} \in G $，使得

$(a\circ a^{-1}) = a^{-1}\circ a = e$

5. 交换群：对于群G中的任意元素，$a,b \in G$都有

$ab = ba$

则称群G为交换群或阿贝尔群。
6. 群的阶：有限群G中的元素个数称为群的阶，记为|G|。
7. 定理1：一个有乘法的有限集合G，若其乘法在G中封闭，且满足结合律和消去律，则G是群。
8. 循环群：设G是一个群，若存在一个元素a，使得G=<a>,则称G为循环群。元素a称为G的生成元。若$\circ(a)=\infty$ ，G称为无限循环群；若$\circ(a)=n$，n是某个正整数，则G称为有限循环群。