密码学的数学基础（二）

本篇主要介绍密码学中有关初等数论的同余理论内容

同余理论

同余

$n$为正整数，$a$和$b$分别模$n$，如果得到相同的余数，就说$a$和$b$在模$n$下满足同余关系，$n$是模数（modulus）：

$$a\equiv b \ (\bmod n )$$

定义：如果$a,b,n∈Z，n>0$，如果$n|(a-b)$，称$a$和$b$在模$n$下同余，记作$a≡b (\bmod n)$。

性质：

$$a\equiv b \ (\bmod n ) \iff a=qn+b,\exists q\in Z$$ $$自反性：a\equiv a\ (\bmod n),a\in Z$$ $$对称性：a\equiv b\ (\bmod n)\iff b\equiv a\ (\bmod n)$$ $$传递性：a\equiv b\ (\bmod n),b\equiv c\ (\bmod n)\Rightarrow a\equiv c\ (\bmod n)$$

乘法逆元

之前我们学过倒数：两个数乘积为$1$，就称两个数互为倒数。可以根据这个思路来引入乘法逆元：

因为我们有：

$$2×3\bmod 5 =1$$

在这里，因为在模$5$下，$3×2=1$，也可以理解为3和2在模5下互为”倒数”，不过这里不叫倒数，而是换了一种叫法：乘法逆元，进而我们可以做如下变换：

$$(7×2^{-1})\bmod 5=(7×3)\bmod 5=1$$

这里的$(7×2^{-1}) \bmod 5$就可以理解为7乘以”2的乘法逆元”模5。

乘法逆元(modular inverse)定义：$a∈Z，n∈N$，如果$az≡1 (\bmod n)$，我们把$z$叫做模$n$下$a$的乘法逆元。记作$a^{-1}=z$，模$n$下的乘法逆元只考虑小于$n$的。

逆元是相互的，$z^{-1}=(a^{-1})^{-1}=a^{(-1)×(-1)}=a$

逆元有唯一性，$a$在模$n$下的乘法逆元是唯一的。

乘法逆元存在法则：$\gcd(a,n)=1\iff$模$n$下，$a$有乘法逆元。

扩展欧几里得算法：$\gcd(a,n)=1\ ,\ as+tn=1$，等式两边同时模$n$，得到$as\equiv 1 (\bmod n)$，即模$n$下$a$的逆元就是$s$。

一次同余方程

消去律

如果$a,n\in Z,n>0$，如果$\gcd(a,n)=d$,得到：

$$az\equiv az'\ (\bmod n)\Rightarrow z\equiv z'\ (\bmod \frac{n}{d})$$

求解一次同余方程：$105x-62\equiv 1\ (\bmod 6)$

可以先把62移过去：$105x\equiv 63\ (\bmod 6)$

$gcd(105,63)=21\ ,\ gcd(21,6)=3$然后使用消去律:$\frac{105x}{21}\equiv \frac{63}{21}(\bmod \frac{6}{3})$

最后得到$5x\equiv 3\ (\bmod 2)\Rightarrow x\equiv 3×5^{-1}\ (\bmod 2)$

又求得$5$在模$2$下的逆元为$1$。

得到$x\equiv 1\ (\bmod 2)$

这里，x的解应该是一个解集：$\{…,-3,-1,-1,3,5,7,…\}$

一次同余方程有解的条件：

如果$\gcd(a,n)=d$，得到$ax\equiv b\ (\bmod n)$有解$\iff d|b$

如果$\gcd(a,n)=1$，同余方程有唯一解。

剩余类

假设我们在模$n$下：余数为$0$的数我们放在一个集合里，余数为$1$的数我们放在一个集合里……

以上子集被称为剩余类，模$n$下含有整数$a$的剩余类记为$[a]_n$，简记为$[a]$。

如模$3$的$3$个剩余类：

$$[0]=\{...,-3,0,3,...\},[1]=\{...,-2,1,4,...\},[2]=\{...,-1,2,5,...\}$$

