欧拉准则

对于质数ppp，x2≡a(modp)⇔ap−12≡1(modp)x^2\\equiv a\\pmod p\\Leftrightarrow a^{\\frac{p-1}{2}}\\equiv 1\\pmod px2≡a(modp)⇔a2p−1​≡1(modp)。

证明：

充分性：
ap−12=(x2)p−12=xp−1≡1(modp)a^{\\frac{p-1}{2}}=(x^2)^{\\frac{p-1}{2}}=x^{p-1}\\equiv 1\\pmod pa2p−1​=(x2)2p−1​=xp−1≡1(modp)

必要性：
设ggg为模ppp意义下的原根，gi≡a(modp)g^i\\equiv a\\pmod pgi≡a(modp)，则
gi(p−1)2≡1(modp)g^{\\frac{i(p-1)}{2}}\\equiv 1\\pmod pg2i(p−1)​≡1(modp)
ggg为原根，则(p−1)∣i(p−1)2(p-1)|\\frac{i(p-1)}{2}(p−1)∣2i(p−1)​，iii为偶数，x≡gi2(modp)x\\equiv g^{\\frac i2}\\pmod px≡g2i​(modp)

Cipolla算法

一种求解模奇质数意义下的二次同余方程的算法。

即ppp为奇质数，给定aaa，求xxx满足：x2≡a(modp)x^2\\equiv a\\pmod px2≡a(modp)

复杂度O(log⁡p)O(\\log p)O(logp)

具体算法:

可能需要死记硬背一下。。。

随机找到任意一个bbb，满足b2−a≡wb^2-a\\equiv wb2−a≡w，www是模ppp意义下的非二次剩余(wp−12≡−1(modp)w^{\\frac{p-1}{2} }\\equiv -1\\pmod pw2p−1​≡−1(modp))。

类似于虚数，设i=wi= \\sqrt wi=w​，扩域后每个数表达为(a,b)=a+bi(a,b)=a+bi(a,b)=a+bi，运算为：
(r1,d1)+(r2,d2)=(r1+r2,d1+d2)(r_1,d_1)+(r_2,d_2)=(r_1+r_2,d_1+d_2)(r1​,d1​)+(r2​,d2​)=(r1​+r2​,d1​+d2​)
(r1,d1)⋅(r2,d2)=(r1r2+d1d2w,r1d2+r2d1)(r_1,d_1)·(r_2,d_2)=(r_1 r_2+d_1d_2w,r_1d_2+r_2d_1)(r1​,d1​)⋅(r2​,d2​)=(r1​r2​+d1​d2​w,r1​d2​+r2​d1​)

&lt;G,+,⋅&gt;&lt;G,+,·&gt;<G,+,⋅>是个环，满足交换律和结合律。

答案即为：x=(b+i)p+12x=(b+i)^{\\frac {p+1}{2}}x=(b+i)2p+1​

证明：
x2\\quad x^2x2
=(b+i)p(b+i)=(b+i)^p(b+i)=(b+i)p(b+i)
=(bp+ip)(b+i)=(b^p+i^p)(b+i)=(bp+ip)(b+

继续阅读与本文标签相同的文章

无标签
最新文章 最热文章
收藏 打印

特别推荐 2026年05月18日 星期一

精彩发现

热门标签

阻止表单提交 窗口 关闭浏览器 清除 CDATA css文件 光标位置 坐标 javascrpt !important 超链接 数字

相关文章