本节讲了二次剩余和判别二次剩余方程是否有解的欧拉准则,并且给出了欧拉准则的相关证明。
上一节讲了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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!