剩余类的每个整数都叫做这个剩余类的代表元。

剩余类集合：$Z_n=\{[0],[1],[2],…,[n-1]\}$，比如$Z_5=\{[0],[1],[2],[3],[4]\}$

一些运算：

$[a]+[b]=[a+b]$,$[a]×[b]=[a×b]\ (a,b\in Z)$，最后需要再模$n$。

设$u,v\in Z_n$,如果$uv=[1]$,得到$uv$互为乘法逆元。

定义集合${Z_n}^*=${$Z_n$中有乘法逆元的剩余类}

中国剩余定理

一次同余方程组：设两两互素的模数$n_1,…,n_m\in N$，以及任何整数$a_1,…,a_m\in Z$，设$N=\sideset{}{}\prod^m_{i=1}n_i$

能得到：

$$\begin{cases}x\equiv a_1\ (\bmod n_1)\\...\\x\equiv a_m\ (\bmod n_m)\end{cases}$$

此方程组必有解，求解此方程组需要用到中国剩余定理，又叫孙子定理。

求解公式为：

$$x\equiv\sum_{i=1}^mN_iN_i^{-1}a_i\pmod N$$

其中，$N_i=\frac{N}{n_i}，N_i^{-1}$是$N_i$在模$n_i$的乘法逆元。

在$[0,N]$以内，方程组在模$N$下有唯一解。

在这篇文章里对中国剩余定理有更详细的介绍：RSA学习笔记（三）

欧拉函数

定义所有正整数$n\in N$，欧拉函数是求在$0$和$n-1$之间有多少正整数和$n$互素。

有关性质：

①设两两互素的正整数$n_1,…,n_m\in N$，设$N=\sideset{}{}\prod^m_{i=1}n_i$：

$$\phi(n)=\sideset{}{}\prod^m_{i=1}\phi(n_i)$$

②$p$为素数：$\phi(p^k)=p^{k-1}\phi(p)$

③$\phi(p)=p-1$

乘法阶

设$a\in {Z_n}^*$，使得$a^k\equiv 1 (\bmod n)$的最小正整数$k$称作$a$在模$n$下的乘法阶，无歧义时可以说是$a$的阶。

设$a\in {Z_n}^*$的乘法阶为$k$，得到以下整数在模$n$下彼此不同：$a^0,a^1,a^2,…,a^{k-1}$

性质：

①$a^i\equiv 1(\bmod n)\iff k|i$

②$a^i\equiv a^j (\bmod n)\iff i\equiv j (\bmod k)$

原根

之前学习了乘法阶：$a,n$互素的情况下有$k$满足$a^k\equiv 1(\bmod n)$的最小正整数为$a$在模$n$下的乘法阶。

$a$在模$n$下的乘法阶为$ord_n(a)$

如果存在$g\in Z,gcd(g,n)=1$，有$ord_n(g)=\phi (n)$，那么$g$为模$n$下的原根，有：

$$g^{ord_n(g)}\equiv g^{\phi (n)}\equiv 1(\bmod n)$$

注意，模$n$下不一定有原根，$\phi (n)$乘法阶的整数不一定存在。

原根存在的条件：

设$p$为奇素数，$e$为正整数，当$n=1,2,4,p^e,2p^e$时，模$n$下存在原根。

在RSA中，$n=pq$，可见$n$不存在原根。

找原根算法：

1.对$\phi (n)$进行因式分解，求出素因子$p_1,…,p_r$。

2.任选$a\in Z_n^*$，如果$a^{\frac {\phi (n)}{p_i}}\bmod n ≠1,i=1,…,r$，那么$a$为原根。

离散对数

$a,n$互素，必然存在唯一的整数$x\ (0≤x≤\phi (n))$，有$a\equiv g^x(\bmod n)$，那么称$x$为以$g$为底的$a$模$n$的指标或离散对数：

