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