RSA加密算法数学基础

概念：给定正整数 $m$ ，全体整数可按照模 $m$ 是否同余分成若干两两不相交的集合，使得每一个集合中的任意两个正整数对模 $m$ 一定同余，而属于不同集合的任意两个整数对模 $m$ 不同余，每一个这样的集合称为模 $m$ 的同余类或剩余类。
例子：取 $m=7$ ，则 $\{0,7,14,...\}$ 是模7的同余类。
定理：对于给定的正整数 $m$ ，有且恰有 $m$ 个不同的模 $m$ 的剩余类。
模 $m$ 的m个剩余类可分别记为 $[i]$ ， $i$ 为该剩余类中整数除 $m$ 所得的余数，可分别如下表示：
$[0]=\{...,-2m,-m,0,m,2m,...\}$
$[1]=\{...,-2m+1,-m+1,1,m+1,2m+1,... \}$
$[2] = \{...,-2m+2,-m+2,2,m+2,2m+2,... \}$
...
$[m-1] = \{...,-2m+(m-1),-m+(m-1),m-1,m+(m-1),2m+(m-1),... \}$

概念：在整数模 $m$ 的所有剩余类中各取一个代表元素 $a_1,a_2,...,a_m,(a_i\in [i-1],i = 1,2,...,m)$ ，则称 $a_1,a_2,...,a_m$ 为模 $m$ 的完全剩余系。完全剩余系 $0,1,2,...,m-1称为最小非负完全剩余系$ 。
例子： $7,15,16,-4,-10,5,-1$ 为模7的一组完全剩余系。 $0,1,2,3,4,5,6$ 为模 $7$ 的最小非负完全剩余系。
$Z_m$ 表示由 $m$ 的最小非负完全剩余系集合 $Z_m = \{ 0,1,2,...,m-1\}$ 。 $Z_m$ 中的加法、减法、乘法都是模 $m$ 下的运算。
定理：设 $m$ 是正整数，整数 $a$ 满足 $gcd(a,m)=1$ ， $b$ 是任意整数。若 $x$ 遍历模 $m$ 的一个完全剩余系，则 $ax+b$ 也遍历模 $m$ 的一个完全剩余系。
定理：设 $m_1,m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个完全剩余系， $y$ 遍历模 $m_2$ 的一个完全剩余系，则 $m_1y+m_2x$ 遍历模 $m_1m_2$ 的一个完全剩余系。

在模 $m$ 的一个剩余类当中，如果有一个数与 $m$ 互素，则该剩余类中所有的数均与 $m$ 互素，这时称该剩余类与 $m$ 互素。
概念：与 $m$ 互素的剩余类的个数称为欧拉函数，记为 $\phi(m)$ 。 $\phi(m)$ 等于 $Z_m$ 当中与 $m$ 互素的数的个数。对于任意一个素数 $p$ ， $\phi(p)=p-1$ 。
例子： $\phi(6)=2$ ，表示 $Z_6$ 中与 $6$ 互素的数的个数，既 $1,5$ 。

概念：在与 $m$ 互素的 $\phi(m)$ 个模 $m$ 的剩余类中各取一个代表元 $a_1,a_2,...,a_{\phi(m)}$ ，它们组成的集合称为模 $m$ 的一个既约剩余系或简化剩余系。 $Z_m$ 中与 $m$ 互素的数构成模 $m$ 的一个既约剩余系，称为最小非负既约剩余系。
定理：设 $m$ 是正整数。整数 $a$ 满足 $gcd(a,m)=1$ 。若 $x$ 遍历模 $m$ 的一个既约剩余系，则 $ax$ 也遍历模 $m$ 的一个既约剩余系。
定理：设 $m_1,m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个既约剩余系， $y$ 遍历模 $m_2$ 的一个既约剩余系，则 $m_1y+m_2x$ 遍历模 $m_1m_2$ 的一个既约剩余系。

推论：设 $m,n$ 是两个互素的整数，则 $\phi(mn)=\phi(m)\phi(n)$ 。
定理：若 $m = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$ ，则 $\phi(m) = m\prod_{i=1}^{k}(1-{1\over{p_i}})$ 。
证明：当 $m = p^{e}$ 为单个素数的方幂时，在模 $m$ 的完全剩余系 $\{0,1,2,...,p^e-1\}$ 的 $p^e$ 整数中与 $p$ 不互素的只有 $p$ 的倍数，共有 $p^{e-1}$ ，因此与 $p^e$ 互素的数共有 $p^e-p^{e-1}$ ，即 $\phi(p^e)=p^{e}-p^{e-1}=p^e(1-{1\over p})$ ，根据上面的推论有 $\phi(m) = \phi(p_1^{e_1})\phi(p_2^{e_2})...\phi(p_k^{e_k})=\prod_{i=1}^{k}p^{e_i}_i(1-{1\over{p_i}})=m\prod_{i=1}^{k}(1-{1\over{p_i}})$ 。
例子： $\phi(120)=120\cdot(1-{1\over2})(1-{1\over3})(1-{1\over5})=32$
定理：设 $m$ 是正整数， $r\in{Z_m}$ ，若 $gcd(r,m)=1$ ，则存在整数 $s\in{Z_m}$ ，使得 $rs\equiv1(mod\ m)$ ，整数 $s$ 也成为 $r$ 模整数 $m$ 下的乘法逆元。
例子：求 $15\ (mod\ 26)$ 的乘法逆元。
解： $15$ 与 $26$ 互素，存在乘法逆元。做辗转相除法，可得：
$26 = 1\times15+11$
$15 = 1\times11+4$
$11 = 2\times4+3$
$4=1\times3+1$
由此有：
$1 = 4-3$
$\ \ =4-(11-2\times4)$
$\ \ =3\times4-11$
$\ \ =3\times(15-11)-11$
$\ \ =3\times15-4\times11$
$\ \ =3\times15-4\times(26-15)$
$\ \ =7\times15-4\times26$
所以 $15\ mod(\ 26)$ 的乘法逆元为 $7$ 。
欧拉定理：设 $m$ 是正整数， $r\in{Z_m}$ ，若 $gcd(r,m)=1$ ，则 $r^{\phi(m)}\equiv{1}(mod\ m)$ 。