$$\log_g(a)\equiv x(\bmod \phi (n))\iff a\equiv g^x(\bmod n)$$

不难发现，在离散对数中，指数位模的其实是$\phi (n)$，如：

$g^{70}\equiv g^{70\bmod 24}\equiv g^{22}(\bmod 35)$

有关对数的运算法则在离散对数中也通用。

欧拉定理

设$a\in {Z_n}^*$，得到：

$$a^{\phi(n)}\equiv1\ (\bmod n)$$

且$k|\phi(n)$，$k$是$a$在模$n$下的阶。

${Z_n}^*$里的整数彼此不相同，每个整数乘$a$后仍然各不相同，乘以$a$在模$n$下整数仍然在集合内。

乘以$a$之前和之后在模$n$下所得集合不变，仍为${Z_n}^*$

定理：

设$a\in Z_n^*,m\in Z$，$a$在模$n$下的乘法阶为$k$，得到$a^m(m\in Z)$在模$n$下乘法阶为$k’=\frac{k}{\gcd(m,k)}$

费马小定理

根据欧拉定理简单变形得到（$p$为素数）：

$$a^p\equiv a\ (\bmod p)$$

二次剩余

设${a\in Z_n}^*$，如果存在$b^2\equiv a (\bmod n),b\in Z$，则称$a$为模$n$下的二次剩余，并称$b$为$a$在模$n$下的平方根。

反之，称$a$为二次非剩余：

$$a\in Z_p^*/(Z_p^*)^2$$

二次剩余集合：

$$(Z^*_n)^2=\\{b^2\bmod n|b\in Z^*_n\\}$$

得到：$a$是模$n$下的二次剩余$\iff a\in(Z^*_n)^2$

从这里开始，没有特殊说明，$Z_n,{Z_n}^*$整数进行乘法默认模$n$

因为每个二次剩余对应${Z_p}^*$的两个整数，二次剩余数量恰好是原来的一半，另一半为二次非剩余：

$$|(Z^*_p)^2|=\frac{p-1}{2}$$

可以使用欧拉准则判断$a$是不是二次剩余：

如果$p$为奇素数，$a\in {Z_p}^*$：

①$a^{\frac{p-1}{2}}=±1$（用欧拉定理可证明）

②为二次剩余：$a\in (Z^*_p)^2\Rightarrow a^{\frac{p-1}{2}}=1$

$$a^{\frac{p-1}{2}}=b^{p-1}=b^{\phi(p)}=1$$

③为二次非剩余：$a\notin (Z^*_p)^2\Rightarrow a^{\frac{p-1}{2}}=-1$

给定$a,b$，如何判断$ab$乘积是不是二次剩余？

如果$p$为奇素数，$a,b\in {Z_p}^*$：

$$\begin{cases} a,b\in (Z_p^*)^2\Rightarrow ab\in (Z_p^*)^2\\\\ a,b\notin (Z_p^*)^2\Rightarrow ab\in (Z_p^*)^2\\\\ a\in (Z_p^*)^2,b\notin (Z_p^*)^2\Rightarrow ab\notin (Z_p^*)^2\\\\ a\notin (Z_p^*)^2,,b\in (Z_p^*)^2\Rightarrow ab\notin (Z_p^*)^2 \end{cases}$$

这个结论还是可以用欧拉准则证明。但是，知道$ab$乘积是否为二次剩余不能反向推算$a$和$b$是不是二次剩余。

$$(ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}$$

都为二次剩余或二次非剩余，乘积都为$1$；否则乘积为$-1$。

如何判断$-1$是不是模$p$下的二次剩余？

性质，对其进行模$4$：

$$p\equiv 1(\bmod 4)\iff -1\in(Z^*_p)^2$$

当模数为$p^k$形式时，规律：a是模$p^k$下二次剩余$\iff$$a$是模$p$下二次剩余

当模数为$n$时，不妨回想一下学过的中国剩余定理：

