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

写在前面

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