信息安全数学基础4
4二次同余式和平方剩余
重点：平方剩余的判定，legendre符号及计算方法。
这一章的重点就是求解rabin公钥系统
引入：
rabin公钥系统密钥的生成:
随机生成两个大素数$p,q$,$N=p \times q$
公钥为$N$，私钥为$(p,q)$
加密：
$c \equiv m_2 \pmod{N}$
其中，B是明文，C是密文。
解密;
即求解二次同余式 $x_2 \equiv c \pmod{N}$
所以第四章的核心就是如何求解二次同余式。
4.1二次同余式和平方剩余
首先，生么是二次同余式？
前面，我们已经遇到了，形如$x_2 \equiv a \pmod{m}$的就是二次同余式，如果$(a,m)=1$则同余式有解。
有解，则称$a$为模$m$的平方剩余(二次剩余)，相反则是平方非剩余(二次非剩余)
强调：
两个条件
$$\begin{cases} x_2 \equiv a \pmod{m} \\ (a,m)=1 \end{cases}$$
$a$一般在模m的完全剩余系里找。${1,2,3..m-1}$
eg：
求$m=5$的平方剩余和非平方剩余
解:
因为
$$1^2 \equiv 1 \pmod{5},2^2 \equiv 4 \pmod{5}$$
$$3^2 \equiv4 \pmod{5},4^2 \equiv 1 \pmod{5}$$
所以1，4是模5的平方剩余，2，3是模5的非平方剩余。
平方剩余的个数？
定理：
若$p$为奇素数，平方剩余和非平方剩余皆为$\frac{p-1}{2}$个，
平方剩余为：$1^2，2^2,….(\frac{p-1}{2})^2$
求得各个$a$
eg:
求$p=17$的平方剩余
解：
$p=17 ; \rightarrow \frac{p-1}{2}=5$
一共5个，
$$1^2 \equiv 1 \pmod{17},2^2 \equiv 4, \pmod{17},3^2 \equiv 9 \pmod{17}$$
$$4^2 \equiv 16 \pmod{17},5^2 \equiv 8, \pmod{17},6^2 \equiv 2 \pmod{17}$$
$$7^2 \equiv 1 \pmod{17},8^2 \equiv 4, \pmod{17}$$
所以，$1,2,4,8,9,13,15,16$是，其他是非平方剩余。
接下来是反向判断，a值是否是平方剩余
当$p$是奇素数，$(a,p)=1$
如果$$a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$$
a是模p的平方剩余
如果$$a^{\frac{p-1}{2}} \equiv -1 \pmod{p}$$
a是模p的非平方剩余。
当a是模p的平方剩余时，$x^2 \equiv a \pmod{p}$恰好有两个解。
eg：
判断$8$是不是模$17$的平方剩余？
$$a^{\frac{p-1}{2}} = 8^{\frac{17-1}{2}} = 8^8 \equiv 1 \pmod{177}$$
所以，8是模17的平方剩余。
平方剩余推论：
如果$p$是奇素数，$(a_1,p)=1,(a_2,p)=1$
1，如果$a_1,a_2$都是模p的平方剩余，则$a_1a_2$是模p的平方剩余；
2，如果$a_1,a_2$都是模p的平方非剩余，则$a_1a_2$是模p的平方剩余；
1，如果$a_1,a_2$一个是模p的平方剩余，另一个不是，则$a_1a_2$是模p的平方非剩余；
4.2Legendre符号及其计算方法
$$ (\frac{a}{p})=\begin{cases}1, \quad a是模p的平方 \\ -1, \quad a是模p的非平方 \\ 0 \quad a能被p整除，即p|a \end{cases} $$
这符号的值，就只有1，-1，和0.
欧拉判别法：
若p是奇素数，a是整数，则$$(\frac{a}{p}) \equiv a^{ \frac{p-1}{2}} \pmod{p}$$
Legendre符号的一些性质：
1，$(\frac{1}{p})=1,(\frac{-1}{p})=-1^{\frac{p-1}{2}}$
2,$ (\frac{a+p}{p})= (\frac{a}{p})$
3,$(\frac{ab}{p})=(\frac{a}{p}) \cdot(\frac{b}{p})$
4,若$(a,p)=1,则(\frac{a^2}{p})=1$
5,$若，a\equiv b \pmod{p},则(\frac{a}{p})=(\frac{b}{p})$
这些性质可以利用于，Legendre符号的一些计算，方便判断，是否是模平方剩余。
高斯引理：
如果p是奇素数，a是整数，$(a,p)=1$.如果$$1 \cdot a,2 \cdot a,3 \cdot a….( \frac{p-1}{2}) \cdot a$$中模p的最小剩余大于$\frac{p}{2}$的个数为m
则$$(\frac{a}{p})=(-1)^m$$.
eg:
$当p=5,a=8时，因1 \cdot 8 \equiv 3 \pmod{5},2 \cdot 8 \equiv 1 \pmod{5}$，故$m=1,所以，(\frac{8}{5})=(-1)^1=-1$
$当p=7,a=2时，因为1 \cdot 2 \equiv 2 \pmod{7}，2 \cdot 2 \equiv 4 \pmod{7}， 3 \cdot 2 \equiv 6 \pmod{7}$
$所以，m=2,所以，(\frac{2}{7}=(-1)^2)=1$
尼玛。还有个定理。特殊情况快速判定
如果，p为奇素数，则
$(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$
二次互反定律
我的天啊，还有个神TM的二次互反定律
如果$q,p$都是奇素数，$(q,p)=1$,则
$$(\frac{q}{p})=(-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}(\frac{p}{q})$$
提示一下：这里要用到前面的公式2
eg:
3是模17的平方非剩余？
解：
$(\frac{3}{17})=(-1)^{\frac{3-1}{2} \cdot \frac{17-1}{2}} (\frac{17}{3})=(\frac{2}{3})=(-1)^{\frac{3^2-1}{8}}=-1$
advance example：
判断$x^2 \equiv 137 \pmod{227}$是否有解。
解;
$$137 \equiv-90 \equiv -2 \times 3^2 \times 5 \pmod{227}$$
$$\rightarrow(\frac{137}{227})=(\frac{-1}{227}) \cdot(\frac{2}{227}) \cdot (\frac{3^2}{227}) \cdot(\frac{5}{227})$$
$$\rightarrow(\frac{-1}{227})=-1,(\frac{2}{227})=-1,(\frac{3^2}{227})=1$$
$$\rightarrow (\frac{5}{227}) = (-1)^{\frac{5-1}{2} \cdot \frac{227-1}{2}} (\frac{2}{5})=(-1)^{(\frac{5^2-1}{8})}=-1$$
故$$(\frac{137}{227})=-1$$无解
4.3Rabin公钥密码系统
基于前面的知识，我们会知道
$$c \equiv m^2 \pmod N$$
如果知道$N=q \times p$
那么$\begin{cases} m^2 \equiv c \pmod{p} \\ m^2 \equiv c \pmod{q} \end{cases}$
最后拓展一下;
如果p是形如$4k+3$的素数，有同余式$x^2 \equiv \pm a^{\frac{(p+1)}{4}} \pmod{p}$
其他的自己拓吧，累了。
如果p,q是形如$4k+3$的素数，有同余式$x^2 \equiv a \pmod{pq}$
其解$x \equiv \pm x_1 \pm x_2$
第四章完