本节是Cipolla算法的补充说明,把上一节没有展开的,进行了说明。
上一节讲了Cipolla算法,思路很精妙。一些朋友反映没有特别明白,英文资料读起来困难,总有一些人求根问底😸,本篇再补充说明一些,主要内容还是上篇给出的参考资料链接。
这是一个类似复数的元素构成的集合。$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$域上。
根据数论中拉格朗日定理,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
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!