2020-2021:teams:alchemist:hardict:qrp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:hardict:qrp [2020/05/16 16:09] hardict [三次剩余] |
2020-2021:teams:alchemist:hardict:qrp [2020/05/16 16:13] (当前版本) hardict [三次剩余] |
||
|---|---|---|---|
| 行 5: | 行 5: | ||
| [[https://en.wikipedia.org/wiki/Cipolla%27s_algorithm|wiki百科]] | [[https://en.wikipedia.org/wiki/Cipolla%27s_algorithm|wiki百科]] | ||
| - | 对于 $x^{2} \equiv a \mod{p}$ | + | 对于 $x^{2} \equiv a \pmod{p}$ |
| 可以随机找一个数$s,\quad s.t:(\frac{s^{2}-a}{p})=-1,即s不是p的二次剩余$,可以知道找到$s$的期望次数为2 | 可以随机找一个数$s,\quad s.t:(\frac{s^{2}-a}{p})=-1,即s不是p的二次剩余$,可以知道找到$s$的期望次数为2 | ||
| 行 11: | 行 11: | ||
| 考虑$\mathbb{Z}(w=\sqrt{s^{2}-a})=\{j+kw\}$以及如下定理 | 考虑$\mathbb{Z}(w=\sqrt{s^{2}-a})=\{j+kw\}$以及如下定理 | ||
| - | * 普通列表项目普通列表项目$w^{p} = w*(w^{2})^{\frac{p-1}{2}}=w*(s^{2}-a)^{\frac{p-1}{2}} \equiv -w \mod{p}$ | + | * $w^{p} = w*(w^{2})^{\frac{p-1}{2}}=w*(s^{2}-a)^{\frac{p-1}{2}} \equiv -w \pmod{p}$ |
| - | * 普通列表项目$(a+b)^{p} \equiv a^{p}+b^{b} \mod p$ | + | * $(a+b)^{p} \equiv a^{p}+b^{b} \pmod p$ |
| 解为$x \equiv (s+w)^{\frac{p+1}{2}}:\\ | 解为$x \equiv (s+w)^{\frac{p+1}{2}}:\\ | ||
| - | (s+w)^{p+1} = (s+w)^{p}(s+w) \equiv (s^{p}+w^{p})(s+w) \equiv (s-w)(s+w) = (s^{2}-w^{2}) = a \mod{p}$ | + | (s+w)^{p+1} = (s+w)^{p}(s+w) \equiv (s^{p}+w^{p})(s+w) \equiv (s-w)(s+w) = (s^{2}-w^{2}) = a \pmod{p}$ |
| ====== 三次剩余 ====== | ====== 三次剩余 ====== | ||
| 行 35: | 行 35: | ||
| 类比二次剩余Cipolla算法,设a的根为$\theta \neq a$ | 类比二次剩余Cipolla算法,设a的根为$\theta \neq a$ | ||
| - | $C=\{j+k\theta+l\theta^{2}}\$,随机生成$j,k,l$得到$y=j+k\theta+l\theta^{2}$ | + | $C=\{y=j+k\theta+l\theta^{2}\}$,$C$与$\mathbb{Z}_{p^{3}}$同构,$y^{p-1}\equiv 1 \pmod{p}$ |
| + | |||
| + | 随机生成$j,k,l$得到$y=j+k\theta+l\theta^{2}$ | ||
| + | |||
| + | $z \equiv y^{\frac{p-1}{3}} \pmod{p},z^{3} \equiv 1 \pmod{p}$ | ||
| + | |||
| + | 若$z$仅含一次项$(k^{'}\theta)^{3} \equiv 1 \pmod{p}$,取$x \equiv (k^{'})^{-1} \pmod{p}$即为一个解 | ||
| - | $z \equiv y^{\frac{p-1}{3}} \pmod{p},z^{3} \euqiv 1 \pmod{p}$ | ||
2020-2021/teams/alchemist/hardict/qrp.1589616549.txt.gz · 最后更改: 2020/05/16 16:09 由 hardict
