区块链中的数学-Cipolla算法补充说明

本节是Cipolla算法的补充说明,把上一节没有展开的,进行了说明。

## 写在前面 上一节讲了[Cipolla算法](https://learnblockchain.cn/article/1520),思路很精妙。一些朋友反映没有特别明白,英文资料读起来困难,总有一些人求根问底,本篇再补充说明一些,主要内容还是上篇给出的参考资料链接。 ## ${F_p}_2$为什么是域? 这是一个类似复数的元素构成的集合。$F_p$ 中元素都可以表示成${F_p}_2$中元素,即$F_p$是${F_p}_2$的一个子群。 ${F_p}_2$运算有加法,乘法,前提都是mod p.满足如下: $(a,b) + (c,d) = (a + c , b + d)$ $(a,b) × (c,d) = (ac + bdw, ad + bc)$ $w=a^2-n$ 接下来检验一下域的属性: 以上两种运算满足封闭性,可结合,可交换,有加法零元0: $a+0=(a+0\sqrt{w})+(0+0\sqrt{w})=a$ 乘法幺元是1: $a*1=(a+0\sqrt{w})*(1+0\sqrt{w})=(a*1+0*w)+(a*0+0\sqrt{w}*0\sqrt{w})=a$ 再看下是否具有加法和乘法逆元。 加法逆元比较显然, (a,b)的加逆元是(-a,-b),二者和为零。 乘法逆元是否存在? 对于(a,b)如果找到(c,d)使得 (a,b)* (c,d) = 1 则(c,d)是(a,b)的乘法逆元。 $(a,b)* (c,d)= (ac + bdw, ad + bc)$ 要使结果为1, 那么 ac + bdw = 1, ad + bc = 0 同时满足, 可以得出: $c=-b^{-1}a(bw-a^2b^{-1})^{-1}$ $d=(bw-a^2b^{-1})^{-1}$ 可以验证是正确的,所以乘法逆元也存在。因此$F_{p2}$的确是个域。 ### ${F_p}_2$域上平方根为什么同是$F_p$根? 由于运算是在${F_p}_2$域上进行的,得到的结果是否一定在$F_p$域上。 根据数论中拉格朗日定理,n次非零多项式在任何域中最多有n个根。 现在已知 $x^2-n$ 在$F_p$域上有两个根。 这些根一定也是${F_p}_2$域上的根。所以两根同属于$F_p$域。 下面再举一个Cipolla算法例子帮助理解过程。 ## 实例计算 例如求 $x^2 \equiv 10 (mod \ 13)$ 1. 检查 $\frac{10}{13}=1$, 是有解的 2. 找到一个数$a=2,a^2-10 \equiv 7(mod \ 13),(\frac{7}{13})=-1$,是二次非剩余,w = -6。 3. 计算 $x=(a+ \sqrt{a^2-n})^{\frac{p+1}{2}}=(2+\sqrt{-6})^7$ 根据${F_p}_2$域上运算规则: $(2+\sqrt{-6})^2=-2+4 \sqrt{-6}$ $(2+\sqrt{-6})^4=-1+ -3 \sqrt{-6}$ $(2+\sqrt{-6})^6=9+2 \sqrt{-6}$ $(2+\sqrt{-6})^7=6$ 最后 $\sqrt{-6}$ 即 $\sqrt{w}$一定会被消掉,这是上面说的${F_p}_2$和$F_p$域根的关系决定的。 所以得到6和13-6=7 两个解满足 $x^2 \equiv 10(mod \ 13)$。 在第2步中,可以随机选择a,因为总共有 $\frac{p-1}{2}$ 个非零解,随机找出来一个数计算 $a^2-n$, 就有将近1/2的概率是二次非剩余. ## 小结 本节是Cipolla算法的补充说明,把上一节没有展开的,进行了说明。 这样再回头去看[上一篇](https://learnblockchain.cn/article/1520)应该清楚多了,还是那句话:对理论不感兴趣的,记住结论即可。 **真要学习就不要懒!!** 最近几篇文章的思路: secp256k1公钥恢复-->二次剩余-->原根--> 二次剩余求解 --> Cipolla算法补充说明 [下一篇](https://learnblockchain.cn/article/1517)真要回到secp256k1公钥恢复实现相关了!! --- 欢迎关注公众号:blocksight

