区块链中的数学-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)$
-
检查 $\frac{10}{13}=1$, 是有解的
-
找到一个数$a=2,a^2-10 \equiv 7(mod \ 13),(\frac{7}{13})=-1$,是二次非剩余,w = -6。
-
计算 $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 )
- 分类:入门/理论
评论