区块链中的数学-二次剩余和欧拉准则

本节讲了二次剩余和判别二次剩余方程是否有解的欧拉准则,并且给出了欧拉准则的相关证明。

## 写在前面 上一节讲了[secp256k1点压缩和公钥恢复原理](https://learnblockchain.cn/article/1526),在讲压缩格式的时候,有一点个人认为需要补充: 例如非压缩格式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)$ ## 欧拉准则 欧拉准则又称欧拉判别法,描述了勒让德符号的性质: 1. 如果 $(\frac{n}{p})=0$,那么n = 0 2. 如果 $(\frac{n}{p})=1$,那么存在整数x, $x^2 \equiv n (mod\ p)$ 即n是模p的二次剩余 3. 如果 $(\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的二次非剩余。 ## 小结 本节讲了二次剩余和判别二次剩余方程是否有解的欧拉准则,并且给出了欧拉准则的相关证明。 可以看到证明的过程中,用到了**本原根**的性质,之前没有说过。 鉴于本原根不是几句话就能说清楚的,就不占用本节的篇幅了,下一节好好介绍一下它吧。 另外,本节只讲了判断二次剩余方程有解的问题,不要忘了,我们的目的还没达到。我们是要知道如何求解?本原根介绍完后,接着这个内容继续。 好了,下一篇就说说[本原根](https://learnblockchain.cn/article/1523)相关内容。 欢迎关注公众号:blocksight

写在前面

上一节讲了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)$

欧拉准则

欧拉准则又称欧拉判别法,描述了勒让德符号的性质:

  1. 如果 $(\frac{n}{p})=0$,那么n = 0

  2. 如果 $(\frac{n}{p})=1$,那么存在整数x, $x^2 \equiv n (mod\ p)$ 即n是模p的二次剩余

  3. 如果 $(\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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-07-27 21:38
  • 阅读 ( 72 )
  • 学分 ( 4 )
  • 分类:入门/理论

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/27851

联系我们

aliyinhang@gmail.com