写在前面
上一节讲了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
