2020-2021:teams:alchemist:hardict:qrp
这是本文档旧的修订版！
二次剩余(QRP)
Cipolla算法(素数情况下)
对于 $x^{2} \equiv a \mod p$
可以随机找一个数$w,\quad s.t:(\frac{w}{p})=-1,即w不是p的二次剩余$,可以知道找到$w$的期望次数为2
考虑$\mathbb{Z}(\Omega=\sqrt{w^{2}-a})$
三次剩余
2020-2021/teams/alchemist/hardict/qrp.1589615192.txt.gz · 最后更改: 2020/05/16 15:46 由 hardict