写在前面

上一节讲了Cipolla算法,思路很精妙。一些朋友反映没有特别明白,英文资料读起来困难,总有一些人求根问底,本篇再补充说明一些,主要内容还是上篇给出的参考资料链接。

${F_p}_2$为什么是域?

这是一个类似复数的元素构成的集合。$F_p$ 中元素都可以表示成${F_p}_2$中元素,即$F_p$是${F_p}_2$的一个子群。

${F_p}_2$运算有加法,乘法,前提都是mod p.满足如下:

$(a,b) + (c,d) = (a + c , b + d)$

$(a,b) × (c,d) = (ac + bdw, ad + bc)$

$w=a^2-n$

接下来检验一下域的属性:

以上两种运算满足封闭性,可结合,可交换,有加法零元0:

$a+0=(a+0\sqrt{w})+(0+0\sqrt{w})=a$

乘法幺元是1:

$a1=(a+0\sqrt{w})(1+0\sqrt{w})=(a1+0w)+(a0+0\sqrt{w}0\sqrt{w})=a$

再看下是否具有加法和乘法逆元。

加法逆元比较显然, (a,b)的加逆元是(-a,-b),二者和为零。

乘法逆元是否存在?

对于(a,b)如果找到(c,d)使得 (a,b)* (c,d) = 1 则(c,d)是(a,b)的乘法逆元。

$(a,b)* (c,d)= (ac + bdw, ad + bc)$

要使结果为1, 那么 ac + bdw = 1, ad + bc = 0 同时满足, 可以得出:

$c=-b^{-1}a(bw-a^2b^{-1})^{-1}$

$d=(bw-a^2b^{-1})^{-1}$

可以验证是正确的,所以乘法逆元也存在。因此$F_{p2}$的确是个域。

${F_p}_2$域上平方根为什么同是$F_p$根?

由于运算是在${F_p}_2$域上进行的,得到的结果是否一定在$F_p$域上。

根据数论中拉格朗日定理,n次非零多项式在任何域中最多有n个根。 现在已知 $x^2-n$ 在$F_p$域上有两个根。

这些根一定也是${F_p}_2$域上的根。所以两根同属于$F_p$域。

下面再举一个Cipolla算法例子帮助理解过程。

实例计算

例如求 $x^2 \equiv 10 (mod \ 13)$

  1. 检查 $\frac{10}{13}=1$, 是有解的

  2. 找到一个数$a=2,a^2-10 \equiv 7(mod \ 13),(\frac{7}{13})=-1$,是二次非剩余,w = -6。

  3. 计算 $x=(a+ \sqrt{a^2-n})^{\frac{p+1}{2}}=(2+\sqrt{-6})^7$

根据${F_p}_2$域上运算规则:

$(2+\sqrt{-6})^2=-2+4 \sqrt{-6}$

$(2+\sqrt{-6})^4=-1+ -3 \sqrt{-6}$

$(2+\sqrt{-6})^6=9+2 \sqrt{-6}$

$(2+\sqrt{-6})^7=6$

最后 $\sqrt{-6}$ 即 $\sqrt{w}$一定会被消掉,这是上面说的${F_p}_2$和$F_p$域根的关系决定的。

所以得到6和13-6=7 两个解满足 $x^2 \equiv 10(mod \ 13)$。

在第2步中,可以随机选择a,因为总共有 $\frac{p-1}{2}$ 个非零解,随机找出来一个数计算 $a^2-n$, 就有将近1/2的概率是二次非剩余.

小结

本节是Cipolla算法的补充说明,把上一节没有展开的,进行了说明。 这样再回头去看上一篇应该清楚多了,还是那句话:对理论不感兴趣的,记住结论即可。

真要学习就不要懒!!

最近几篇文章的思路: secp256k1公钥恢复-->二次剩余-->原根--> 二次剩余求解 --> Cipolla算法补充说明

下一篇真要回到secp256k1公钥恢复实现相关了!!

欢迎关注公众号:blocksight

区块链技术网。

  • 发表于 2020-08-07 12:27
  • 阅读 ( 966 )
  • 学分 ( 4 )
  • 分类:入门/理论

评论