$$\begin{cases}x\equiv a_1\ (\bmod n_1)\\\\...\\\\x\equiv a_m\ (\bmod n_m)\end{cases}^{中国剩余定理\Rightarrow}_{\Leftarrow中国剩余映射} x\equiv x_0(\bmod N)$$

向量$(a_1,…,a_m)$和$x_0$存在双射，称为中国剩余映射。

设$n>1$为奇数，且$n=p_1^{k_1}×…×p_m^{k_m}$，根据中国剩余映射可以得到（证明暂时不考虑）：

$$a\in(Z_n^*)^2\iff a_i\in(Z^*_{p_i^{k_i}})^2,i=1,...,m$$

暂且记为：大模同余，小模也同余。

根据算数基本定理：

$$|(Z_n^*)^2|=|(Z^*_{p_1^{k_1}})^2×...×(Z^*_{p_m^{k_m}})^2|=\sideset{}{}\prod^m_{i=1}\frac{\phi(p_i^{k_i})}{2}=\frac{\phi(n)}{2^m}$$

得到在$n$下的二次剩余的数量：

$$|(Z_n^*)^2|=\frac{\phi(n)}{2^m}$$

勒让德符号

定义$p$为奇素数，整数$a$满足$\gcd(a,p)=1$，勒让德符号定义为：

$$(\frac{a}{p})=\begin{cases}1,a\in(Z_p^*)^2 \\\\-1,a\in Z_p^*/(Z_p^*)^2 \end{cases}$$

使用勒让德符号可以更快地判断一个任意整数是否为模数的二次剩余。

规定：$(\frac{a}{p})=0\ \ (p|a)$

性质：（p为奇素数，$a,b\in Z$）

①$(\frac{a}{p})\equiv a^{\frac{p-1}{2}}(\bmod p)$，特别地，$(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}$

②$(\frac a p)(\frac b p)=(\frac{ab}p)$

③$a\equiv b(\bmod p)\Rightarrow(\frac a p)=(\frac b p)$

④$(\frac 2 p)=(-1)^{\frac{p^2-1} 8}$，这个式子可以转化成另一种形式：$2\in(Z_p^*)^2\iff p \equiv ±1(\bmod 8)$

⑤二次互反律：设p和q为奇素数：$(\frac p q)=(-1)^{\frac{p-1}2\cdot\frac{q-1}2}(\frac q p)$

雅可比符号

设a为整数，n为正奇数，且$n=p_1…p_t$，其中$p_i$都为奇素数（彼此可以相等），雅可比符号定义为（左边为雅可比符号，右边为勒让德符号）：

$$(\frac a n)=(\frac a {p_1})...(\frac{a}{p_t})$$

规定$(\frac a 1)=1$

易知$gcd(a,n)>1\iff (\frac a n)=0$

性质：（m和n为正奇数，$a,b\in Z$）

①$(\frac {-1} n)=(-1)^{\frac{n-1}2}$

②$(\frac a n)(\frac b n)=(\frac{ab}n)$

③$a\equiv b(\bmod n)\Rightarrow(\frac a n)=(\frac b n)$

④$(\frac 2 n)=(-1)^{\frac{n^2-1} 8}$

⑤$(\frac a{mn})=(\frac a m)(\frac a n)$

⑥二次互反律的推广：设$m$和$n$为正奇数，得到：

$$(\frac mn)=(-1)^{\frac{m-1}2\cdot\frac{n-1}2}(\frac nm)$$

可以引申出以下关系：

$$m\equiv 1 (\bmod 4)\ or \ n\equiv1(\bmod 4)\iff(\frac mn)=(\frac nm)$$

注意：雅克比符号并不能判断$a$是否是模$n$下的二次剩余。

半素数又叫二素数。名字虽带有素数，但是它的本质还是合数。

$n$为半素数，得到$n=pq，p,q$都是$n$的素因子。（$p$和$q$可以相同）