二次剩余-Cipolla
2024-09-18 14:53:13
二次剩余 \(Cipolla\) 算法
概述
- 大概就是在模 \(p\) 意义下开根号,如求解方程\(x^2\equiv n(mod\ p)\).
- 这里只考虑 \(p\) 为素数的情况.若 \(p=2\) ,则\(x=0\ when\ n=0,x=1\ when\ n=1\).
- 若 \(p\) 为奇素数,定义勒让德符号:
\[
\lgroup\frac{n}{p}\rgroup =n^{\frac{p-1}{2}}
\]
- 则根据欧拉准则,
- 对于 \(\lgroup \frac{n}{p} \rgroup \equiv 1\) 的情况,我们随机取一个 \(a\) 使得 \(a^2-n\) 不为 \(p\) 的二次剩余,可证期望步数为 \(2\) .
- 记 \(\omega=\sqrt{a^2-n}\) ,定义一个新数域\(x+y\cdot\ \omega\),类似于复数,只是单位复数为\(\omega\).
- 那么 \(x\equiv \pm (a+\omega)^{\frac{p+1}{2}}\ (mod\ p)\),据拉格朗日定理可知虚数部分系数为 \(0\) .
- 简要论证,尝试倒推变形,
\[
x\equiv \pm (a+\omega)^{\frac{p+1}{2}}\\
x^2\equiv (a+\omega)^{p+1}\\
x^2\equiv (a+\omega)^p(a+\omega)
\]
- 注意到 \((a+\omega)^p\) 可用二项式定理展开,\((a+\omega)^p\equiv \sum_{i=0}^{p}C_p^i a_i \omega ^{a-i}\ (mod\ p)\).
- \(p\) 是个质数,.使用 \(Lucas\) 定理处理组合数,发现仅当\(i=0,i=n\)时组合数在模意义下才为非 \(0\) 的,仅计算\(i=0,i=n\),可得到\((a+\omega)^p\equiv a^p+\omega ^p\ (mod\ p)\).
- 得到这个式子后,继续对上面的式子变形,
\[
x^2\equiv (a+\omega)^p(a+\omega)\\
x^2\equiv (a^p+\omega^p)(a+\omega)
\]
- 注意到\(a^p\equiv a\) (费马小定理),而\(\omega ^p\equiv \omega * \omega^{p-1} \equiv \omega*(\omega ^2)^{\frac{p-1}{2}}\equiv \omega*(a^2-n)^{\frac{p-1}{2}}\equiv -\omega\).
- 继续变形,
\[
x^2\equiv (a^p+\omega^p)(a+\omega)\\
x^2\equiv(a-\omega)(a+\omega)\\
x^2\equiv a^2-\omega^2\\
x^2\equiv a^2-(a^2-n)\\
x^2\equiv n\ (mod\ p).
\]
- 这里的变形操作容易验证都是可逆的,可以一步一步推回去,就说明了有两个解,\(x\equiv \pm (a+\omega)^{\frac{p+1}{2}}\ (mod\ p)\).
- 时间复杂度为\(O(log^2p)\).
最新文章
- [内核笔记1]内核文件结构与缓存——inode和对应描述
- MiniProfiler
- 逻辑回归&;&;code
- centos 6.5 下用apache部署web 应用
- Magento速度优化
- 白盒测试之gmock入门篇
- PHP输出图片文件,实现浏览器缓存机制
- 使用Raphael 画图(二) 扩展的图形 (javascript)
- Eclipse中处理图片引包问题
- js 鸭式辨型法
- Zend Studio配合Xdebug调试
- Begin again
- 【翻译】Ext JS 6早期访问版本发布
- codeforces 1077F2. Pictures with Kittens (hard version)单调队列+dp
- Java反射,参数为数组
- java static方法不能被重写@Override
- 【洛谷p1164】小A点菜
- PHP获取IP地址的方法,防止伪造IP地址注入攻击
- natapp搭建外网服务器
- ReactNative For Android 项目实战总结