写在前面
上一节讲了secp256k1点压缩和公钥恢复原理,在讲压缩格式的时候，有一点个人认为需要补充：
例如非压缩格式04 + x + y, 如果不知道x,y各自的长度也无法解析。
补充说明的是：secp256k1曲线上的点都是256位的，具体到点的坐标x，y各是32字节。这样无论压缩格式还是非压缩格式，都能清楚解析了。
除了补充说明外，上节提出了一个核心问题：
已知二次模p方程，求解。
本节深入讲解下这个问题。
二次剩余
对于给定的p和n，如果有x满足：
$x^2 \equiv n(mod \ p)$
那么n在模p意义下就是二次剩余（Quadratic residue），如果x不存在，称n是模p的二次非剩余 。
有点绕，说白了就是n在模p意义下能否开根号。这个x是模p的有限域上取值。
求解该方程就是解决二次剩余问题的过程。
这样的方程是否一定有解呢？
【注：这里我们只考虑p为奇素数&n不整除p的情况】
这里需要借助一种判别方法：欧拉准则。
介绍欧拉准则前，先看一下勒让德符号（legendre symbol）
勒让德符号
$(\frac{n}{p})$是勒让德符号表示形式，有时也写成（n|p）为了书写方便。
其计算式为：
$(\frac{n}{p})=n^{\frac{p-1}{2}}(mod \ p)$
欧拉准则
欧拉准则又称欧拉判别法，描述了勒让德符号的性质：
-
如果 $(\frac{n}{p})=0$，那么n = 0
-
如果 $(\frac{n}{p})=1$，那么存在整数x, $x^2 \equiv n (mod\ p)$ 即n是模p的二次剩余
-
如果 $(\frac{n}{p})=-1$, 表明不存在整数x,$x^2 \equiv n (mod\ p)$ 即n是模p的二次非剩余
第三种情况下，a称为模p的二次非剩余。
这样的性质为何成立？
对于性质1，是显然的。下面证明下性质2，3.
性质2证明：
(1)充分性：n是p二次剩余 => $(\frac{n}{p})=1$
证明：
由费马小定理，
$n^{p-1} \equiv 1(mod\ p) \Rightarrow (n^{(p-1)/2}+1)*(n^{(p-1)/2}-1) \equiv 0(mod\ p)$
p 素数，所以两项不会同时为零，即$n^{\frac{p-1}{2}}=-1$ 或者 $n^{\frac{p-1}{2}}=1$
也证明了勒让德符号在n不为0的情况下，只能有这两种取值。
n是p的二次剩余，则存在x使得 $x^2 \equiv n (mod\ p)$，
$n^{(p-1)/2} \equiv x^{2(p-1)/2}\equiv x^{p-1} \equiv 1(mod\ p)$
即 $(\frac{n}{p})= 1$
(2)必要性：$(\frac{n}{p})= 1$ => n是p二次剩余
证明：
p 是一个奇素数，所以关于p的原根存在【原根定理】。设a是p的一个原根，则存在1 ,于是1 < j < p-1 使得 $n = a^j$,于是下式成立。
$(\frac{n}{p})= 1 \Rightarrow n^{\frac{p-1}{2}}=a^{j\frac{p-1}{2}}$
a是p的原根，所以a mod p指数是p-1, 因此p-1整除$j\frac{p-1}{2}$ ，得到j必是偶数。
令$i = \frac{j}{2} $ ,那么$ a^{i^2}= a^j=d$
所以存在一个数$a^i$的二次方同模d, 可得n是p的二次剩余.
性质3证明:
反证法证明:
假设$n^{\frac{p-1}{2}} = -1$，同时存在x使得
$x^2= n\ mod\ p$
推出$x^{p-1}= -1\ mod\ p $, 显然不会存在这样的正整数x. 即n是模p的二次非剩余。
小结
本节讲了二次剩余和判别二次剩余方程是否有解的欧拉准则，并且给出了欧拉准则的相关证明。
可以看到证明的过程中，用到了本原根的性质，之前没有说过。
鉴于本原根不是几句话就能说清楚的，就不占用本节的篇幅了，下一节好好介绍一下它吧。
另外，本节只讲了判断二次剩余方程有解的问题，不要忘了，我们的目的还没达到。我们是要知道如何求解？本原根介绍完后，接着这个内容继续。
好了，下一篇就说说本原根相关内容。
欢迎关注公众号：blocksight
