二次剩余 Cipolla 算法浅析
2022/7/6 1:21:02
本文主要是介绍二次剩余 Cipolla 算法浅析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
参考资料
- yyb blog
- Kewth blog
求解
\[x^2=n \pmod p \]仅介绍模数 p 为奇素数的解法,也就是 Cipolla 算法。
判定是否存在二次剩余
设 \(n=g^a,x=g^b\),由于原根环的长度为 \(p-1\) (是个偶数),
列出方程 \(2b = a \pmod {p-1}\),根据贝祖定理,当且仅当 \(\gcd(p-1,2)=2 \mid a\) 时有解。
因此
- 在 \(a\) 为偶数时有解 \(g^{ a\over 2}\) 和 \(-g^{ a\over 2}\)。
- 在 \(a\) 为奇数时无解。
用原根求解较慢,尝试寻找等价条件。
- 在 \(a\) 为偶数时,\(n^{p-1 \over 2}=g^{a(p-1) \over 2}=(g^{a \over2})^{p-1}=1 \pmod p\)
- 在 \(a\) 为奇数时,\(n^{p-1 \over 2}=g^{a(p-1) \over 2}\),由于 ${a(p-1)\over 2} \ne 0 \pmod {p-1} $,因此 \(n^{p-1 \over 2} \ne 1\) 。但是 \((n^{p-1 \over 2})^2=n^{p-1}=1 \pmod p\),所以 \(n^{p-1 \over 2}=-1\)。
因此 有无解等价于 \(n^{p-1 \over 2}\) 是否为 \(1\)。
上述证明过程的一些推论
- 若有解,必有两个 ,因为 \(g^{ a\over 2}\) 和 \(-g^{ a\over 2}\) 的奇偶性不同。同时不会有更多个,因为 \(2b = a \pmod {p-1}\) 的步长为 \({p-1 \over \gcd(2,p-1)}={p-1 \over 2}\) 加两次又回到第一个点了。
- 在 \(\bmod \: p\) 意义下有 \({p-1\over 2}\) 个二次剩余,\({p-1\over 2}\) 个二次非剩余。(考虑 \(p-1\) 是偶数,\([1,p-1]\) 的数中有几个偶数和奇数)。
二次剩余的求解
先随机出一个 \(a\) ,使 \(a^2-n\) 为二次非剩余。
扩域,假设存在一个 \(w\) 使得 \(w^2=a^2-n \pmod p\)。
则 \(n=(a+w)(a-w)\) 。
- 引理1:\(w^p=-w\)(证明:\(w^p=(w^2)^{p-1 \over2}w=w(a^2-n)^{p-1 \over 2}=-w\))
- 引理2:\((a+w)^p=a^p+w^p\) 证明:\(j \in [1,p-1],{p \choose j}|p\).
有
\[(a+w)^{p+1}=(a+w)^p(a+w)=(a^p+w^p)(a+w)=(a^{p-1}a-w)(a+w)=(a-w)(a+w)=n \]因此 \((a+w)^{p+1 \over 2}\) 为一个解。
容易得出另一个解为 \(-(a+w)^{p+1 \over 2}\)
Code
#include<ctime> #include<cstdio> #include<cstdlib> #include<iostream> using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; LL power(LL x,LL k,LL MOD) { LL res=1; x=x%MOD; while(k) { if(k&1) res=res*x%MOD; x=x*x%MOD; k>>=1; } return res%MOD; } PLL mul(PLL a,PLL b,LL IOI,LL p) { return PLL((a.first*b.first%p+a.second*b.second%p*IOI%p)%p,(a.second*b.first%p+a.first*b.second%p)%p); } bool residue(LL n,LL p,LL& x0,LL& x1) { if(n==0) return (x0=x1=0,true); // 注意这个特判 if(power(n,(p-1)>>1,p)!=1) return false; LL a=rand()%p; while(!a || power(a*a-n+p,(p-1)>>1,p)==1) a=rand()%p; LL IOI=(a*a-n+p)%p; LL k=(p+1)>>1; PLL res(1,0),x(a,1); while(k) { if(k&1) res=mul(res,x,IOI,p); x=mul(x,x,IOI,p); k>>=1; } x0=res.first; x1=p-x0; if(x0>x1) swap(x0,x1); return true; } int T; LL n,p; int main() { srand(time(0)); cin>>T; while(T--) { cin>>n>>p; LL x0,x1; if(!residue(n,p,x0,x1)) puts("Hola!"); else printf("%lld %lld\n",x0,x1); } return 0; }
应用
本身可以解一元二次方程
也可以配合 exgcd,BSGS,原根之类解更多方程。
求解 一元二次方程 在模意义下的根。
bool solve(LL a,LL b,LL c,LL p,LL& x0,LL& x1) { a=(a%p+p)%p; b=(b%p+p)%p; c=(c%p+p)%p; LL d=(b*b-4*a*c%P+P)%P; if(!residue(d,p,x0,x1)) return false; d=x0; x0=(-b+d+p)*inv(a+a,p)%p; x1=(-b-d+2*p)*inv(a+a,p)%p; return true; }
- BZOJ5104 Fib数列 yyb Itst
这篇关于二次剩余 Cipolla 算法浅析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!